11. 컬렉션 프레임웍

컬렉션 프레임웍이란, '데이터 군(群)을 저장하는 클래스들을 표준화한 설계'를 뜻한다. 즉 데이터 그룹(collection)을 표준화한 프로그래밍 방식이다.
JDK1.2부터 컬렉션 프레임웍이 등장하면서 모든 컬렉션 클랙스를 표준화된 방식으로 다룰 수 있도록 체계화 되었다.

public interface Collection<E>
extends Iterable<E>

• 컬렉션 프레임웍의 장점
  1. collection(다수의 데이터)을 다루는데 다양한 클래스를 제공
  2. 인터페이스와 다형성을 이용하여 표준화
  3. 사용하기 편리
  4. 재사용성 높은 코드 작성

라이브러리와 프레임웍

• 라이브러리: 공통으로 사용될만한 유용한 기능을 모듈화하여 제공
  • 개발을 위한 도구
• 프레임웍: 기능뿐만 아니라 프로그래밍 방식을 정형화
  • 복잡한 문제를 해결하거나 서술하는 데 사용되는 기본 개념 구조
    참고: https://webclub.tistory.com/458

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

컬렉션 데이터 그룹을 3가지로 나누고, 각 컬렉션을 다루기 위한 3개의 인터페이스 정의

• List: 순서가 있는 데이터의 집합, 중복 허용
• Set: 순서가 없는 데이터의 집합, 중복 허용하지 않음
• Map: key-value로 이루어진 데이터의 집합. 키는 중복 허용되지 않음.

Collection interface

참고: https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html
데이터를 읽고, 추가하고, 삭제하는 등 컬렉션을 다루는데 가장 기본적인 메서드를 정의

List interface

• 순서가 있는 컬렉션. integr 인덱스를 통해 각 element에 접근이 가능하다.
• set과 다르게 중복을 허용한다.

Set interface

• 저장순서가 유지되지 않음
• 중복을 허용하지 않는다

Map interface

• key-value 쌍을 저장하는 컬렉션 클래스
• key는 중복될 수 없지만 value는 중복을 허용한다

Map map = new HashMap();

// value의 중복은 허용한다
map.put("key", "value");
map.put("key2", "value");
System.out.println(map.get("key"));        // value
System.out.println(map.get("key2"));    // value

// key의 중복은 허용하지 않는다.
// 새로운 value로 대채
map.put("key", "value");
System.out.println(map.get("key"));        // value

map.put("key", "value2");
System.out.println(map.get("key"));        // value2

ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final int DEFAULT_CAPACITY = 10;

    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

    ...
}

Object 배열을 이용해서 데이터를 순차적으로 저장한다.
실제로 크기를 변경할 수 없다. 배열에 더 이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존 배열을 새로운 배열로 복사하여 저장한다. 이 과정에서 메모리가 낭비된다.

특징

• add 등 메소드를 수행하면 O(n)이 소요된다.
  • 중간에 데이터를 추가하면 다른 데이터들을 복사해서 이동해야 한다.
• 모든 ArrayList 인스턴스는 리스트에 저장될 수 있는 사이즈인 _capacity_를 가지며 최대 사이즈는 리스트 사이즈이다.
• synchronized하지 않다.

LinkedList

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable
{
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;

    ...
}

배열의 단점을 보완. 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있다. 링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.

// LinkedList 내부에 구현되어 있는 Node class
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Stack and Queue

Stack

• 마지막에 저장한 데이터를 가장 먼저 꺼낸다
• 순차적으로 데이터를 추가/삭제하기 때문에 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합

Queue

• 처음에 저장한 데이터를 가장 먼저 꺼낸다
• 데이터를 꺼낼 때 첫 번째 데이터를 삭제하므로, LinkedList가 적합

Iterator

Iterator, ListIterator, Enumeration 모두 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스

public interface Iterator<E>

public interface Collection<E>
extends Iterable<E>