List

ArrayList

---

ArrayList는 기본 배열과 비슷한 점이 많지만 배열의 길이를 선언시 정하지 않고 동적으로 요소를 추가, 수정, 삭제가 가능하다는 장점이 있다.

이런 활용이 가능한 이유를 ArrayList 내부 코드를 보면서 찾아보자.

생성자 코드

transient Object[] elementData;


public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
    }
}

    public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

위는 ArrayList의 생성자 내부 코드이다. 코드를 보면 생성자가 받아온 매개변수를 elementData라는 Object 배열에 저장한다. 즉 ArrayList도 결국 배열이라는 의미이다. 하지만 배열이 아닌 척을 할 뿐이다.

add(), get(), remove() 코드

// add()
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    size = s + 1;
}

// remove()
public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

// get()
public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

다음은 요소를 추가, 삭제, 가져오는 메소드들의 내부 코드를 봐도 결국 새로운 값을 저장할 배열을 새로 선언하고 이를 리턴할 뿐이다. 하지만 메소드 내부에서 작동하기 때문에 메소드를 사용하는 개발자 입장에선 편리함을 제공받을 뿐이다.

LinkedList

---

LinkedList는 ArrayList와는 다르게 각 요소들은 앞과 뒤에 위치한 요소의 존재만을 인지하고 있는다고 한다.

이를 자바에선 어떻게 구현했는지 코드를 보자.

생성자 코드

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

    transient Node<E> last;
}

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;
    }
}

코드를 보면 LinkedList는 내부적으로 Node 클래스로 각각의 요소를 저장하고 first와 last의 이름으로 요소를 연결하는 구조를 가진다.

add(), remove() 코드

// add()
public boolean offer(E e) {
    return add(e);
}

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

// remove()
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

LinkedList의 add(), remove() 메소드도 코드를 살펴보면 요소가 추가 및 삭제될 때마다 first와 last 변수에 담긴 Node 객체를 바꿔주거나 새로 생성하는 형태로 구현되어 있다.

즉 인덱스가 아닌 요소의 앞, 뒤 요소를 저장해두기만 하는 것을 의미한다.

침고 사이트 : ArrayList

침고 사이트 : LinkedList