[자바의 정석] Chapter 11. 컬렉션 프레임워크 - List

1권에서 습득한 객체지향 관점 놓치지 않기!

---

 

컬렉션 프레임워크

컬렉션 프레임워크는 다수의 데이터(컬렉션)를 다루는데 필요한 다양하고 풍부한 클래스들을 제공한다. 또한 인터페이스와 다형성을 이용한 객체지향적 설계를 통해 표준화되어 있기 때문에 재사용성이 높은 코드를 작성할 수 있도록 해준다.

 

컬렉션 프레임워크의 핵심 인터페이스

컬렉션 프레임워크에서는 컬렉션(데이터 그룹)을 크게 3가지 타입이 존재한다고 인식하고 각 컬렉션을 다루는데 필요한 기능을 가진 3개의 인터페이스를 정의하였다.

이때 List 인터페이스와 Set 인터페이스는 공통부분이 많아 해당 공통부분을 다시 뽑아 Collection 인터페이스를 정의하였다.
하지만 Set 인터페이스의 경우 공통되는 부분이 아예 없어 따로 떨어져 있다.

 

 

이 3가지 인터페이스의 특징과 종류는 절대 잊지 말아야 한다...

 

1. List

1-1. ArrayList

ArrayList는 컬렉션 프레임워크에서 가장 많이 사용되는 컬렉션 클래스일 것이다.

• 저장 순서가 유지된다.
• 중복을 허용한다.

만약 배열에 더 이상 저장할 공간이 없으면 더 큰 새로운 배열을 생성하여 기존의 배열에 저장된 내용을 새로운 배열로 복사하여 저장한다.
그리고 ArrayList의 경우 한 요소가 삭제될 때마다 빈 공간을 채우기 위해 나머지 요소들이 자리이동을 한다. 그렇기 때문에 여러 요소를 삭제할 일이 있으면 가장 뒤에 있는 요소부터 삭제하는 것이 좋다.

ArrayList나 Vector 같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장하는 데 있어서 효율이 좋지만, 용량을 변경해야 할 때는 새로운 배열을 생성한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사한다.
Why? 메모리 단편화 때문에

 

ArrayList와 Vector의 메모리 단편화

자바의 정석을 보는데 ArrayList와 Vector의 용량을 늘릴 때마다 계속 새로운 배열을 만들어 참조하고 있었다.
처음에 이 부분을 보고 정말 괴로웠다...
왜 새로운 배열을 할당하는 거지? 왜지? 그럴 거면 얘네를 왜 쓰는 거지? 그냥 기존 배열을 늘리면 안 되나? 당연히 안된다..
애초에 얘네는 배열이라 늘릴 수 없다. 무조건 새로 선언해야 한다.
심지어 메모리 공간을 재할당을 하기 때문에 외부 단편화까지 발생시키며, size와 capacity가 괴리감이 느껴질 정도로 차이가 나면 내부 단편화까지 걱정해야 한다.

 

하지만 그럼에도 불구하고 ArrayList와 Vector를 쓰는 이유는 데이터를 읽고 (순차적으로) 저장하는 것이 매우 효율적이기 때문이다.

용량을 줄이고 늘리거나, 비순차적으로 요소를 추가하거나, 중간 요소를 삭제할 일이 많은 경우 바로 밑에 정리할 LinkedList를 사용하자...

 

1-2. LinkedList

위에서 알아본 ArrayList의 단점은

1. 크기를 변경할 수 없다. (배열의 지독한 숙명)
   • 때문에 크기를 변경하고 싶으면 새로운 배열을 선언해서 복사해야 한다.
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
   • 차례대로 데이터를 추가하고 마지막부터 데이터를 삭제하는 것은 빠르지만, 이 외의 모든 추가 및 삭제는 비효율적임

이러한 배열의 단점을 보완하기 위해서 등장한 자료구조가 링크드 리스트(Linked list)이다.

 

 

배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있다.

어떻게 연결하냐면 다음 요소의 주소와 자신의 데이터를 저장하는 노드를 통해 연결되어 있다.

 

class Node {
    Node next;        // 다음 요소의 주소를 저장
    Object obj;        // 데이터를 저장
}

 

삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다.
때문에 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다.

 

 

