연결 리스트(Linked List): 보물 찾기 쪽지의 비밀 (완전정복)

1. 프롤로그 - 보물 찾기 쪽지가 더 낫다고?

자료구조를 처음 공부할 때 가장 이해가 안 갔던 게 연결 리스트(Linked List)였다. 배열(Array)이라는 완벽한 자료구조가 있는데, 왜 굳이 조회가 O(N)이나 걸리는 비효율적인 자료구조를 배워야 하냐는 거였다. "이거 실제로 언제 써요?"라는 질문을 달고 살았다.

그런데 LRU Cache를 직접 구현해보고 나서야 이해했다. 연결 리스트는 배열과 완전히 다른 철학으로 설계된 자료구조였다. 배열이 "빠른 조회"에 목숨을 건 자료구조라면, 연결 리스트는 "빠른 삽입/삭제"에 목숨을 건 자료구조였다. 쓰임새가 다른 거였다.

나는 연결 리스트를 보물 찾기 쪽지로 이해했다.

첫 번째 쪽지를 펴본다. "다음 쪽지는 부산역 3번 비상구 뒤에 있음." 그곳에 가야만 다음 위치를 알 수 있다. 메모리 여기저기에 흩어져 있는 노드들을 포인터로 연결한 구조, 결국 이거였다.

반면, 배열(Array)은 훈련소 연병장에 줄 서 있는 군인들이다. "3번째 놈 나와!" 하면 바로 튀어나온다. 어깨를 맞대고 붙어 있으니까(연속된 메모리). 하지만 중간에 끼워 넣으려면? 뒤에 있는 1,000명이 한 칸씩 물러나야 한다.

이 차이를 정확히 이해하고 나니, 왜 어떤 상황에서는 배열이 압도적으로 빠르고, 어떤 상황에서는 연결 리스트가 필수인지 와닿았다. 이 글은 그 깨달음을 정리해본다.

2. 구조의 핵심 - 노드와 포인터라는 설계

연결 리스트의 구조를 처음 봤을 때, "왜 이렇게 복잡하게 만들었지?"라고 생각했다. 배열은 그냥 데이터를 연속해서 저장하면 끝인데, 연결 리스트는 노드(Node)라는 단위로 데이터를 감싸야 한다.

노드는 두 가지 정보를 담는다.

Data: 진짜 저장하려는 값 (예: 숫자 10, 문자열 "hello").
Pointer (Next): 다음 노드가 있는 메모리 주소.

[ Data: 10 | Next: 0x1A2B ]  ---->  [ Data: 20 | Next: 0x3C4D ]  ---->  [ Data: 30 | Next: NULL ]
   (Head)

배열은 데이터만 저장하면 되는데, 연결 리스트는 주소를 저장할 추가 공간(Overhead)이 필요하다. 64비트 시스템에서는 8바이트짜리 포인터를 모든 노드마다 저장해야 한다. 4바이트 정수를 저장하려고 8바이트 포인터를 쓰는 건 배보다 배꼽이 더 큰 격이다.

하지만 이 포인터 덕분에 얻는 게 있다. 메모리의 연속성이 필요 없어진다.

배열은 반드시 연속된 메모리 블록이 있어야 한다. 1,000개짜리 배열을 만들려면, 메모리에 딱 1,000칸이 이어진 공간이 있어야 한다. 메모리가 조각조각 파편화된 상태에서는 배열을 할당할 수 없다.

반면 연결 리스트는 메모리 어디든 빈 곳에 노드를 만들고, 포인터로 연결하면 된다. 메모리가 조각나 있어도 상관없다. 이걸 받아들이고 나니, 왜 운영체제의 메모리 관리자가 연결 리스트를 쓰는지 이해됐다.

3. 조회(Read)의 비극 - 순차 접근의 한계

배열의 가장 큰 장점은 랜덤 접근(Random Access)이다. "50번째 원소 가져와." 배열은 계산 한 번(시작주소 + 50 × sizeof(int))으로 바로 접근한다. O(1).

연결 리스트는? 방법이 없다. 1번부터 49번까지 다 방문해서 포인터를 읽어봐야 50번 위치를 알 수 있다. 이것이 순차 접근(Sequential Access)이다.

# 배열 - O(1) 조회
arr = [10, 20, 30, 40, 50]
print(arr[3])  # 즉시 40을 가져옴

# 연결 리스트 - O(N) 조회
current = head
for i in range(3):
    current = current.next
print(current.data)  # 3번 이동해야 40에 도달

처음엔 이게 너무 비효율적으로 보였다. "왜 이런 자료구조를 쓰냐"고 생각했다.

