[자료구조] 코드로 알아보는 java의 LinkedList

Java에서 List를 구현하는 구현체는 대표적으로 ArrayList, LinkedList, Vector가 있습니다. 저희는 저번 포스팅에서 ArrayList에 대해서 코드를 보며 내부 구조와 실질적인 시간복잡도를 파악해 보았습니다. 오늘은 LinkedList에 대해서 코드를 보며 ArrayList와는 어떻게 다른지 그 구조와 시간복잡도를 파악해보도록 하겠습니다.

ArrayList와 LinkedList

arraylist 구조

우리가 일반적으로 알고 있는 ArrayList의 이미지는 위와 같습니다. String 형태의 "Hello Wo" char 배열에 저장한다고 하면 위와같은 형태가 될 것입니다. index를 가지고 있으며 index에 값을 저장하고 있는 형태입니다. 이런형태를 가짐으로써 RandomAccess가 가능하고 군집해 있기때문에 메모리적으로도 이득인부분을 가진다고 알고 있습니다.

linkedlist 구조

위의 그림은 String 형태의 "Hello Wo"를 LinkedList의 자료구조에 저장했을 때 나타나는 형태입니다. 각 Node들은 이전 Node를 가리키는 P, 다음 Node를 가리키는 N, 가지고 있는 값을 가지고 있습니다. ArrayList와는 달리 N과 P의 가리키는 Node를 변경함으로 써 삽입과 삭제를 하며 재정렬이 필요없기 때문에 ArrayList에 비해 상대적으로 삽입과 삭제가 빠르다고 합니다. 또한 ArrayList는 고정크기이며 add에서 크기의 재산정이 필요하지만 LinkedList는 재산정이 필요없습니다.

그럼 이제 실제 구현되어있는 코드로 확인해보도록 하겠습니다.

interface와 내부 변수

/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
*            (first.prev == null && first.item != null)
*/
transient Node<E> first;

/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
*            (last.next == null && last.item != null)
*/
transient Node<E> last;

LinkedList의 내부변수로는 firstNode와 lastNode의 값이 들어있습니다. 위의 예제를 들면 첫번째 H와 마지막 O의 값이 들어있다고 할 수 있습니다. 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;
    }
}

item은 Node에 들어있는 값, next는 다음 node, prev는 이전 node를 값을 가지고 있다는것을 알 수 있습니다.

생성자

/**
* Constructs an empty list.
*/
public LinkedList() {
}

생성자는 위와 같습니다. 우리가 List<String> list = new LinkedList<>(); 라고 Client에서 선언하면 이런 default 빈 생성자를 호출하게 되며 인스턴트가 생성됩니다.

add

/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
    linkLast(e);
    return true;
}

기본적으로 사용하는 add입니다. 내부 메서드를 보니 #addLast와 동일한 메서드라고 입니다. 마지막에 Node를 추가하는 메서드라는것을 알 수 있습니다.

/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
*/
public void addLast(E e) {
    linkLast(e);
}

#addLast 메서드도 똑같은 #linkLast 메서드를 호출하는 것을 알 수 있습니다.

/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}

제일 처음 앞에 추가하는 #addFirst도 있습니다.

/**
    * Links e as last element.
    */
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++;
}

#linkLast는 마지막 Node 뒤에 실제 Node를 추가하는 메서드입니다. 새로운 노드를 생성하면서 prev는 last Node, next는 null로 생성합니다. 그리고 기존의 last Node의 Next는 새로 생성한 Node를 바라보게 합니다. 그리고 last를 새로만든 Node로 만듭니다. 이렇게 마지막 Node에 추가하는것으로 마무리 됩니다.

/**
* Links e as first element.
*/
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

#linkLast는 마지막에 node로 추가하는 것이라면 #linkFirst는 Node의 제일 앞에 추가하는 것입니다. 내부 로직은 linkLast와 동일합니다.

그렇다면 중간에 삽입하는건 어떨까요?