이처럼 다음 요소의 주소만 바꿔주면 매우 빠르게 중간 요소를 삭제할 수 있다. (추가도 마찬가지)

 

더블 링크드리스트

 

링크드 리스트의 단점은 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다.
이 점을 보완하기 위해 나온 것이 더블 링크드리스트(이중 연결리스트)이다.

 

class Node {
    Node next;        // 다음 요소의 주소를 저장
    Node previous;        // 이전 요소의 주소를 저장
    Object obj;        // 데이터를 저장
}

 

여기서 0x200의 null에 0x380을 넣어주고, 0x380의 null에 0x200을 넣어주면 더블 써큘러 링크드리스트(이중 원형 연결리스트)가 된다.

 

 

결론

1. 순차적으로 추가/삭제하는 경우에는 ArrayList가 빠르다.
2. 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 빠르다.

 

1-3. Stack과 Queue

• Stack : 마지막에 저장한 데이터를 가장 먼저 꺼낸다. (LIFO)
• Queue : 처음에 저장한 데이터를 가장 먼저 꺼낸다. (FIFO)

스택은 순차적으로 데이터를 추가하고 삭제하기 때문에 ArrayList 같은 배열 기반의 컬렉션 클래스가 적합하고,
큐는 데이터를 꺼낼 때 항상 첫 번째에 저장된 데이터를 삭제하므로 추가/삭제가 쉬운 LinkedList로 구현하는 것이 적합하다.

 

PriorityQueue

Qeue 인터페이스의 구현체 중 하나로, 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내는 큐이다. (null은 저장할 수 없다.)

• 저장공간으로 "배열"을 사용
• 각 요소를 "힙"이라는 자료구조 형태로 저장
  • 때문에 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다.

 

Deque

Queue의 변형으로, 한쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리, Deque은 양쪽 끝에 추가/삭제가 가능하다.

 

1-4. Iterator, ListIterator

이 두 개는 컬렉션에 저장된 요소에 접근하는 데 사용되는 인터페이스이다.

컬렉션에 저장된 각 요소에 접근하는 기능을 가진 Iterator 인터페이스를 정의하고 컬렉션 인터페이스에는 Iterator를 반환하는 iterator()을 정의하고 있다.

List list = new ArrayList();

Iterator it = list.iterator();

while(it.hasNext()) {
    System.out.println(it.next());
}

Map 인터페이스를 구현한 컬렉션은 키와 값을 쌍으로 저장하고 있기 때문에 keySet()과 entrySet()을 통해 iterator()를 호출한다. 해당 코드가 아래의 코드이다.

Map map = new HashMap();
Iterator it = map.keySet().iterator();

Set eSet = map.entrySet();
Iterator it = eSet.iterator();

ListIterator는 Iterator를 상속받아서 기능을 추가한 것으로, 컬렉션의 요소에 접근할 때 Iterator는 단방향으로만 이동할 수 있는데 반해 ListIterator는 양방향으로의 이동이 가능하다. 단, List를 구현한 경우에만 사용이 가능하기 때문에 주의해야 한다.

 

1-5. Arrays

Arrays 클래스에는 배열을 다루는데 유용한 메서드가 정의되어 있다.

 

배열의 복사 - copyOf(), copyOfRange()

copyOf()는 배열 전체를, copyOfRange()는 배열의 일부를 복사해서 새로운 배열을 만들어 반환한다.

int[] arr = {0,1,2,3,4};

int[] arr2 = Arrays.copyOf(arr, arr.length);
int[] arr3 = Arrays.copyOf(arr, 3);
int[] arr4 = Arrays.copyOf(arr, 7); 
int[] arr5 = Arrays.copyOfRange(arr, 2, 4);
int[] arr6 = Arrays.copyOfRange(arr, 0, 7);

 

배열을 List로 변환 - asList(Object... a)

asList()는 배열을 List에 담아서 반환한다.
단, asList()를 통해 만들어진 리스트는 크기 변경이 불가능하다.

List list = Arrays.asList(new Integer[]{1,2,3,4,5});    
List list = Arrays.asList(1,2,3,4,5);    // list = [1,2,3,4,5]
list.add(6);

만약 크기를 변경하고 싶다면 아래의 코드로 작성하면 된다.

List list = new ArrayList(Arrays.asList(1,2,3,4,5));