하지만 연결 리스트는 조회를 포기한 대신 다른 걸 얻었다는 걸 나중에 이해했다. 조회가 느린 건 설계상 의도된 트레이드오프였다. 대신 삽입/삭제가 압도적으로 빠르다.

이 트레이드오프를 받아들이고 나니, "어떤 상황에서 연결 리스트를 써야 하는가?"라는 질문의 답이 명확해졌다. 조회는 드물고, 삽입/삭제가 빈번한 곳.

4. 삽입/삭제(Insert/Delete)의 기적 - 포인터 2개만 바꾸면 끝

연결 리스트의 진짜 강점은 중간 삽입/삭제다.

배열에서 중간에 원소를 삽입하려면?

arr = [1, 2, 4, 5]
arr.insert(2, 3)  # 2번 인덱스에 3 삽입
# 내부적으로 4, 5를 한 칸씩 뒤로 이동 (Shifting)

원소가 100만 개면? 뒤에 있는 99만 9천 개를 전부 이동시켜야 한다. O(N).

연결 리스트는? 포인터 2개만 바꾸면 된다.

A와 C 사이에 B를 넣으려면?

A의 Next 포인터: C를 가리키던 걸 -> B로 변경.
B의 Next 포인터: C를 가리키게 설정.

Before: A ---> C
After:  A ---> B ---> C

데이터가 100만 개가 있어도, 단 두 번의 포인터 변경으로 끝이다. O(1).

하지만 여기엔 함정이 있다.

주의: 삽입 자체는 O(1)이지만, "어디에 넣을지 찾는 과정(Search)"은 O(N)이다. 탐색 없이 위치를 알고 있을 때만 빠르다.

예를 들어, "50번째 위치에 삽입"하려면?

50번째 노드까지 이동: O(N).
삽입: O(1). 총 O(N).

결국 삽입이 O(1)인 건 이미 포인터를 들고 있을 때다. 이게 와닿은 건 LRU Cache를 구현할 때였다.

LRU Cache는 "최근에 쓴 데이터를 맨 앞으로 옮긴다"는 로직이 핵심이다. 만약 이미 해시맵으로 노드의 포인터를 들고 있다면?

해시맵에서 노드 포인터를 O(1)에 찾는다.
그 노드를 연결 리스트 맨 앞으로 옮긴다 (포인터 몇 개만 수정) -> O(1).

이때 연결 리스트의 진가가 발휘된다. 배열이었다면 원소를 삭제하고 맨 앞에 추가하는 데 O(N)이 걸렸을 것이다.

5. 숨겨진 단점 - 메모리 파편화와 캐시 미스

연결 리스트를 공부하면서 한 가지 의문이 들었다. "삽입/삭제가 이렇게 빠른데, 왜 실제로는 배열을 더 많이 쓰지?"

답은 캐시 효율에 있었다.

현대 CPU는 메모리를 읽을 때 캐시(Cache)를 적극 활용한다. 데이터를 읽으면 그 주변 데이터도 함께 캐시에 올려놓는다(Spatial Locality). 배열은 연속된 메모리에 있으니, 한 번에 여러 원소를 캐시에 올릴 수 있다.

연결 리스트는? 노드들이 힙(Heap) 메모리 여기저기 흩어져 있다. 다음 노드를 읽으려면 캐시 미스(Cache Miss)가 나고, RAM까지 갔다 와야 한다. 이게 반복되면 성능이 급격히 떨어진다.

실제 벤치마크를 돌려보면, 같은 10만 개 데이터를 순회할 때 배열이 연결 리스트보다 10배 이상 빠른 경우도 있다.

또 다른 단점은 메모리 오버헤드다. 4바이트 정수를 저장하는데, 8바이트 포인터를 추가로 써야 한다. 메모리 사용량이 3배로 늘어난다.

이걸 이해하고 나니, 왜 고성능이 필요한 곳에서는 배열을 쓰는지 납득이 갔다. 연결 리스트는 삽입/삭제가 압도적으로 많고, 조회는 드문 특수한 상황에서만 쓴다는 걸 받아들였다.

6. 변형의 세계 - 원형, 이중, 센티넬

연결 리스트는 기본 형태(Singly Linked List)에서 여러 변형이 생겼다. 각각의 변형은 특정 문제를 해결하기 위해 고안됐다.

6-1. 원형 연결 리스트 (Circular Linked List)

마지막 노드가 NULL을 가리키는 게 아니라, 다시 Head를 가리킨다.

A ---> B ---> C ---> D
^                    |
|____________________|

