이중 연결 리스트

Q: 단일 연결 리스트와 이중 연결 리스트의 차이는 무엇인가요?

단일 연결 리스트는 노드마다 포인터가 하나(`next`)라서 앞으로만 이동할 수 있습니다. 이중 연결 리스트는 `prev` 포인터를 추가하여 역방향 순회와, 참조를 가진 노드의 `O(1)` 삭제를 가능하게 합니다. 그 대가로 노드마다 포인터가 하나 더 늘고 변경 때마다 두 개의 링크를 갱신해야 합니다.

Q: 이중 연결 리스트가 추가 메모리를 감수할 만한 때는 언제인가요?

역방향 순회나, 이미 참조하는 임의 노드의 `O(1)` 삭제가 필요할 때입니다. 대표적인 예는 덱(양방향 큐)과 LRU 캐시로, 항목이 양쪽 끝에서 자주 옮겨지고 밀려납니다.

Q: 이중 연결 리스트와 배열 중 무엇을 사용해야 하나요?

인덱스로 `O(1)` 접근과 캐시 친화적인 반복이 필요하고 삽입이 주로 끝에서 일어난다면 배열을 사용하세요. 노드 참조를 가진 채 중간이나 양쪽 끝에 자주 삽입/삭제한다면 이중 연결 리스트를 사용하세요. 이는 배열의 `O(n)` 이동에 비해 `O(1)`이기 때문입니다. 배열은 메모리와 지역성에서 유리하고, 리스트는 구조적 편집에서 유리합니다.

Q: 이중 연결 리스트에서 삭제할 때 가장 흔한 버그는 무엇인가요?

첫 번째나 마지막 노드를 삭제할 때 `head`나 `tail` 갱신을 잊어, 해제된 노드를 가리키는 댕글링 포인터가 남는 것입니다. 이웃을 다시 연결하기 전에 `node.prev`가 `null`인지(`head` 갱신), `node.next`가 `null`인지(`tail` 갱신) 항상 확인하세요.

마지막 업데이트 2026년 7월 1일

이중 연결 리스트는 각 노드가 두 개의 포인터를 갖는 연결 리스트입니다: next(다음 노드로)와 prev(이전 노드로). 이 추가된 역방향 링크 덕분에 양방향으로 순회할 수 있고, 이미 참조를 가지고 있는 노드는 O(1)에 삭제할 수 있습니다. 머리부터 걸어가지 않고 그 앞 노드에 곧바로 도달할 수 있기 때문입니다. 위의 재생 버튼을 눌러 노드가 양방향으로 연결되고 다시 연결되는 모습을 확인하세요.

그 비용은 노드마다 포인터 하나가 더 필요하고 관리 부담이 커진다는 점입니다. 모든 삽입과 삭제는 이웃 노드의 next와 prev를 모두 갱신해야 합니다. 이는 양쪽 끝에서의 빠른 제거가 중요한 여러 덱(deque)과 LRU 캐시의 바탕이 되는 구조입니다.

시간 복잡도

연산	복잡도	비고
머리/꼬리에 삽입	O(1)	머리와 꼬리 포인터가 있을 때
알려진 노드 삭제	O(1)	prev에 직접 도달, 순회 없음
검색	O(n)	여전히 선형 탐색
인덱스로 접근	O(n)	임의 접근 불가

단일 연결 리스트와 이중 연결 리스트 비교

측면	단일	이중
노드당 포인터	1 (next)	2 (next + prev)
역방향 순회	불가	가능
알려진 노드 삭제	O(n) (prev 찾기)	O(1)
메모리 오버헤드	더 낮음	더 높음

예제 풀이

뒤에 추가하여 [10, 20, 30]을 만든 뒤 노드 20을 삭제하기:

단계	구조	동작
시작	`null`	빈 리스트: `head`와 `tail` 모두 `null`
10 추가	`10`	첫 노드; `head`와 `tail`이 이를 가리키고 `prev` = `next` = `null`
20 추가	`10 <-> 20`	`10.next = 20`과 `20.prev = 10` 설정; `tail` = `20`
30 추가	`10 <-> 20 <-> 30`	`20.next = 30`과 `30.prev = 20` 설정; `tail` = `30`
20 삭제	`10 <-> 30`	`20.prev`와 `20.next`를 사용해 `10.next = 30`과 `30.prev = 10`을 `O(1)`에 설정

이중 연결 리스트를 사용할 때

