LinkedList 상세 분석

LinkedList 역시 Java 컬렉션 프레임워크에서 매우 흔한 List 구현이지만, ArrayList와는 접근 방식이 완전히 다릅니다. ArrayList의 핵심은 동적 배열이고, LinkedList의 핵심은 연결 리스트입니다. ArrayList를 연속 번호가 붙은 칸이라고 보면, LinkedList는 각 노드가 자기 값과 앞뒤 노드를 기억하는 노드 체인에 가깝습니다.

클래스 전체 구조

소스 코드 관점에서 LinkedList는 대략 다음과 같습니다.

Java

        public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, Serializable

여기서 중요한 정보는 두 가지입니다.

단순한 List가 아니다
Deque도 구현하므로, 양방향 큐 연산을 기본적으로 지원합니다.
AbstractSequentialList 를 상속한다
이름 그대로 순차 접근에 유리하고, 랜덤 접근에는 유리하지 않은 구조입니다.

이 점은 ArrayList와 크게 다릅니다. ArrayList는 랜덤 접근에 더 가깝고, LinkedList는 순차 구조 조작에 더 가깝습니다.

내부 핵심 필드

LinkedList에서 가장 중요한 필드는 보통 다음 세 가지입니다.

Java

        transient int size = 0;
transient Node<E> first;
transient Node<E> last;

의미는 다음과 같습니다.

size
현재 리스트에 들어 있는 요소 개수
first
머리(head) 노드를 가리킴
last
꼬리(tail) 노드를 가리킴

연결 리스트를 null <- A <-> B <-> C -> null 로 보면,

first는 A를 가리킴
last는 C를 가리킴
size는 3

이 세 필드가 LinkedList의 대부분 동작을 결정합니다.

Node란 무엇인가

LinkedList의 실제 저장 단위는 요소 자체가 아니라 Node 입니다.

소스 아이디어는 대략 다음과 같습니다.

Java

        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
현재 노드의 값
next
다음 노드 참조
prev
이전 노드 참조

이것이 이중 연결 리스트의 본질입니다. 예를 들어 A <-> B <-> C 에서 B는 다음과 같습니다.

B.prev = A
B.item 은 B의 값
B.next = C

따라서 LinkedList 데이터는 연속 메모리에 놓이지 않고, 참조로 연결됩니다.

왜 이중 연결 리스트인가

각 노드가 이전 노드와 다음 노드를 모두 알기 때문입니다.

직접적인 장점은 두 가지입니다.

머리에서 뒤로 탐색 가능
꼬리에서 앞으로 탐색 가능

그래서 LinkedList 소스에서 index를 찾을 때 항상 머리부터 시작하지 않고, 위치에 따라 first 또는 last에서 출발합니다.

빈 리스트 상태

리스트가 비어 있을 때:

size = 0
first = null
last = null

이 상태는 매우 중요합니다. 삽입/삭제 로직이 보통 두 가지로 나뉘기 때문입니다.

원래 비어 있었는지
원래 비어 있지 않았는지

소스 코드의 많은 분기 조건이 이 상태를 기준으로 작성됩니다.

머리 삽입 linkFirst

머리 삽입은 LinkedList의 대표 로직입니다.

Java

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

순서대로 보면:

기존 머리 f 를 저장
새 노드 newNode 생성
새 노드의 prev 는 새 머리가 되므로 null
새 노드의 next 는 기존 머리 f
first 를 새 노드로 변경
원래 비어 있었다면
기존 머리 f 가 null 이므로 last 도 새 노드를 가리켜야 함
원래 비어 있지 않았다면
기존 머리의 prev 를 새 노드로 설정
size 증가
modCount 증가

핵심은 머리 삽입 시 다른 요소를 옮길 필요가 없고, 참조 몇 개만 바꾸면 된다는 점입니다.

꼬리 삽입 linkLast

꼬리 삽입은 대칭 구조입니다.

Java

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

로직은 다음과 같습니다.

기존 꼬리 l 저장
새 노드의 prev 는 기존 꼬리
새 노드의 next 는 꼬리이므로 null
last 업데이트
원래 비어 있었으면 first 도 새 노드를 가리킴
아니면 기존 꼬리의 next 를 새 노드로 연결
size, modCount 업데이트