처음엔 "왜 굳이 원형으로 만들지?"라고 생각했는데, 운영체제 스케줄러를 공부하면서 이해했다.

Round Robin 스케줄링은 모든 프로세스에게 공평하게 시간을 나눠준다.

Process A -> Process B -> Process C -> Process D.
D가 끝나면? 다시 A로 돌아간다.

이걸 일반 연결 리스트로 구현하면, 끝에 도달할 때마다 "Head로 다시 이동"하는 로직을 추가해야 한다. 원형 연결 리스트는 이걸 자동으로 처리한다.

6-2. 이중 연결 리스트 (Doubly Linked List)

Prev 포인터를 추가해서, 앞뒤로 이동할 수 있게 만든다.

NULL <- [ Prev | Data | Next ] <-> [ Prev | Data | Next ] <-> [ Prev | Data | Next ] -> NULL

처음엔 "포인터가 2개나 되면 메모리 낭비 아니야?"라고 생각했다. 하지만 LRU Cache를 구현하면서 이해했다.

LRU Cache의 핵심은 두 가지다.

최근에 쓴 데이터를 맨 앞으로 이동 (Move to Front).
캐시가 꽉 차면 맨 뒤의 데이터를 삭제 (Delete Least Recently Used).

Singly Linked List로는 "맨 뒤 삭제"가 O(N)이다. 맨 뒤까지 가야 하니까. Doubly Linked List는 tail.prev로 바로 접근할 수 있다. O(1).

# LRU Cache 핵심 구조
class LRUCache:
    def __init__(self):
        self.cache = {}  # 해시맵 {key: Node}
        self.head = DummyNode()  # 최근 사용
        self.tail = DummyNode()  # 오래된 데이터
        self.head.next = self.tail
        self.tail.prev = self.head

    def move_to_front(self, node):
        # 1. 원래 위치에서 제거 (O(1) - Prev/Next만 조작)
        node.prev.next = node.next
        node.next.prev = node.prev

        # 2. Head 바로 뒤에 삽입 (O(1))
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

이중 연결 리스트 없이는 LRU Cache를 효율적으로 구현할 수 없다는 걸 직접 구현하면서 체감했다.

6-3. 센티넬 노드 (Sentinel / Dummy Node)

맨 앞에 빈 노드(Dummy)를 둬서 코드를 단순하게 만드는 기법이다.

일반 연결 리스트는 Head가 NULL인지 항상 체크해야 한다.

def insert(self, data):
    new_node = Node(data)
    if self.head is None:  # 예외 처리
        self.head = new_node
    else:
        # 일반 삽입 로직

센티넬 노드를 쓰면?

def __init__(self):
    self.sentinel = Node(None)  # Dummy

def insert(self, data):
    new_node = Node(data)
    new_node.next = self.sentinel.next
    self.sentinel.next = new_node
    # if 문 불필요!

알고리즘 문제에서 연결 리스트를 다룰 때, 센티넬 노드를 쓰면 엣지 케이스 처리가 훨씬 간단해진다. 이 패턴을 알고 나서 연결 리스트 문제 풀이 속도가 2배 빨라졌다.

7. 완전한 구현 - 파이썬 코드로 만들기

이론만 알고 있으면 실제로 쓸 수 없다. 나는 직접 구현해보면서 연결 리스트의 동작 방식을 완전히 이해했다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    # O(N) - 맨 끝까지 이동
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return

        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    # O(1) - Head 앞에 삽입
    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # O(N) - 특정 값 삭제
    def delete(self, target):
        if not self.head:
            return

        # Head가 타겟인 경우
        if self.head.data == target:
            self.head = self.head.next
            return

        # 중간/끝 노드 삭제
        current = self.head
        while current.next:
            if current.next.data == target:
                current.next = current.next.next
                return
            current = current.next

    # O(N) - 순회하며 탐색
    def search(self, target):
        current = self.head
        while current:
            if current.data == target:
                return True
            current = current.next
        return False

    # O(N) - 역순 변환 (핵심 패턴)
    def reverse(self):
        prev = None
        current = self.head

        while current:
            next_node = current.next  # 다음 노드 백업
            current.next = prev       # 방향 뒤집기
            prev = current            # Prev 전진
            current = next_node       # Current 전진

        self.head = prev

    # 출력용
    def display(self):
        current = self.head
        result = []
        while current:
            result.append(str(current.data))
            current = current.next
        print(" -> ".join(result))

# 사용 예시
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.prepend(5)
ll.display()  # 5 -> 10 -> 20
ll.reverse()
ll.display()  # 20 -> 10 -> 5