사용할 때	피할 때
양방향으로 순회하거나 이어 붙여야 할 때	앞으로만 이동할 때: 단일 리스트가 더 가볍다
이미 참조를 가진 임의의 노드를 삭제할 때 (`O(1)`)	주로 위치로 인덱싱할 때: `O(1)` 접근에는 배열을 사용하라
덱, LRU 캐시, 실행 취소 기록을 구현할 때	메모리가 빠듯할 때: 추가 `prev` 포인터가 링크 오버헤드를 두 배로 만든다
삽입과 제거가 양쪽 끝에서 자주 일어날 때	데이터가 작고 거의 바뀌지 않을 때: 배열 복사가 더 저렴하다

Doubly Linked List 코드

Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Doubly Linked List 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.

Python로 구현한 Doubly Linked List 코드Python
1class Node:2    def __init__(self, value):3        self.value = value4        self.prev = None5        self.next = None6
7
8class DoublyLinkedList:9    def __init__(self):10        self.head = None11        self.tail = None12
13    def append(self, value):14        node = Node(value)15        if self.tail is None:16            self.head = self.tail = node17            return18        # Wire both directions: old tail <-> new node19        node.prev = self.tail20        self.tail.next = node21        self.tail = node22
23    def prepend(self, value):24        node = Node(value)25        if self.head is None:26            self.head = self.tail = node27            return28        node.next = self.head29        self.head.prev = node30        self.head = node31
32    def forward(self):33        values, current = [], self.head34        while current:35            values.append(current.value)36            current = current.next37        return values38
39    def backward(self):40        values, current = [], self.tail41        while current:42            values.append(current.value)43            current = current.prev44        return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49    lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())
이 코드를 Python 플레이그라운드에서 실행하기

JavaScript로 구현한 Doubly Linked List 코드JavaScript
1class Node {2    constructor(value) {3        this.value = value;4        this.prev = null;5        this.next = null;6    }7}8
9class DoublyLinkedList {10    constructor() {11        this.head = null;12        this.tail = null;13    }14
15    // Tail pointer makes append O(1)16    append(value) {17        const node = new Node(value);18        if (!this.tail) {19            this.head = node;20            this.tail = node;21            return;22        }23        node.prev = this.tail;24        this.tail.next = node;25        this.tail = node;26    }27
28    forward() {29        const out = [];30        for (let n = this.head; n; n = n.next) out.push(n.value);31        return out;32    }33
34    backward() {35        const out = [];36        for (let n = this.tail; n; n = n.prev) out.push(n.value);37        return out;38    }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));
이 코드를 JavaScript 플레이그라운드에서 실행하기

Java로 구현한 Doubly Linked List 코드Java
1public class Main {2    static class Node {3        int value;4        Node prev, next;5        Node(int value) { this.value = value; }6    }7
  static Node head, tail;9
  static void append(int value) {11        Node node = new Node(value);12        if (head == null) { head = tail = node; return; }13        node.prev = tail;14        tail.next = node;15        tail = node;16    }17
  // Unlink in O(1) once found: fix both neighbor pointers19    static void delete(int value) {20        for (Node cur = head; cur != null; cur = cur.next) {21            if (cur.value != value) continue;22            if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23            if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24            return;25        }26    }27
  public static void main(String[] args) {29        append(1);30        append(2);31        append(3);32        append(4);33
      StringBuilder forward = new StringBuilder("Forward:");35        for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36        System.out.println(forward);37
      StringBuilder backward = new StringBuilder("Backward:");39        for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40        System.out.println(backward);41
      delete(3);43        StringBuilder after = new StringBuilder("After delete 3:");44        for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45        System.out.println(after);46    }47}
이 코드를 Java 플레이그라운드에서 실행하기

C++로 구현한 Doubly Linked List 코드C++
1#include <iostream>2
3struct Node {4    int value;5    Node* prev = nullptr;6    Node* next = nullptr;7    explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11    Node* head = nullptr;12    Node* tail = nullptr;13
14    void append(int value) {15        Node* node = new Node(value);16        if (tail == nullptr) {17            head = tail = node;18            return;19        }20        node->prev = tail;  // link both directions21        tail->next = node;22        tail = node;23    }24
25    void prepend(int value) {26        Node* node = new Node(value);27        if (head == nullptr) {28            head = tail = node;29            return;30        }31        node->next = head;32        head->prev = node;33        head = node;34    }35
36    void printForward() const {37        for (Node* cur = head; cur != nullptr; cur = cur->next) {38            std::cout << cur->value << " <-> ";39        }40        std::cout << "null\n";41    }42
43    void printBackward() const {44        for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45            std::cout << cur->value << " <-> ";46        }47        std::cout << "null\n";48    }49};50
51int main() {52    DoublyLinkedList list;53    for (int value : {10, 20, 30}) list.append(value);54    list.prepend(5);55    std::cout << "Forward:  ";56    list.printForward();57    std::cout << "Backward: ";58    list.printBackward();59    return 0;60}
이 코드를 C++ 플레이그라운드에서 실행하기

