Collection Framework - List

List Interface

가장 많이 쓰이는 Collection Framework중에 하나이다. 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용된다. List인터페이스를 구현한 클래스로는 ArrayList, LinkedList, Vector, Stack등이 있다. 기본적으로 내부에서 어떤 자료구조가 Collection 데이터를 보관 관리하느냐에 따라서 클래스명을 결정한다.

예를들어 ArrayList는 데이터를 배열(Array)에 저장하고, LinkedList는 next Element와 prev Element를 저장하는 Linked Node로 구성된 자료구조 형태에 데이터를 저장한다.

List Interface의 메소드는 아래와 같다. 물론 Collection Interface의 내용은 모두 갖고 있다.

Method	설명
void add(int index, Object element)	지정된 위치(index)에 객체(element)를 추가.
boolean addAll(int index, Collection c)	지정된 위치(index)에 Collection(c)에 포함 된 객체를 추가.
Object get(int index)	지정된 위치(index)에 있는 객체를 반환.
int indexOf(Object o)	지정된 객체의 위치(index)를 반환.  (List의 첫 번째 요소부터 순방향으로 찾는다.)
int lastIndexOf(Object o)	지정된 객체의 위치(index)를 반환.  (List의 마지막 요소부터 역방향으로 찾는다.)
ListIterator listIterator()	List의 객체에 접근할 수 있는 ListIterator를 반환.
ListIterator listIterator(int index)	지정된 index위치 부터 이후에 있는 객체 List의 객체에 접근할 수 있는 ListIterator를 반환.
Object remove(int index)	지정된 index위치의 객체를 삭제하고 삭제된 객체를 리턴.
Object set(int index, Object element)	지정된 위치(index)에 객체(element)를 저장.
List subList(int fromIndex, int toIndex)	지정된 범위(fromIndex~toIndex)까지에 있는 객체를 List로 반환.

ArrayList

장점 : 간단하면서 사용하기 쉽고 데이터에 접근 시간이 가장 빠르다.

단점 : 배열은 크기 변경이 불가능하기 때문에 새로운 배열을 생성하여 데이터를 복사하는 작업이 내부적으로 수행되어 비용증가. 데이터 중간 위치에 추가/삭제가 발생하는 경우 deecopy가 발생하여 처리비용 발생.

Constructor와 Capacity

ArrayList를 생성할 때 capacity를 지정하여 생상하는 경우 Array는 입력된 capacity의 크기 만큼의 배열로 생성된다. 다들 아시다 싶이 배열은 유동적으로 공간을 늘이는 것이 불가능하다. 그래서 capacity를 지정하지 않고 생성되는 배열은 0의 크기로 생성되고 객체가 add될 때 배열을 ArrayList.DEFAULT_CAPACITY의 크기인 10만큼의 배열을 생성하게 된다. 객체가 10개 이상 추가되는 경우는 20개의 길이를 갖는 배열을 생성하여 기존의 데이터를 deep copy하게 된다. 때문에 초기 생성시 적절한 capacity를 주면 불필요한 배열 할당 및 deep copy의 처리 시간을 아낄 수 있다.

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

add(E element)와 add(int index, E element)

ArrayList의 경우 배열을 기반으로 하기 때문에 마지막 요소에 데이터를 추가하는 add(E element) 메소드의 경우는 위에서 설명한 capacity를 초과하지 않는다면 별다른 연산이나 처리를 수행하지 않고 데이터가 추가된다. 하지만, add(int index, E element)의 경우는 배열 중간에 객체가 추가된다. 실제로 추가되는 과정은 아래 소스와 같다. capacity검사->arraycopy->array[index]데이터 할당. arraycopy가 발생하기 때문에 내부적으로 처리시간이 오래 걸리게 된다. remove(index)의 경우도 마찬가지 이다.

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

LinkedList

장점 : ArrayList보다 중간요소에 추가/삭제가 빠르다.

단점 : ArrayList가 데이터 접근 속도는 훨씬 빠르며, 순차적(역방향도 역시) 데이터 추가삭제의 경우는 ArrayList가 훨씬 빠르다. (단, capacity가 충분하다는 가정)

ArrayList는 위에 설명처럼 배열(Array)가 갖는 특성인 크기를 변경할 수 없다는 특성 때문에 데이터 추가/삭제에 많은 비용이 발생함을 알 수 있다. 이를 해결하기 위해서 LinkedList가 고안되었다. LinkedList는 불연속적으로 존재하는 데이터를 서로 연결한 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;
        }
    }

위 소스코드 처럼 각 개별 Node는 Next와 Prev노드의 레퍼런스를 갖고 있어 다음과 이전 값에 접근한다. 만약 객체가 추가 삭제되는 경우 현재 Position에 객체에  next의 참조만 변경하여 주면 된다. 마찬가지로 삭제되는 경우도 삭제 된 위치에 이전이 노드의 next와 이후 노드의 prev를 변경해주는 것으로 작업이 완료된다.

또한 새로운 노드가 추가되는 경우도 capacity라는 개념이 없고 last Node에 새로운 노드를 생성하여 서로 연결시켜주는 것으로 모든 작업이 완료 된다.

Stack and Queue

Stack : LIFO(Last In First Out) 후입선출의 자료구조로 마지막으로 입력 된 데이터를 가장 먼저 내보낸다.

Queue : FILO(First In Last Out) 선입선출의 자료구조로 처음입력 된 데이터를 가장 먼저 내보낸다.

Stack과 Queue는 List의 상속구조에서 List와 연관되어 여기 포함시켰다. 후입선출의 구조인 Stack의 경우 ArrayList연관된다. 왜냐하면 배열구조로 되어 있는 ArrayList가 마지막에 입력된 데이터 접근성이 좋으며 마지막에 있는 데이터를 추가/삭제하여도 비용이 적게 들기 때문이다.

(Vector를 상속받아 구현)

반대로 Queue는 LinkedList와 관련되어 있다. 선입선출 구조의 자료구조이기 때문에 처음 입력된 값을 가장먼저 내보내야 한다. 배열로 구현한다면 첫 번째 요소가 매번 삭제되기 때문에 ArrayCopy를 수행해야 하기 때문에 비용이크다. 그래서 중간요소를 쉽게 추가/삭제할 수 있는 LinkedList와 연관되어 있다.

(LinkedList가 Queue, Deque를 구현)

Summary

Class	구현	입력순서	중복가능	접근속도	추가/삭제 속도
ArrayList	Array	보장	가능	빠름	순차인 경우 빠름  중간위치 느림
LinkedList	Node	보장	가능	느림	순차인 경우 느림  중간위치 빠름
Stack	Vector 상속	후입선출의 자료구조로 Vector를 상속받아 구현.
Queue	LinkedList가 Queue구현	선입선출의 자료구조로 LinkedList가 Qeueue를 구현하고 있음.

관련글 보기

Collection Framework

List Interface : ArrayList, LinkedList, Stack and Queue

Set Interface : HashSet, LinkedHashSet, TreeSet, Comparable, Comparator

Map Interface : HashMap, LinkedHashMap, TreeMap

출처: http://javaslave.tistory.com/123?category=534252 [전산쟁이]