reverse() 함수는 알고리즘 구현에서 가장 자주 다루는 문제 중 하나다. 포인터 3개(prev, current, next)를 조작해서 방향을 뒤집는 로직을 직접 구현해보니, 포인터 조작의 원리가 손에 익었다.

8. 실제 응용 - LRU Cache 구현

연결 리스트의 가장 유명한 응용이 LRU Cache다. 이중 연결 리스트 + 해시맵을 조합해서 만든다.

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # {key: Node}

        # Sentinel 노드
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        """노드를 연결 리스트에서 제거"""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add_to_head(self, node):
        """노드를 Head 바로 뒤에 추가 (최근 사용)"""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1

        node = self.cache[key]
        self._remove(node)
        self._add_to_head(node)  # 최근 사용으로 갱신
        return node.value

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])

        new_node = Node(key, value)
        self._add_to_head(new_node)
        self.cache[key] = new_node

        if len(self.cache) > self.capacity:
            # 가장 오래된 노드(Tail 직전) 삭제
            lru_node = self.tail.prev
            self._remove(lru_node)
            del self.cache[lru_node.key]

# 사용 예시
cache = LRUCache(2)
cache.put(1, 100)
cache.put(2, 200)
print(cache.get(1))  # 100
cache.put(3, 300)    # 2를 제거 (LRU)
print(cache.get(2))  # -1 (삭제됨)

이 코드를 직접 짜보기 전까지는 "LRU Cache가 왜 O(1)이지?"라고 이해가 안 갔다. 구현해보니 명확해졌다.

해시맵: Key로 노드를 O(1)에 찾는다.
이중 연결 리스트: 노드를 맨 앞/뒤로 옮기는 게 O(1).

배열로는 절대 이런 성능을 낼 수 없다. 이게 연결 리스트의 진짜 쓰임새다.

9. 현실 - 고수준 언어에서는 잘 안 쓴다

여기까지 공부하고 나서 한 가지 의문이 들었다. "그럼 실제로 연결 리스트를 많이 쓰나?"

답은 아니다.

JavaScript에는 아예 없다

JavaScript에는 네이티브 연결 리스트 자료구조가 아예 없다. 배열(Array)이 너무 강력하기 때문이다.

JavaScript의 배열은 사실 동적 배열(Dynamic Array)이다. 크기가 자동으로 늘어나고, push()/pop()이 O(1)이다. 중간 삽입도 splice()로 간단히 처리된다.

연결 리스트의 장점(동적 크기, 삽입/삭제)을 배열이 이미 제공하니, 굳이 연결 리스트를 만들 이유가 없다.

Java: LinkedList vs ArrayList

Java는 java.util.LinkedList를 제공하지만, 실제로는 거의 안 쓴다. 대부분 ArrayList를 쓴다.

List<Integer> list = new ArrayList<>();  // 대부분 이거
List<Integer> list = new LinkedList<>(); // 거의 안 씀

이유?

캐시 효율: ArrayList가 압도적으로 빠르다.
메모리: LinkedList는 노드당 포인터 2개(Prev, Next) 오버헤드가 크다.
실제 워크로드: 대부분의 앱은 조회가 많고 삽입/삭제가 적다.

LinkedList를 써야 하는 경우는 큐(Queue)를 구현할 때 정도다. 앞에서 삭제(poll), 뒤에서 삽입(offer)이 O(1)이니까.

그럼 언제 쓰냐?

저수준 시스템 프로그래밍: 운영체제 메모리 관리자, 커널 자료구조.
알고리즘 문제: 알고리즘 문제에서 자주 등장.
특수 자료구조: LRU Cache, Undo/Redo 스택.

고수준 언어에서는 직접 쓸 일이 거의 없다. 하지만 내부 동작 원리를 이해하는 건 중요하다. LRU Cache, 브라우저 히스토리, 운영체제 스케줄러 같은 곳에서 핵심 원리로 쓰이니까.

10. 시간 복잡도 비교 - 배열 vs 연결 리스트

연산	배열 (Array)	연결 리스트 (Linked List)
조회 (Access)	O(1) - Random Access	O(N) - Sequential
탐색 (Search)	O(N)	O(N)
맨 앞 삽입	O(N) - Shift 필요	O(1)
맨 뒤 삽입	O(1) - Amortized	O(N) - Tail 없으면 / O(1) - Tail 있으면
중간 삽입	O(N) - Shift 필요	O(1) - 포인터만 변경 (위치 알 때)
맨 앞 삭제	O(N) - Shift 필요	O(1)
맨 뒤 삭제	O(1)	O(N) - Singly / O(1) - Doubly
중간 삭제	O(N) - Shift 필요	O(1) - 포인터만 변경 (위치 알 때)
메모리	연속 할당, 캐시 친화적	파편화, 포인터 오버헤드

