LinkedList — 이중 연결 리스트의 구조와 실전 활용

지난 글에서 ArrayList의 동적 배열 구조와 성능 특성을 살펴봤다. 이번에는 **LinkedList**를 다룬다. LinkedList는 ArrayList와 달리 연속된 메모리 블록 대신 노드 체인으로 데이터를 저장한다. “항상 ArrayList를 쓰라”는 통설 너머에 LinkedList가 진정 빛나는 상황이 존재한다.

내부 구조: 이중 연결 리스트

Java의 LinkedList는 **이중 연결 리스트(Doubly Linked List)**로 구현되어 있다. 각 원소는 독립적인 Node<E> 객체에 저장되며, 이전 노드와 다음 노드를 참조하는 두 포인터를 보유한다.

// java.util.LinkedList 내부 (간략화)
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 객체 자체는 head, tail, size 세 필드만 직접 보유한다. 원소를 추가하면 새 Node를 힙에 할당하고 기존 노드의 포인터만 교체하면 된다.

주요 연산과 시간 복잡도

인덱스 접근 get(i): 배열처럼 임의 접근이 불가능하다. head(또는 tail)에서 순차적으로 포인터를 따라가야 하므로 O(n)이다. i < size/2이면 head에서, 그 반대이면 tail에서 탐색해 절반으로 줄이지만 여전히 O(n)이다.

끝에 추가 add(e): tail 포인터를 알고 있으므로 새 노드를 tail.next에 연결하고 tail을 교체하면 된다. O(1).

중간 삽입/삭제: 노드 포인터 교체 자체는 O(1)이다. 단, 해당 위치 노드를 먼저 찾아야 하기 때문에 인덱스 기반 호출(add(i, e), remove(i))은 내부적으로 탐색 O(n)을 수행한다. 반복자(Iterator)를 통해 현재 위치를 유지하는 경우에만 진정한 O(1) 삽입/삭제가 보장된다.

List 인터페이스 구현

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

List<String> tasks = new LinkedList<>();
tasks.add("compile");
tasks.add("test");
tasks.add("deploy");

// 중간 삽입 — 반복자 사용 시 O(1)
ListIterator<String> it = tasks.listIterator(1);
it.add("lint");          // "test" 앞에 삽입
System.out.println(tasks); // [compile, lint, test, deploy]

// 인덱스 접근 — 내부적으로 O(n) 탐색
String second = tasks.get(1);   // "lint"

Deque 인터페이스 구현

LinkedList는 List뿐만 아니라 Deque<E>도 구현한다는 점이 특징적이다. 양방향 큐(Double-Ended Queue)로 쓸 수 있다.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

// 스택처럼
Deque<Integer> stack = new LinkedList<>();
stack.push(1);   // addFirst
stack.push(2);
stack.push(3);
System.out.println(stack.pop());  // 3 (LIFO)

// 큐처럼
Deque<String> queue = new LinkedList<>();
queue.offer("a");
queue.offer("b");
System.out.println(queue.poll()); // "a" (FIFO)

다만 Deque 용도라면 ArrayDeque가 LinkedList보다 빠르다 — 배열 기반으로 캐시 지역성이 좋고 노드 객체 할당이 없기 때문이다.

LinkedList vs ArrayList 선택 기준

LinkedList가 ArrayList보다 유리한 경우:

1. Iterator를 통한 대량 중간 삽입/삭제: 순차 순회 중 많은 원소를 삽입·삭제하는 편집 워크플로.
2. Queue/Deque 구현 (성능보다 코드 명확성 우선): ArrayDeque가 없던 시절 코드베이스 유지.
3. 무한히 증가하는 순차 큐: 배열 복사 비용을 원천적으로 제거.

반대로 대부분의 상황에서는 ArrayList가 낫다. 인덱스 접근, 캐시 지역성, 메모리 오버헤드(각 노드가 두 포인터를 추가 보유) 모두 ArrayList에 유리하다.

// 잘못된 패턴: 인덱스로 LinkedList 순회
LinkedList<Integer> list = new LinkedList<>(List.of(1, 2, 3, 4, 5));
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i)); // 매번 O(n) 탐색 — O(n²) 전체!
}

// 올바른 패턴: 향상 for문 또는 Iterator 사용
for (int v : list) {
    System.out.println(v);           // 내부적으로 Iterator — O(n)
}

메모리 고려사항

ArrayList는 원소마다 참조(8바이트) 하나만 추가하지만, LinkedList는 각 Node 객체(헤더 16바이트 + item 8바이트 + next 8바이트 + prev 8바이트 = 40바이트)를 별도로 힙에 할당한다. 원소 수가 많을수록 메모리 사용량과 GC 부담이 커진다.

// 메모리 비교 시뮬레이션 (원소 100만 개)
// ArrayList:  ~8MB (참조 배열)
// LinkedList: ~40MB (노드 객체 × 100만)

원소 수가 수만 이상이고 랜덤 접근이 빈번하다면 LinkedList는 현실적으로 사용 적합도가 낮다.

요약

특성	LinkedList
구현	이중 연결 리스트
get(i)	O(n)
끝에 add	O(1)
Iterator 삽입/삭제	O(1)
구현 인터페이스	List, Deque
메모리 오버헤드	높음 (노드 객체)

---

지난 글: List와 ArrayList — 순서 있는 컬렉션의 핵심

다음 글: Vector와 Stack — 레거시 스레드 안전 컬렉션

읽어주셔서 감사합니다. 😊