그래서 LinkedList는 꼬리 삽입도 자연스럽습니다.

중간 삽입 linkBefore

머리/꼬리가 아닌, 특정 노드 앞에 삽입할 때의 로직은 다음과 같습니다.

Java

        void linkBefore(E e, Node<E> succ) {
        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++;
}

핵심은 succ 입니다. 즉 "누구 앞에 삽입할 것인가"를 나타내는 후속 노드입니다.

기존이 A <-> B <-> C 이고 B 앞에 X를 넣으면:

succ 는 B
pred 는 A
X의 prev = A
X의 next = B
A.next 를 X로 변경
B.prev 를 X로 변경

결과는 A <-> X <-> B <-> C 가 됩니다.

실제로 바뀌는 것은 참조 몇 개뿐입니다.

노드 삭제 unlink

삭제도 연결 리스트의 핵심입니다. 이미 알고 있는 노드 x를 삭제할 때는 보통 다음과 같습니다.

Java

        E unlink(Node<E> x) {
        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;
}

이 메서드는 반드시 이해해 두는 것이 좋습니다.

A <-> B <-> C 에서 가운데 B를 삭제하면 A <-> C 가 되어야 합니다.

소스가 하는 일은:

B의 prev 인 A를 찾고
B의 next 인 C를 찾은 뒤
A.next = C
C.prev = A

이렇게 B를 체인에서 분리합니다.

그리고 다음 처리도 중요합니다.

x.prev = null
x.next = null
x.item = null

주요 목적은 GC가 더 빨리 회수할 수 있도록 불필요한 참조를 제거하는 것입니다.

이미 찾은 노드 삭제가 빠른 이유

ArrayList처럼 전체 요소 이동이 필요 없기 때문입니다.

배열에서 삭제하면 뒤 요소를 앞으로 당겨야 합니다. 연결 리스트는 앞뒤 노드를 다시 연결하면 끝납니다.

그래서 삭제 대상 노드를 이미 가지고 있다면, 삭제 자체는 O(1) 입니다.

다만 매우 중요한 전제가 있습니다. 그 노드를 먼저 찾아야 합니다.

remove(index) 라면 삭제 전에 index 노드를 찾는 과정이 필요하고, 이 탐색은 보통 O(n) 입니다.

따라서 소스 관점에서 정확히 말하면:

노드 연결 해제는 O(1)
노드 탐색은 보통 O(n)
인덱스 기반 삭제 전체는 O(n)

인덱스 접근이 느린 이유

LinkedList의 핵심 메서드인 node(index) 를 보면 이해됩니다.

Java

        Node<E> node(int 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;
        }
}

의미는 다음과 같습니다.

index 가 앞 절반이면
머리에서 뒤로 탐색
index 가 뒤 절반이면
꼬리에서 앞으로 탐색

예를 들어 size = 100, index = 80 이면 first 에서 80칸 가지 않고, last 에서 역방향으로 약 19칸 이동합니다.

이것은 최적화일 뿐, 본질은 바뀌지 않습니다. 여전히 선형 탐색이며 배열의 O(1) 직접 접근이 아닙니다.

따라서 get(index), set(index), add(index, e), remove(index) 는 모두 node(index) 의 영향을 받습니다.

get, set, add, remove의 본질

자주 쓰는 메서드는 같은 패턴으로 이해할 수 있습니다.

get(index)

Java

        public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
}

인덱스를 검사하고 node(index) 로 노드를 찾은 뒤 item 을 반환합니다. 병목은 node(index) 입니다.

set(index, element)

Java

        public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
}

수정 자체는 빠르지만 노드 탐색이 느려서 전체는 O(n) 입니다.

add(index, element)

Java

        public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
        linkLast(element);
        else
        linkBefore(element, node(index));
}

끝에 추가면 linkLast, 그 외에는 node(index) 후 linkBefore 입니다.

remove(index)

Java

        public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

먼저 노드를 찾고, 그다음 연결을 끊습니다.

즉 인덱스 기반 연산의 병목은 "수정 동작"이 아니라 "노드 찾기"입니다.