이 표를 보면 명확하다.

조회 많음 → 배열
삽입/삭제 많음 → 연결 리스트

11. 실전 문제 - 사이클 검출 (Floyd's Cycle Detection)

연결 리스트 관련 알고리즘 문제에서 가장 유명한 문제는 "연결 리스트에 사이클이 있는지 검출하기"다.

Floyd's Cycle Detection Algorithm (토끼와 거북이 알고리즘):

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next        # 1칸 이동
        fast = fast.next.next   # 2칸 이동

        if slow == fast:
            return True  # 사이클 발견

    return False

왜 동작하냐?

사이클이 있으면, 빠른 포인터(Fast)가 느린 포인터(Slow)를 언젠가 따라잡는다.
사이클이 없으면, Fast가 먼저 끝(NULL)에 도달한다.

공간 복잡도 O(1)로 사이클을 검출하는 이 알고리즘을 이해하고 나니, 포인터 조작의 묘미가 느껴졌다.

12. 요약 - 결국 내가 이해한 연결 리스트

구조: 데이터 + 포인터를 묶은 노드들의 체인. 메모리가 연속일 필요가 없다.
장점: 중간 삽입/삭제가 O(1). 메모리 파편화 상황에서도 동작.
단점: 조회 O(N). 캐시 효율 나쁨. 포인터 오버헤드.
변형: 원형(Round Robin), 이중(LRU Cache), 센티넬(엣지 케이스 제거).
현실: 고수준 언어에서는 직접 안 쓰지만, 내부 원리로 중요.
핵심 깨달음: 배열과 완전히 다른 철학. 조회 vs 삽입/삭제의 트레이드오프.

나는 연결 리스트를 "보물 찾기 쪽지"로 이해했다. 다음 위치를 알려면 현재 쪽지를 펴봐야 한다. 비효율적으로 보이지만, 쪽지를 추가하거나 빼는 건 순식간이다. 이 차이를 받아들이고 나니, 언제 배열을 쓰고 언제 연결 리스트를 써야 하는지 명확해졌다.

결국 자료구조는 정답이 없다. 상황에 맞는 선택이 있을 뿐이다. 연결 리스트는 그 선택지 중 하나다.

Linked List: The Scavenger Hunt of Data Structures (Definitive Guide)

1. Prologue: Why Choose Scavenger Hunt Over Apartments?

When I first learned data structures, Linked Lists confused me the most. Why would anyone use a data structure with O(N) lookup when we have Arrays? "When do we actually use this in production?" was my constant question.

It clicked when I implemented an LRU Cache from scratch. Linked Lists aren't a worse version of Arrays. They're designed with a completely different philosophy. If Arrays prioritize "fast lookup," Linked Lists prioritize "fast insertion/deletion." Different tools for different jobs.

I understood Linked Lists as a scavenger hunt.

You open the first note. "Next clue is behind Exit 3 at Busan Station." You must go there to find the next location. Nodes scattered across memory, tied together with pointers. That's what it was.

In contrast, Arrays are soldiers standing in formation at boot camp. "Number 3, step forward!" Instant response. They're shoulder-to-shoulder (contiguous memory). But insert someone in the middle? The 1,000 people behind must shift one step back.

Once I understood this difference, it became clear why Arrays dominate in some scenarios and Linked Lists are essential in others. This post captures that realization.

2. Core Structure: Nodes and Pointers by Design

The first time I saw a Linked List structure, I thought, "Why make it so complicated?" Arrays just store data contiguously. Linked Lists wrap data in a Node.

A Node contains two pieces of information:

Data: The actual value you want to store (e.g., integer 10, string "hello").
Pointer (Next): Memory address of the next node.

[ Data: 10 | Next: 0x1A2B ]  ---->  [ Data: 20 | Next: 0x3C4D ]  ---->  [ Data: 30 | Next: NULL ]
   (Head)

Arrays only need data storage. Linked Lists need address storage, adding overhead. On 64-bit systems, that's an 8-byte pointer per node. Storing a 4-byte integer requires an 8-byte pointer—the tail is bigger than the dog.

But this pointer buys something valuable: No contiguous memory requirement.

Arrays need a continuous memory block. To create a 1,000-element array, you need exactly 1,000 consecutive slots. In fragmented memory, array allocation fails.

Linked Lists? Create nodes wherever space exists, then connect with pointers. Memory fragmentation doesn't matter. Once I accepted this, I understood why OS memory managers use linked lists.

3. The Tragedy of Access: Sequential Access Limitation

Arrays' biggest advantage is Random Access. "Get the 50th element." Arrays compute start_address + 50 × sizeof(int) instantly. O(1).

Linked Lists? No shortcut. You must visit nodes 1 through 49, reading pointers along the way. This is Sequential Access.

# Array: O(1) access
arr = [10, 20, 30, 40, 50]
print(arr[3])  # Instantly gets 40

# Linked List: O(N) access
current = head
for i in range(3):
    current = current.next
print(current.data)  # Must traverse 3 times to reach 40

Initially, this seemed absurdly inefficient. "Why use this data structure?"

But I later understood: Linked Lists sacrifice lookup to gain something else. Slow access is an intentional design tradeoff. In exchange, insertion/deletion is dramatically faster.

Once I accepted this tradeoff, the answer to "When should I use Linked Lists?" became obvious: When lookups are rare and insertions/deletions are frequent.

4. The Miracle of Insertion/Deletion: Just Flip Two Pointers

The real strength of Linked Lists is mid-list insertion/deletion.

Inserting into the middle of an array?

arr = [1, 2, 4, 5]
arr.insert(2, 3)  # Insert 3 at index 2
# Internally shifts 4, 5 one position right (Shifting)

With 1 million elements? You shift 999,000 elements. O(N).

Linked Lists? Change two pointers.

Insert B between A and C:

A's Next pointer: Change from C to B.
B's Next pointer: Point to C.

Before: A ---> C
After:  A ---> B ---> C

Even with 1 million elements, just two pointer changes. O(1).

But there's a catch.

Caveat: Insertion itself is O(1), but finding where to insert (Search) is O(N). Only fast when you already know the position.

For example, "insert at position 50":

Traverse to 50th node: O(N).
Insert: O(1). Total: O(N).

Insertion is O(1) only when you already hold the pointer. This clicked when I implemented LRU Cache.

LRU Cache's core logic is "move recently used data to the front." If you already have the node pointer via a hash map:

Find node pointer from hash map in O(1).
Move that node to front of linked list (modify a few pointers) → O(1).

That's when Linked Lists shine. With an array, deleting and re-inserting at the front would cost O(N).

5. Hidden Cost: Memory Fragmentation and Cache Misses

While studying Linked Lists, one question nagged me: "If insertion/deletion is this fast, why do we use arrays more in production?"

The answer: Cache efficiency.

Modern CPUs heavily utilize cache when reading memory. Reading data prefetches surrounding data into cache (Spatial Locality). Arrays store data contiguously, so multiple elements load into cache at once.

Linked Lists? Nodes scatter across heap memory. Reading the next node causes cache misses, forcing slow RAM fetches. Repeated misses crush performance.

Real-world benchmarks show arrays can be 10× faster than Linked Lists when iterating 100,000 elements.

Another drawback: Memory overhead. Storing a 4-byte integer requires an additional 8-byte pointer. Memory usage triples.

Understanding this explained why high-performance systems favor arrays. Linked Lists are reserved for special scenarios with heavy insertion/deletion and rare lookups.

6. Variations: Circular, Doubly, Sentinel

Linked Lists evolved from the basic form (Singly Linked List) into variations, each solving specific problems.

6-1. Circular Linked List

The last node doesn't point to NULL—it points back to Head.

A ---> B ---> C ---> D
^                    |
|____________________|

Initially, I thought, "Why make it circular?" Then I studied OS schedulers.

Round Robin Scheduling fairly distributes time to all processes:

Process A → Process B → Process C → Process D.
After D? Return to A.

With a regular linked list, you'd need extra logic to "jump back to Head" when reaching the end. Circular lists handle this automatically.

6-2. Doubly Linked List

Adds a Prev pointer, enabling bidirectional traversal.

NULL <- [ Prev | Data | Next ] <-> [ Prev | Data | Next ] <-> [ Prev | Data | Next ] -> NULL

At first, I thought, "Two pointers per node wastes memory." But implementing LRU Cache changed my mind.

LRU Cache has two core operations:

Move recently used data to front (Move to Front).
Delete tail when cache is full (Delete Least Recently Used).

With Singly Linked Lists, "delete tail" costs O(N)—you must traverse to the end. Doubly Linked Lists access tail.prev directly. O(1).

# LRU Cache core structure
class LRUCache:
    def __init__(self):
        self.cache = {}  # Hash map {key: Node}
        self.head = DummyNode()  # Recently used
        self.tail = DummyNode()  # Old data
        self.head.next = self.tail
        self.tail.prev = self.head

    def move_to_front(self, node):
        # 1. Remove from original position (O(1) - manipulate Prev/Next)
        node.prev.next = node.next
        node.next.prev = node.prev

        # 2. Insert right after Head (O(1))
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

Without Doubly Linked Lists, efficient LRU Cache implementation is impossible. I learned this by building it myself.

6-3. Sentinel Node (Dummy Node)

Place an empty node (Dummy) at the start to simplify code.

Regular linked lists require constant null checks:

def insert(self, data):
    new_node = Node(data)
    if self.head is None:  # Edge case handling
        self.head = new_node
    else:
        # Normal insertion logic

With a sentinel node:

def __init__(self):
    self.sentinel = Node(None)  # Dummy

def insert(self, data):
    new_node = Node(data)
    new_node.next = self.sentinel.next
    self.sentinel.next = new_node
    # No if statement needed!

In coding interviews, using sentinel nodes when solving linked list problems eliminates edge case handling. Learning this pattern doubled my solving speed.

7. Complete Implementation: Python Code

Theory alone doesn't make you proficient. I fully understood Linked Lists by implementing them from scratch.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    # O(N) - Traverse to end
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return

        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    # O(1) - Insert before Head
    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # O(N) - Delete specific value
    def delete(self, target):
        if not self.head:
            return

        # If Head is target
        if self.head.data == target:
            self.head = self.head.next
            return

        # Delete middle/end node
        current = self.head
        while current.next:
            if current.next.data == target:
                current.next = current.next.next
                return
            current = current.next

    # O(N) - Search by traversal
    def search(self, target):
        current = self.head
        while current:
            if current.data == target:
                return True
            current = current.next
        return False

    # O(N) - Reverse (core pattern)
    def reverse(self):
        prev = None
        current = self.head

        while current:
            next_node = current.next  # Backup next node
            current.next = prev       # Flip direction
            prev = current            # Advance prev
            current = next_node       # Advance current

        self.head = prev

    # Display utility
    def display(self):
        current = self.head
        result = []
        while current:
            result.append(str(current.data))
            current = current.next
        print(" -> ".join(result))

# Usage example
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.prepend(5)
ll.display()  # 5 -> 10 -> 20
ll.reverse()
ll.display()  # 20 -> 10 -> 5

The reverse() function is one of the most common practical problems. Implementing it with three pointers (prev, current, next) to flip direction taught me pointer manipulation by muscle memory.

8. Real-World Application: LRU Cache Implementation

The most famous application of Linked Lists is LRU Cache, combining Doubly Linked List + Hash Map.

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # {key: Node}

        # Sentinel nodes
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        """Remove node from linked list"""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add_to_head(self, node):
        """Add node right after Head (most recently used)"""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1

        node = self.cache[key]
        self._remove(node)
        self._add_to_head(node)  # Mark as recently used
        return node.value

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])

        new_node = Node(key, value)
        self._add_to_head(new_node)
        self.cache[key] = new_node

        if len(self.cache) > self.capacity:
            # Delete least recently used (right before Tail)
            lru_node = self.tail.prev
            self._remove(lru_node)
            del self.cache[lru_node.key]