C로 구현한 Doubly Linked List 코드C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5    int value;6    struct Node* prev;7    struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14    Node* n = calloc(1, sizeof(Node));15    n->value = value;16    return n;17}18
19void append(int value) {20    Node* node = newNode(value);21    if (tail == NULL) {22        head = tail = node;23        return;24    }25    node->prev = tail;  // link both directions26    tail->next = node;27    tail = node;28}29
30void prepend(int value) {31    Node* node = newNode(value);32    if (head == NULL) {33        head = tail = node;34        return;35    }36    node->next = head;37    head->prev = node;38    head = node;39}40
41void printForward(void) {42    for (Node* cur = head; cur != NULL; cur = cur->next) {43        printf("%d <-> ", cur->value);44    }45    printf("NULL\n");46}47
48void printBackward(void) {49    for (Node* cur = tail; cur != NULL; cur = cur->prev) {50        printf("%d <-> ", cur->value);51    }52    printf("NULL\n");53}54
55int main(void) {56    int values[] = {10, 20, 30};57    for (int i = 0; i < 3; i++) append(values[i]);58    prepend(5);59    printf("Forward:  ");60    printForward();61    printf("Backward: ");62    printBackward();63    return 0;64}
이 코드를 C 플레이그라운드에서 실행하기

이중 연결 리스트 FAQ

단일 연결 리스트와 이중 연결 리스트의 차이는 무엇인가요?

단일 연결 리스트는 노드마다 포인터가 하나(next)라서 앞으로만 이동할 수 있습니다. 이중 연결 리스트는 prev 포인터를 추가하여 역방향 순회와, 참조를 가진 노드의 O(1) 삭제를 가능하게 합니다. 그 대가로 노드마다 포인터가 하나 더 늘고 변경 때마다 두 개의 링크를 갱신해야 합니다.

이중 연결 리스트가 추가 메모리를 감수할 만한 때는 언제인가요?

역방향 순회나, 이미 참조하는 임의 노드의 O(1) 삭제가 필요할 때입니다. 대표적인 예는 덱(양방향 큐)과 LRU 캐시로, 항목이 양쪽 끝에서 자주 옮겨지고 밀려납니다.

이중 연결 리스트가 노드를 O(1)에 삭제할 수 있는 이유는 무엇인가요?

노드를 제거하려면 그 앞 노드를 뒤 노드에 이어 붙여야 합니다. 단일 연결 리스트에서는 앞 노드를 찾으려고 머리부터 걸어가야 하지만(O(n)), 이중 연결 리스트에서는 노드의 prev 포인터가 앞 노드를 곧바로 알려주므로 다시 연결하는 작업이 O(1)입니다.

이중 연결 리스트와 배열 중 무엇을 사용해야 하나요?

인덱스로 O(1) 접근과 캐시 친화적인 반복이 필요하고 삽입이 주로 끝에서 일어난다면 배열을 사용하세요. 노드 참조를 가진 채 중간이나 양쪽 끝에 자주 삽입/삭제한다면 이중 연결 리스트를 사용하세요. 이는 배열의 O(n) 이동에 비해 O(1)이기 때문입니다. 배열은 메모리와 지역성에서 유리하고, 리스트는 구조적 편집에서 유리합니다.

이중 연결 리스트의 센티넬(sentinel) 노드란 무엇인가요?

센티넬(또는 더미) 노드는 리스트가 결코 진짜로 비지 않도록 머리 앞이나 꼬리 뒤에 두는 자리 표시자입니다. head, tail, 경계에서의 삽입/삭제에 대한 null 검사를 없애 모든 연산이 동일한 재연결 코드 경로를 따르게 합니다. 많은 실제 LRU 캐시 구현은 양 끝을 특수 처리하지 않으려고 센티넬을 두 개 사용합니다.

이중 연결 리스트에서 삭제할 때 가장 흔한 버그는 무엇인가요?

첫 번째나 마지막 노드를 삭제할 때 head나 tail 갱신을 잊어, 해제된 노드를 가리키는 댕글링 포인터가 남는 것입니다. 이웃을 다시 연결하기 전에 node.prev가 null인지(head 갱신), node.next가 null인지(tail 갱신) 항상 확인하세요.