왜 LinkedList는 랜덤 접근에 부적합한가

소스 관점에서 이유는 명확합니다.

배열처럼 인덱스로 바로 찾아가는 능력이 없다 next 또는 prev 를 한 칸씩 따라가야 한다 get(index) 때마다 머리/꼬리에서 다시 찾을 수 있다

그래서 다음 코드:

Java

        for (int i = 0; i < list.size(); i++) {
        list.get(i);
}

ArrayList에서는 보통 문제 없지만, LinkedList에서는 각 get(i) 가 탐색을 수행해 전체가 O(n^2) 에 가까워질 수 있습니다.

LinkedList 순회는 다음을 권장합니다.

for-each
Iterator
머리부터 꼬리까지 순차 순회

인덱스 반복 조회는 피하는 편이 좋습니다.

Deque가 자연스럽게 맞는 이유

LinkedList는 Deque 를 구현하며, 구조 특성과 잘 맞습니다.

예를 들면:

addFirst
본질적으로 linkFirst
addLast
본질적으로 linkLast
removeFirst
본질적으로 first 삭제
removeLast
본질적으로 last 삭제
peekFirst
first.item 반환
peekLast
last.item 반환

머리와 꼬리를 항상 유지하므로 양방향 큐로 사용하기 매우 편합니다.

이것이 LinkedList 소스 설계의 대표 가치 중 하나입니다. 단순히 List일 뿐 아니라 Deque로도 매우 적합합니다.

Iterator가 순차 순회를 할 수 있는 이유

LinkedList 내부에는 ListItr 같은 이터레이터 구현이 있습니다. 보통 다음 상태를 유지합니다.

next
다음에 반환할 노드
lastReturned
직전에 반환한 노드
nextIndex
현재 반복 위치
expectedModCount
이터레이터 생성 시점의 수정 버전

next() 의 본질은 다음입니다.

동시 수정 여부 확인 현재 노드 값 반환 포인터를 다음 노드로 이동

연결 리스트 자체가 순서대로 연결되어 있으므로, 이터레이터는 next 를 따라가면 됩니다.

modCount와 fail-fast

이 또한 소스에서 자주 보이는 포인트입니다.

LinkedList의 상속 계층에는 modCount 필드가 있고, 구조 변경 횟수를 의미합니다. 일반적으로 다음 연산에서 증가합니다.

add
remove
clear
기타 구조 변경

이터레이터 생성 시 expectedModCount 를 기록합니다.

이후 반복마다,

현재 modCountexpectedModCount 와 같은지

를 검사합니다.

같지 않으면 반복 중 외부에서 리스트가 변경된 것이므로 ConcurrentModificationException 을 던집니다.

이것이 fail-fast 메커니즘입니다.

목적은 스레드 안전성을 보장하는 것이 아니라, 잘못된 사용을 빨리 드러내는 것입니다.

예를 들어 이터레이터로 순회하면서 직접 list.remove() 를 호출하면 이 예외가 발생할 수 있습니다.

초간단 소스 사고 모델

Java

        class MyLinkedList<E> {
        Node<E> first;
        Node<E> last;
        int size;

        static class Node<E> {
                E item;
                Node<E> prev;
                Node<E> next;
        }
}

용도

일반 List로 사용할 때:

add
get
set
remove
size

큐로 사용할 때:

offer
poll
peek

덱(deque)으로 사용할 때:

offerFirst
offerLast
pollFirst
pollLast
peekFirst
peekLast

스택으로 사용할 때:

push
pop
peek

결국 LinkedList가 하는 일은 다음으로 요약됩니다.

머리 삽입: first 와 기존 머리의 prev 갱신
꼬리 삽입: last 와 기존 꼬리의 next 갱신
중간 삽입: predecessor, 새 노드, successor를 다시 연결
삭제: 대상 노드 앞뒤를 다시 연결
인덱스 접근: 머리 또는 꼬리에서 따라가며 노드 찾기
이터레이터: next 를 따라 순차 접근

Fonnpo

Spring 프레임워크 완전 가이드

HashMap 상세 분석

ArrayList 상세 분석