# Usage example
cache = LRUCache(2)
cache.put(1, 100)
cache.put(2, 200)
print(cache.get(1))  # 100
cache.put(3, 300)    # Removes key 2 (LRU)
print(cache.get(2))  # -1 (deleted)

Before writing this code, I didn't understand "Why is LRU Cache O(1)?" Implementation made it crystal clear:

Hash Map: Find node by key in O(1).
Doubly Linked List: Move node to front/back in O(1).

Arrays could never achieve this performance. This is Linked Lists' true purpose.

9. Reality: Rarely Used in High-Level Languages

After studying all this, one question remained: "Do we actually use Linked Lists in production?"

Answer: Not really.

JavaScript Doesn't Even Have Them

JavaScript has no native Linked List data structure. Arrays (Array) are too powerful.

JavaScript arrays are actually Dynamic Arrays. They auto-resize, push()/pop() run in O(1), and mid-list insertion is easy with splice().

Arrays already provide Linked Lists' advantages (dynamic size, insertion/deletion), so there's no reason to implement linked lists.

Java: LinkedList vs ArrayList

Java provides java.util.LinkedList, but production code rarely uses it. Most code uses ArrayList.

List<Integer> list = new ArrayList<>();  // Almost always this
List<Integer> list = new LinkedList<>(); // Rarely used

