연결 리스트
마지막 업데이트
연결 리스트는 시퀀스를 노드들의 사슬로 저장하며, 각 노드는 값과 다음 노드를 가리키는 포인터를 담습니다. 배열과 달리 노드들은 메모리에서 연속적이지 않으며, 리스트를 따라가려면 next 포인터를 따라갑니다. 위의 재생을 눌러 노드가 앞과 뒤에서 연결되고, 사슬을 따라가며 값이 탐색되고, 포인터를 다시 연결하여 노드가 제거되는 모습을 지켜보세요.
앞에서의 삽입이나 삭제는 헤드만 다시 가리키면 되므로 O(1)입니다. 중간의 위치나 끝에 도달하는 것은 먼저 그곳까지 걸어가야 하므로 O(n)입니다. 이 절충점(양 끝은 저렴하지만 임의 접근이 없음)이 연결 리스트를 배열과 구별짓는 특징입니다.
시간 복잡도
| 연산 | 복잡도 | 비고 |
|---|---|---|
| 앞에 삽입 | O(1) | 헤드를 다시 가리킴 |
| 뒤에 삽입 | O(n) | 먼저 끝까지 걸어감 (꼬리 포인터가 있으면 O(1)) |
| 탐색 | O(n) | next 포인터를 따라감 |
| 헤드 삭제 | O(1) | 헤드를 그 너머로 다시 가리킴 |
| 인덱스로 접근 | O(n) | 임의 접근 없음 |
연결 리스트 대 배열
| 측면 | 연결 리스트 | 배열 |
|---|---|---|
| 메모리 | 흩어진 노드 + 포인터 | 연속된 블록 |
| 임의 접근 | O(n) | O(1) |
| 앞에서 삽입/삭제 | O(1) | O(n) (이동) |
| 캐시 친화성 | 나쁨 | 좋음 |
풀이 예제
리스트 [10, 20]를 만들고, 5를 앞에 붙인 다음, 20을 삭제하기:
| 단계 | 구조 | 동작 |
|---|---|---|
| 시작 | head -> null | 빈 리스트 |
| 앞에 10 삽입 | head -> 10 -> null | next가 이전 헤드(null)인 새 노드로 헤드를 다시 가리킴 |
| 뒤에 20 삽입 | head -> 10 -> 20 -> null | 노드 10까지 걸어가 그 next를 새 노드 20으로 설정 |
| 앞에 5 삽입 | head -> 5 -> 10 -> 20 -> null | 새 노드 5가 이전 헤드 10을 가리키고, 헤드는 이제 5를 가리킴 |
| 20 삭제 | head -> 5 -> 10 -> null | 10까지 걸어가 그 next를 20에서 null로 설정; 노드 20은 연결이 끊김 |
연결 리스트를 사용할 때
| 사용할 때 | 피해야 할 때 |
|---|---|
| 인덱싱보다 양 끝(또는 이미 쥐고 있는 노드)에서 삽입하거나 삭제하는 일이 훨씬 많을 때 | 위치별 빠른 임의 접근(O(1) 인덱싱)이 필요할 때 |
| 크기가 많이 변하고 크기 조정/복사 비용을 원하지 않을 때 | 캐시 지역성이 성능을 좌우하는 촘촘한 루프를 돌 때 |
| 큐, 스택 또는 인접 리스트를 구축할 때 | 메모리가 빠듯할 때 - 각 노드는 요소마다 추가 포인터 비용을 치름 |
| 다른 곳에서의 삽입에도 살아남는 노드에 대한 안정적인 참조가 필요할 때 | 주로 읽고 거의 수정하지 않아 배열이 더 단순하고 빠를 때 |
Linked List 코드
Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Linked List 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.
Python로 구현한 Linked List 코드
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.next = None5
6
7class LinkedList:8 def __init__(self):9 self.head = None10
11 def append(self, value):12 node = Node(value)13 if self.head is None:14 self.head = node15 return16 current = self.head17 while current.next:18 current = current.next19 current.next = node20
21 def find(self, value):22 current = self.head23 while current:24 if current.value == value:25 return True26 current = current.next27 return False28
29 def delete(self, value):30 # Re-link the previous node around the match31 current, prev = self.head, None32 while current:33 if current.value == value:34 if prev is None:35 self.head = current.next36 else:37 prev.next = current.next38 return True39 prev, current = current, current.next40 return False41
42 def __str__(self):43 values, current = [], self.head44 while current:45 values.append(str(current.value))46 current = current.next47 return " -> ".join(values) + " -> None"48
49
50lst = LinkedList()51for value in [3, 7, 1, 9]:52 lst.append(value)53
54print("List: ", lst)55print("find(7): ", lst.find(7))56lst.delete(1)57print("After delete(1):", lst)JavaScript로 구현한 Linked List 코드
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6}7
8class LinkedList {9 constructor() {10 this.head = null;11 }12
13 append(value) {14 const node = new Node(value);15 if (!this.head) {16 this.head = node;17 return;18 }19 let current = this.head;20 while (current.next) current = current.next;21 current.next = node;22 }23
24 find(value) {25 for (let n = this.head; n; n = n.next) {26 if (n.value === value) return n;27 }28 return null;29 }30
31 delete(value) {32 if (!this.head) return false;33 if (this.head.value === value) {34 this.head = this.head.next;35 return true;36 }37 // Walk to the node just before the one to remove38 for (let n = this.head; n.next; n = n.next) {39 if (n.next.value === value) {40 n.next = n.next.next;41 return true;42 }43 }44 return false;45 }46
47 toArray() {48 const out = [];49 for (let n = this.head; n; n = n.next) out.push(n.value);50 return out;51 }52}53
54const list = new LinkedList();55for (const value of [10, 20, 30, 40]) list.append(value);56console.log("List:", list.toArray().join(" -> "));57console.log("find(30):", list.find(30) !== null);58list.delete(20);59console.log("After delete(20):", list.toArray().join(" -> "));Java로 구현한 Linked List 코드
Java
1public class Main {2 static class Node {3 int value;4 Node next;5 Node(int value) { this.value = value; }6 }7
8 static Node head;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = node; return; }13 Node cur = head;14 while (cur.next != null) cur = cur.next;15 cur.next = node;16 }17
18 static boolean find(int value) {19 for (Node cur = head; cur != null; cur = cur.next) {20 if (cur.value == value) return true;21 }22 return false;23 }24
25 // Unlink the first node holding value26 static void delete(int value) {27 if (head == null) return;28 if (head.value == value) { head = head.next; return; }29 Node cur = head;30 while (cur.next != null && cur.next.value != value) cur = cur.next;31 if (cur.next != null) cur.next = cur.next.next;32 }33
34 static void print() {35 StringBuilder sb = new StringBuilder();36 for (Node cur = head; cur != null; cur = cur.next) {37 sb.append(cur.value).append(" -> ");38 }39 System.out.println(sb.append("null"));40 }41
42 public static void main(String[] args) {43 append(3); append(7); append(1); append(9);44 print();45 System.out.println("find 7: " + find(7));46 delete(7);47 print();48 System.out.println("find 7: " + find(7));49 }50}C++로 구현한 Linked List 코드
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* next = nullptr;6 explicit Node(int v) : value(v) {}7};8
9struct LinkedList {10 Node* head = nullptr;11
12 void append(int value) {13 Node* node = new Node(value);14 if (head == nullptr) {15 head = node;16 return;17 }18 Node* cur = head;19 while (cur->next != nullptr) cur = cur->next;20 cur->next = node;21 }22
23 bool find(int value) const {24 for (Node* cur = head; cur != nullptr; cur = cur->next) {25 if (cur->value == value) return true;26 }27 return false;28 }29
30 void remove(int value) {31 if (head == nullptr) return;32 if (head->value == value) { // removing the head is a special case33 Node* old = head;34 head = head->next;35 delete old;36 return;37 }38 for (Node* cur = head; cur->next != nullptr; cur = cur->next) {39 if (cur->next->value == value) {40 Node* old = cur->next;41 cur->next = old->next;42 delete old;43 return;44 }45 }46 }47
48 void print() const {49 for (Node* cur = head; cur != nullptr; cur = cur->next) {50 std::cout << cur->value << " -> ";51 }52 std::cout << "null\n";53 }54};55
56int main() {57 LinkedList list;58 for (int value : {10, 20, 30, 40}) list.append(value);59 list.print();60 std::cout << std::boolalpha << "find(30): " << list.find(30) << "\n";61 list.remove(20);62 list.remove(10);63 list.print();64 return 0;65}C로 구현한 Linked List 코드
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* next;8} Node;9
10Node* head = NULL;11
12void append(int value) {13 Node* node = malloc(sizeof(Node));14 node->value = value;15 node->next = NULL;16 if (head == NULL) {17 head = node;18 return;19 }20 Node* cur = head;21 while (cur->next != NULL) cur = cur->next;22 cur->next = node;23}24
25bool find(int value) {26 for (Node* cur = head; cur != NULL; cur = cur->next) {27 if (cur->value == value) return true;28 }29 return false;30}31
32void deleteValue(int value) {33 if (head == NULL) return;34 if (head->value == value) { // removing the head is a special case35 Node* old = head;36 head = head->next;37 free(old);38 return;39 }40 for (Node* cur = head; cur->next != NULL; cur = cur->next) {41 if (cur->next->value == value) {42 Node* old = cur->next;43 cur->next = old->next;44 free(old);45 return;46 }47 }48}49
50void printList(void) {51 for (Node* cur = head; cur != NULL; cur = cur->next) {52 printf("%d -> ", cur->value);53 }54 printf("NULL\n");55}56
57int main(void) {58 int values[] = {10, 20, 30, 40};59 for (int i = 0; i < 4; i++) append(values[i]);60 printList();61 printf("find(30): %s\n", find(30) ? "true" : "false");62 deleteValue(20);63 deleteValue(10);64 printList();65 return 0;66}연결 리스트 자주 묻는 질문
연결 리스트와 배열의 차이는 무엇인가요?
배열은 요소를 하나의 연속된 블록에 저장하여
O(1) 임의 접근을 제공하지만, 요소를 이동시키는 삽입/삭제는 O(n)입니다. 연결 리스트는 노드를 메모리 어디에나 포인터로 연결하여 저장하므로 알려진 위치에서의 삽입/삭제는 O(1)이지만, 사슬을 따라가야 하므로 접근은 O(n)입니다.언제 연결 리스트를 사용해야 하나요?
연결 리스트는 양 끝(또는 이미 참조를 쥐고 있는 노드)에서 자주 삽입하거나 제거하고 임의 접근이 거의 필요 없을 때, 예를 들어 큐, 스택, 인접 리스트, LRU 캐시에서 빛을 발합니다. 빠른 인덱스 접근이 필요하다면 배열이나 동적 배열이 대개 더 낫습니다.
연결 리스트의 시간 복잡도는 어떻게 되나요?
헤드에서의 삽입이나 삭제는
O(1)입니다. 탐색, 또는 꼬리 포인터 없이 끝에 도달하는 것은 next 포인터를 하나씩 따라가므로 O(n)입니다. O(1) 임의 접근은 없습니다. 연결 리스트를 인덱싱하는 것은 O(n)입니다.단일 연결 리스트와 이중 연결 리스트의 차이는 무엇인가요?
단일 연결 리스트는 노드마다
next 포인터만 저장하므로 한 방향으로만 갈 수 있고, 노드를 삭제하려면 그 앞 노드에 대한 참조가 필요합니다. 이중 연결 리스트는 prev 포인터를 추가하여 뒤로의 순회와 쥐고 있는 노드의 O(1) 삭제를 가능하게 하지만, 노드마다 추가 포인터와 모든 삽입·삭제 시 더 많은 관리 비용이 듭니다.앞에 삽입하는 것이 O(1)인데 왜 뒤에 삽입하는 것은 O(n)인가요?
앞에 삽입하는 것은
head 포인터만 다시 연결하므로 상수 작업입니다. 끝에 도달하려면 헤드에서 끝까지 next 포인터를 따라가야 하므로 O(n)입니다. 별도의 tail 포인터를 유지하면 뒤에 삽입하는 것도 O(1)이 되므로, 실제 리스트는 종종 양 끝을 모두 추적합니다.연결 리스트는 어디서나 O(1) 삽입이 가능한가요?
아니요, 그것은 흔한 오해입니다. 삽입 자체는 삽입할 위치의 앞 노드에 대한 포인터를 이미 쥐고 있을 때만
O(1)입니다. 그 위치를 값이나 인덱스로 찾는 것은 그곳에 도달하기 위해 사슬을 따라가야 하므로 여전히 O(n)이 듭니다.관련 자료
더 많은 시각화
