지식
Algorithm
단일 연결 리스트
노드와 포인터로 구성된 단일 연결 리스트의 구조, 삽입·삭제·역전 알고리즘을 Python으로 직접 구현합니다.
지난 글에서 동적 배열을 구현해봤습니다. 배열은 인덱스 접근이 빠르지만 중간 삽입·삭제가 느립니다. **단일 연결 리스트(Singly Linked List)**는 이 약점을 보완하는 대표적인 자료구조입니다.
연결 리스트란
연결 리스트는 **노드(Node)**들이 포인터로 연결된 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가집니다. 배열과 달리 메모리가 연속적이지 않아도 됩니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None # 다음 노드 포인터
class SinglyLinkedList:
def __init__(self):
self.head = None # 첫 번째 노드
self.tail = None # 마지막 노드 (선택적)
self._size = 0기본 연산 구현
앞에 삽입 (prepend) — O(1)
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head # 새 노드 → 기존 head
self.head = new_node # head 갱신
if self.tail is None:
self.tail = new_node
self._size += 1뒤에 삽입 (append) — O(1) with tail pointer
def append(self, data):
new_node = Node(data)
if self.tail is None:
self.head = self.tail = new_node
else:
self.tail.next = new_node # 기존 tail → 새 노드
self.tail = new_node # tail 갱신
self._size += 1tail 포인터를 유지하지 않으면 뒤 삽입이 O(n)이 됩니다. 반드시 tail을 관리하세요.
앞 삭제 (delete head) — O(1)
def delete_head(self):
if self.head is None:
raise IndexError("빈 리스트")
data = self.head.data
self.head = self.head.next # head를 한 칸 앞으로
if self.head is None:
self.tail = None
self._size -= 1
return data뒤 삭제 — O(n): 단일 연결 리스트의 약점
def delete_tail(self):
if self.head is None:
raise IndexError("빈 리스트")
if self.head is self.tail:
data = self.head.data
self.head = self.tail = None
self._size -= 1
return data
# tail 이전 노드를 찾기 위해 전체 순회 필요 — O(n)
curr = self.head
while curr.next is not self.tail:
curr = curr.next
data = self.tail.data
curr.next = None
self.tail = curr
self._size -= 1
return data이것이 단일 연결 리스트의 핵심 단점입니다. 이전(prev) 포인터가 없어서 tail 삭제가 O(n)입니다.
리스트 역전 — O(n)
def reverse(self):
prev, curr = None, self.head
self.tail = self.head # 현재 head가 역전 후 tail
while curr:
curr.next, prev, curr = prev, curr, curr.next
self.head = prev포인터만 변경하므로 데이터 복사 없이 O(n)에 역전됩니다.
전체 구현
class SinglyLinkedList:
def __init__(self):
self.head = self.tail = None
self._size = 0
def __len__(self):
return self._size
def __iter__(self):
curr = self.head
while curr:
yield curr.data
curr = curr.next
def search(self, target): # O(n)
curr = self.head
idx = 0
while curr:
if curr.data == target:
return idx
curr = curr.next
idx += 1
return -1
def delete_value(self, val): # O(n)
if self.head is None:
return False
if self.head.data == val:
self.delete_head()
return True
curr = self.head
while curr.next:
if curr.next.data == val:
if curr.next is self.tail:
self.tail = curr
curr.next = curr.next.next
self._size -= 1
return True
curr = curr.next
return False복잡도 요약
| 연산 | 복잡도 |
|---|---|
| 앞 삽입/삭제 | O(1) |
| 뒤 삽입 (tail 유지) | O(1) |
| 뒤 삭제 | O(n) |
| 중간 삽입 (위치 알 때) | O(1) (포인터 연결만) |
| 탐색 | O(n) |
| 인덱스 접근 | O(n) |
연결 리스트가 배열보다 유리한 경우
- 앞쪽에 빈번한 삽입/삭제: 배열은 O(n) 이동이 필요하지만 연결 리스트는 O(1)
- 크기를 모를 때: 배열처럼 확장 복사 없이 노드를 그냥 추가
- 중간 위치에서 이미 노드 포인터를 가질 때: 연결만 바꾸면 O(1) 삽입
반면 배열이 유리한 경우: 인덱스 접근(O(1)), 캐시 효율이 중요한 순차 처리.
실전 응용
# 연결 리스트로 스택 구현 (배열 대비 앞 push가 O(1))
class Stack:
def __init__(self):
self.list = SinglyLinkedList()
def push(self, val):
self.list.prepend(val) # O(1)
def pop(self):
return self.list.delete_head() # O(1)
def peek(self):
return self.list.head.data
# Python의 deque는 이중 연결 리스트로 구현
from collections import deque
dq = deque()
dq.appendleft(1) # O(1)
dq.popleft() # O(1)정리
- 단일 연결 리스트 = 노드(data + next 포인터)의 체인
- head 포인터로 시작, tail 포인터 유지 시 뒤 삽입 O(1)
- 앞 삽입/삭제 O(1) vs 뒤 삭제/탐색 O(n)
- 역전은 포인터만 변경 — O(n), 공간 O(1)
지난 글: 동적 배열
다음 글: 이중 연결 리스트
읽어주셔서 감사합니다. 😊