Why?

Cache efficiency: ArrayList is overwhelmingly faster.
Memory: LinkedList has heavy overhead (2 pointers per node: Prev, Next).
Real workloads: Most apps do more lookups than insertions/deletions.

LinkedList's main use case: implementing Queues. Front deletion (poll) and rear insertion (offer) are both O(1).

So When Do We Use Them?

Low-level systems programming: OS memory managers, kernel data structures.
Algorithm problems: Frequently appear in technical assessments.
Specialized data structures: LRU Cache, Undo/Redo stacks.

High-level languages rarely need them directly. But understanding the underlying principles matters. LRU Cache, browser history, and OS schedulers all rely on these core concepts.

10. Time Complexity Comparison: Array vs Linked List

Operation	Array	Linked List
Access	O(1) - Random Access	O(N) - Sequential
Search	O(N)	O(N)
Insert Front	O(N) - Shift required	O(1)
Insert Back	O(1) - Amortized	O(N) - No tail / O(1) - With tail
Insert Middle	O(N) - Shift required	O(1) - Just pointer change (if position known)
Delete Front	O(N) - Shift required	O(1)
Delete Back	O(1)	O(N) - Singly / O(1) - Doubly
Delete Middle	O(N) - Shift required	O(1) - Just pointer change (if position known)
Memory	Contiguous, cache-friendly	Fragmented, pointer overhead

