- Java Collection FrameWork
- Array(배열), List, ArrayList의 차이점
- List
- 문제풀이
1. Java Collection Framework
Java Collection Framework는 Java에서 데이터를 저장, 관리 및 처리하기 위한 표준 라이브러리입니다. 이는 자주 사용되는 자료구조(데이터 컨테이너)와 이를 다루는 다양한 알고리즘을 제공합니다.
1-1. 특징
- 인터페이스 기반 설계: Java Collection Framework는 주로 인터페이스 기반으로 설계되어 있습니다. 이를 통해 다양한 종류의 자료구조를 표준화된 방식으로 사용할 수 있으며, 유연성과 재사용성을 강화합니다.
- 제네릭(Generic) 지원: Java Collection Framework는 제네릭을 활용하여 타입 안정성을 제공합니다. 제네릭은 컴파일 시점에 오류를 미리 감지하여 안전한 타입 변환을 가능하게 합니다.
- 동적 크기 조정: 대부분의 컬렉션 클래스들은 동적으로 크기를 조정할 수 있습니다. 요소를 추가하거나 제거할 때 자동으로 크기가 조정되므로 메모리 관리에 용이합니다.
- 다양한 자료구조 제공: Java Collection Framework는 다양한 자료구조를 지원합니다. 주요 인터페이스로는 List, Set, Queue, Map 등이 있으며, 각각의 구현체들로 기능을 구현합니다.
- 알고리즘 및 검색 기능 제공: 컬렉션 프레임워크는 자료구조를 다루는데 유용한 여러 가지 알고리즘과 검색 기능을 제공합니다.
1-2. 주요 인터페이스와 구현체
1.List
- 순서가 있는 요소들을 중복을 허용하며 저장하는 인터페이스입니다.
- 주요 구현체: ArrayList, LinkedList, Vector 등
2.Set
- 순서가 없는 요소들을 중복 없이 저장하는 인터페이스입니다.
- 주요 구현체: HashSet, TreeSet 등
3.Queue
- FIFO(First-In-First-Out) 또는 우선순위에 따라 요소들을 저장하는 인터페이스입니다.
- 주요 구현체: LinkedList, PriorityQueue 등
4.Map
- 키(Key)-값(Value) 쌍으로 데이터를 저장하는 인터페이스입니다.
- 주요 구현체: HashMap, TreeMap, LinkedHashMap 등
2. Array(배열), List, ArrayList의 차이점
1.Array(배열)
int[] array = new int[5]; // 크기가 5인 정수형 배열 생성- 배열은 동일한 데이터 타입의 요소들을 연속적인 메모리 공간에 저장하는 자료구조입니다.
- 장점
- 인덱스를 이용하여 빠르게 요소에 접근할 수 있습니다.
- 연속된 메모리 공간에 요소들을 저장하므로, 데이터 접근이 빠르고 효율적입니다.
- 고정된 크기로 인해 메모리 할당에 대한 오버헤드가 적습니다.
- 단점
- 크기가 고정되어 있어 추가나 삭제가 어렵습니다.
- 배열의 크기를 변경하려면 새로운 배열을 할당하고 기존 요소들을 복사해야 합니다.
- 크기를 변경하려면 추가적인 작업이 필요하므로, 메모리 낭비가 발생할 수 있습니다.
2.List
List<String> list = new ArrayList<>(); // 크기가 가변적인 문자열 리스트 생성- List는 Java Collection Framework의 인터페이스로, 순서가 있는 데이터 요소들을 저장하는 자료구조입니다.
- 장점
- 동적인 크기를 가지고 있어서 요소를 추가하거나 삭제할 수 있습니다.
- 인덱스를 이용하여 요소에 빠르게 접근할 수 있습니다.
- 배열보다 메모리 관리가 더 유연하며, 크기 변경이 용이합니다.
- 단점
- 순차적인 요소 접근에 대해서는 배열보다 성능이 떨어질 수 있습니다.
- ArrayList 등 일부 List 구현체의 경우 요소 추가/삭제 시 내부 배열의 재할당과 복사가 발생하여 성능 저하가 있을 수 있습니다.
3.ArrayList
ArrayList<Integer> arrayList = new ArrayList<>(); // 크기가 가변적인 정수형 ArrayList 생성- ArrayList는 List 인터페이스를 구현한 클래스 중 하나로, 내부적으로 배열을 사용하여 요소들을 저장하는 자료구조입니다.
- 장점
- 배열 기반이므로 인덱스를 이용하여 빠르게 요소에 접근할 수 있습니다.
- 요소를 추가하거나 삭제하는 작업이 매우 빠르고 편리합니다.
- 크기가 자동으로 조정되므로 메모리 관리에 편리합니다.
- 단점
- 배열 기반이기 때문에 요소를 삽입하거나 삭제할 때 내부 배열의 재할당과 복사가 발생할 수 있습니다.
- 빈번한 추가/삭제 작업이 필요한 경우에는 성능 저하가 발생할 수 있습니다.
3. List
3-1. ArrayList
ArrayList는 Collection 프레임워크의 일부이며 java.util 패키지에 소속되어 있다.
직접 한번 ArrayList 함수들을 구현해 보겠습니다.
MyArrayList
package com.example.datastructure.List;
import java.util.Arrays;
public class MyArrayList<T> implements IList<T> {
private int size;
private T[] elements;
public MyArrayList(){
this.size = 0;
this.elements = (T[]) new Object[50];
}
// 데이터 추가
@Override
public void add(T t){
// 배열 늘리기
if(this.size == this.elements.length){
this.elements = Arrays.copyOf(this.elements, this.size * 2);
}
this.elements[this.size++] = t;
}
// 원하는 위치에 데이터 추가
@Override
public void insert(int index, T t){
// 배열 늘리기
if(this.size == this.elements.length){
this.elements = Arrays.copyOf(this.elements, this.size * 2);
}
// 데이터 한칸씩 뒤로 밀어주기
for(int i = index; i < this.size; i++){
this.elements[i + 1] = this.elements[i];
}
this.elements[index] = t;
this.size++;
}
// 모두 비우기
@Override
public void clear(){
this.size = 0;
this.elements = (T[]) new Object[50];
}
// 원하는 데이터 삭제
@Override
public boolean delete(T t){
for(int i = 0; i < this.size; i++){
if(this.elements[i].equals(t)){
for(int j = i; j< this.size; j++){
this.elements[j] = this.elements[j + 1];
}
this.size--;
return true;
}
}
return false;
}
// 원하는 위치의 데이터 삭제하기
@Override
public boolean deleteByIndex(int index){
// 인덱스가 잘못 들어왔을때 처리
if(index < 0 || index > this.size - 1){
return false;
}
for(int i = index; i < this.size - 1; i++){
this.elements[i] = this.elements[i+1];
}
this.size--;
return true;
}
// 값 가져오기
@Override
public T get(int index){
// 인덱스가 잘못 들어왔을때 처리
if(index < 0 || index > this.size - 1){
throw new IndexOutOfBoundsException();
}
return this.elements[index];
}
// index 값 가져오기
@Override
public int indexOf(T t){
for(int i = 0; i < this.size; i++){
if(this.elements[i].equals(t)){
return i;
}
}
return -1;
}
// 데이터가 있나 없나 확인
@Override
public boolean isEmpty(){
return this.size == 0;
}
// 값을 가지고 있나 확인
@Override
public boolean contains(T t){
for(int i = 0; i < this.size; i++){
if(this.elements[i].equals(t)){
return true;
}
}
return false;
}
// 사이즈 반환
@Override
public int size(){
return this.size;
}
}
추가
삽입
삭제
3-2. LinkedList
Java에서 LinkedList는 List 인터페이스를 구현한 연결 리스트 기반의 자료구조입니다. LinkedList는 java.util 패키지에 속해 있으며, 각 요소가 노드(Node)로 연결되어 순서를 유지하고 요소를 삽입하거나 삭제하는 데에 용이한 자료구조입니다.
특징
1.연결 리스트 구조
LinkedList는 각 요소가 노드로 구성되어 연결 리스트 형태로 데이터를 저장합니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(참조)를 갖고 있으며, 이 포인터를 통해 연결이 이루어집니다.
2.동적 크기 조정
LinkedList는 동적으로 크기를 조정할 수 있어서 요소를 추가하거나 삭제하는 작업이 간편합니다. 노드들은 연결 리스트로 구성되어 있으므로 크기 조정에 대한 배열의 재할당과 복사가 필요하지 않습니다.
3.삽입 삭제에 유리
LinkedList는 특정 위치에 요소를 삽입하거나 삭제하는 작업이 다른 자료구조들보다 효율적입니다. 삽입 또는 삭제 시 해당 위치를 찾는데 O(n)의 시간이 소요되지만, 삽입 또는 삭제 작업 자체는 O(1)의 시간에 이루어집니다.
4.인덱스 기반 접근의 단점
LinkedList는 배열과 달리 인덱스를 통한 요소 접근이 배열보다 느립니다. 특정 인덱스로 바로 접근하기 위해서는 첫 번째 노드부터 해당 인덱스의 노드까지 순차적으로 접근해야 합니다.
MyLinkedList
package com.example.datastructure.List;
public class MyLinkedList<T> implements IList<T>{
private int size;
private Node head;
public MyLinkedList(){
this.size = 0;
this.head = new Node(null); // 더미 헤더 노드
}
@Override
public void add(T t) {
Node curr = this.head;
// 헤드부터 curr Next가 null이 아닐때 까지
while(curr.next != null){
curr = curr.next;
}
// 노드 생성 후 마지막에 추가
Node node = new Node(t);
curr.next = node;
this.size++;
}
@Override
public void insert(int index, T t) {
if(index > this.size || index < 0){
throw new IndexOutOfBoundsException();
}
Node prev = this.head;
Node curr = prev.next;
int i = 0;
while(i++ < index){
prev = prev.next;
curr = curr.next;
}
Node node = new Node(t, curr);
prev.next = node;
this.size++;
}
@Override
public void clear() {
this.size = 0;
this.head.next = null;
}
@Override
public boolean delete(T t) {
Node prev = this.head;
Node curr = prev.next;
while(curr != null){
if(curr.data.equals(t)){
prev.next = curr.next;
curr.next = null;
this.size--;
return true;
}
prev = prev.next;
curr = curr.next;
}
return false;
}
@Override
public boolean deleteByIndex(int index) {
if(index >= this.size || index < 0){
throw new IndexOutOfBoundsException();
}
Node prev = this.head;
Node curr = prev.next;
int i = 0;
while(i++ < index){
prev = prev.next;
curr = curr.next;
}
prev.next = curr.next;
curr.next = null;
this.size--;
return true;
}
@Override
public T get(int index) {
if(index >= this.size || index < 0){
throw new IndexOutOfBoundsException();
}
Node curr = this.head.next;
int i = 0;
while(i++ < index){
curr = curr.next;
}
return curr.data;
}
@Override
public int indexOf(T t) {
Node curr = this.head.next;
int index = 0;
while(curr != null){
if(t.equals(curr.data)){
return index;
}
curr = curr.next;
index++;
}
return -1;
}
@Override
public boolean isEmpty() {
return this.head.next == null;
}
@Override
public boolean contains(T t) {
Node curr = this.head.next;
while(curr != null){
if(t.equals(curr.data)){
return true;
}
curr = curr.next;
}
return false;
}
@Override
public int size() {
return this.size;
}
// LinkedList는 노드 기반이기 때문에
private class Node{
T data;
Node next;
Node(T data){
this.data = data;
}
Node(T data, Node next){
this.data = data;
this.next = next;
}
}
}- 추가의 경우 노드를 하나 추가하고 기존에 마지막 노드에 next에 추가한 노드를 설정해 주면 추가가 됩니다.
- 삭제의 경우 노드의 연결을 끊어주어 주고 그 다음 노드에 연결해주게 되면 연결이 끊긴 노드는 찾을 수 없게 됩니다.
추가
삽입
삭제
4. 문제풀이
백준 11728. 배열 합치기
https://www.acmicpc.net/problem/11728
Baekjoon_11728
package com.example.datastructure.List;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Baekjoon_11728 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 배열 A의 사이즈
int M = sc.nextInt(); // 배열 B의 사이즈
List<Integer> A = new ArrayList<>();
for(int i = 0; i < N; i++){
int n = sc.nextInt();
A.add(n);
}
List<Integer> B = new ArrayList<>();
for(int i = 0; i < M; i++){
int n = sc.nextInt();
B.add(n);
}
List<Integer> result = new ArrayList<>();
int i = 0;
int j = 0;
while(i < N && j < M){
int a = A.get(i);
int b = B.get(j);
if(a <= b) {
result.add(a);
i++;
}else{
result.add(b);
j++;
}
}
for(; i < N; i++){
result.add(A.get(i));
}
for(; j < M; j++){
result.add(B.get(j));
}
StringBuilder sb = new StringBuilder();
for(int e : result){
sb.append(e + " ");
}
System.out.println(sb.toString());
}
}