/**
* 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) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

중간에 값을 삽입하기 위해서 index의 값의 범위를 확인하고 그 index가 size와 같다면 위에서 살펴봤던 linkLast 메서드로 마지막에 insert하며 그게 아니라면 linkBefore 메서드를 이용하여 insert합니다. 보도록 하겠습니다.

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

index가 정상인지에 대한 여부는 0 ~ size 사이의 값인지 판단합니다. 아니라면 IndexOutOfBoundsException을 발생시킵니다.

/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

node 메서드를 이용하여 index를 기준으로 node를 찾습니다. index가 size의 50% 이상이라면 last를 기준으로 찾고 50% 미만이라면 first를 기준으로 찾습니다.

/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

index가 마지막이 아니라면 linkBefore 메서드를 호출합니다. 삽입할 값과 #node 메서드를 통해 찾은 Node를 이용하여 연결합니다. 새로운 Node를 생성하며 찾은 Node는 next가 되고 찾은 Node의 전 Node는 before가 됩니다. 그리고 각각 서로 연결해주고 size를 올리며 노드의 생성이 마무리 됩니다.

• linkedList의 삽입은 제일 앞 또는 제일 뒤에 진행할 경우 O(1)의 시간복잡도를 가지는것을 알았습니다. 하지만 중간에 삽입할때는 삽입시간 O(1)과는 별도로 index를 찾아내는데 n/2의 시간 시간복잡도로는 O(n)이 별도로 추가된다는 것을 알 수 있었습니다.

remove

그렇다면 삭제에 대해서 알아보도록 하겠습니다. 삭제 또한 삽입과 마찬가지로 처음 / 마지막 / 중간으로 나누어 확인해보도록하겠습니다.

/**
* Retrieves and removes the head (first element) of this list.
*
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
public E remove() {
    return removeFirst();
}

기본 삭제 메서드인 #remove입니다. 해당 메서드는 #pop 메서드와 코드레벨도 동일합니다.

/**
* Removes and returns the first element from this list.
*
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

#removeFirst와 #removeLast에서는 삭제할 노드를 선택 각각 #unlinkFirst, #unlinkLast 메서드를 호출합니다.

/**
* Unlinks non-null last node l.
*/
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

삭제할 node와 이전 Node를 이용하여
unlink시에는 양쪽의 link를 모두 null처리해주어야 합니다. 그렇지 않으면 참조되고있는 메모리 영역으로 판단하여 GC가 삭제하지 못하기 때문입니다. #unlinkFirst 메소드도 동일한 로직으로 앞의 Node를 제거합니다.

/**
     * Removes the element at the specified position in this list.  Shifts any
     * subsequent elements to the left (subtracts one from their indices).
     * Returns the element that was removed from the list.
     *
     * @param index the index of the element to be removed
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

index를 기준으로 삭제하는 메서드입니다. 먼저 정상적인 범위의 index인지 판단한 후 #node 메서드를 이용하여 index에 해당하는 Node가 어떤건지 가져옵니다. 해당 메서드들은 add시 사용했던 메서드와 동일합니다.

/**
     * Unlinks non-null node x.
     */
    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;
    }

unlink는 unlinkLast 메서드와 unlinkFirst 메서드를 합친 것과 같습니다. 본인의 Node를 기준으로 prev에 있는 Node와 next에 있는 node를 가져와 둘을 이어주고 본인은
null로 GC를 기다리는 것입니다.

• remove역시 add와 마찬가지로 맨앞, 맨뒤는 O(1)의 시간복잡도를 보이는 것을 알 수 있었습니다. 그리고 중간에 있는 index를 기준으로 삭제하는 경우에는 add와 마찬가지로 node가 어디에 존재하는지 찾는데 O(n)의 시간이 걸리는 것을 알 수 있습니다.

마무리

오늘은 이렇게 LinkedList에 대해서 코드로 알아봤습니다.

도움이 되셨다면 하트와 아랫 광고 한번 클릭 부탁드려요 !

감사합니다.

참조

https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html