This table makes it clear:

Many lookups → Array
Many insertions/deletions → Linked List

11. Practice Problem: Cycle Detection (Floyd's Algorithm)

The most famous coding interview problem for Linked Lists is "Detect if a linked list has a cycle."

Floyd's Cycle Detection Algorithm (Tortoise and Hare):

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next        # Move 1 step
        fast = fast.next.next   # Move 2 steps

        if slow == fast:
            return True  # Cycle detected

    return False

Why does it work?

If a cycle exists, the fast pointer eventually catches up to the slow pointer.
If no cycle exists, fast reaches the end (NULL) first.

Understanding this O(1) space complexity cycle detection algorithm revealed the elegance of pointer manipulation.

연결 리스트(Linked List): 보물 찾기 쪽지의 비밀 (완전정복)

관련 포스트

메모리 관리: 연속 할당과 분산 할당

BFS와 DFS: 그래프 탐색의 두 축

퀵 정렬(Quick Sort): 분할 정복의 대표

Keep-Alive: 전화 끊지 말고 기다려

1. 프롤로그 - 보물 찾기 쪽지가 더 낫다고?

2. 구조의 핵심 - 노드와 포인터라는 설계

3. 조회(Read)의 비극 - 순차 접근의 한계

4. 삽입/삭제(Insert/Delete)의 기적 - 포인터 2개만 바꾸면 끝

5. 숨겨진 단점 - 메모리 파편화와 캐시 미스

6. 변형의 세계 - 원형, 이중, 센티넬

6-1. 원형 연결 리스트 (Circular Linked List)

6-2. 이중 연결 리스트 (Doubly Linked List)

6-3. 센티넬 노드 (Sentinel / Dummy Node)

7. 완전한 구현 - 파이썬 코드로 만들기

8. 실제 응용 - LRU Cache 구현

9. 현실 - 고수준 언어에서는 잘 안 쓴다

JavaScript에는 아예 없다

Java: LinkedList vs ArrayList

그럼 언제 쓰냐?

10. 시간 복잡도 비교 - 배열 vs 연결 리스트

11. 실전 문제 - 사이클 검출 (Floyd's Cycle Detection)

12. 요약 - 결국 내가 이해한 연결 리스트

Linked List: The Scavenger Hunt of Data Structures (Definitive Guide)

1. Prologue: Why Choose Scavenger Hunt Over Apartments?

2. Core Structure: Nodes and Pointers by Design

3. The Tragedy of Access: Sequential Access Limitation

4. The Miracle of Insertion/Deletion: Just Flip Two Pointers

5. Hidden Cost: Memory Fragmentation and Cache Misses

6. Variations: Circular, Doubly, Sentinel

6-1. Circular Linked List

6-2. Doubly Linked List

6-3. Sentinel Node (Dummy Node)

7. Complete Implementation: Python Code

8. Real-World Application: LRU Cache Implementation

9. Reality: Rarely Used in High-Level Languages

JavaScript Doesn't Even Have Them

Java: LinkedList vs ArrayList

So When Do We Use Them?

10. Time Complexity Comparison: Array vs Linked List

11. Practice Problem: Cycle Detection (Floyd's Algorithm)