**연결 리스트(Linked List)**는 데이터 필드와 포인터(Link) 필드를 가진 **노드(Node)**들이 동적으로 연결된 선형 자료구조입니다.
1. 단일 연결 리스트 (Singly Linked List)
각 노드가 다음 노드(next)의 참조 주소만을 가지는 형태입니다.
class SList:
class Node:
def __init__(self, item, link):
self.item = item
self.next = link
def __init__(self):
self.head = None
self.size = 0
def insert_front(self, item):
self.head = self.Node(item, self.head)
self.size += 1
def insert_after(self, item, p):
p.next = self.Node(item, p.next)
self.size += 1
def delete_front(self):
if self.size == 0:
raise IndexError("Underflow")
target = self.head
self.head = self.head.next
self.size -= 1
return target.item
2. 이중 연결 리스트 (Doubly Linked List)
각 노드가 이전 노드(prev)와 다음 노드(next) 두 개의 포인터를 가져 양방향 이동이 가능합니다.
class DList:
class Node:
def __init__(self, item, prev, link):
self.item = item
self.prev = prev
self.next = link
def __init__(self):
self.head = self.Node(None, None, None)
self.tail = self.Node(None, self.head, None)
self.head.next = self.tail
self.size = 0
def insert_before(self, p, item):
t = p.prev
n = self.Node(item, t, p)
p.prev = n
t.next = n
self.size += 1
def delete(self, x):
f = x.prev
r = x.next
f.next = r
r.prev = f
self.size -= 1
return x.item
3. 원형 연결 리스트 (Circular Linked List)
마지막 노드의 next가 리스트의 첫 번째 노드를 가리켜 고리 모양을 형성합니다.
class CList:
class Node:
def __init__(self, item, link):
self.item = item
self.next = link
def __init__(self):
self.last = None
self.size = 0
def insert(self, item):
n = self.Node(item, None)
if self.size == 0:
n.next = n
self.last = n
else:
n.next = self.last.next
self.last.next = n
self.size += 1
4. 연결 리스트 종류별 비교표
| 구분 | 단일 연결 리스트 | 이중 연결 리스트 | 원형 연결 리스트 |
|---|---|---|---|
| 포인터 수 | 노드당 1개 (next) |
노드당 2개 (prev, next) |
노드당 1개 (끝과 시작 연결) |
| 탐색 방향 | 단방향 (앞 $ | ||
| ightarrow$ 뒤) | 양방향 | 순환 지속 탐색 가능 | |
| 메모리 오버헤드 | 적음 | 포인터 2개로 약간 증가 | 적음 |
| 주 활용처 | 단순 스택/큐 구현 | Deque, LRU 캐시, 에디터 | 라운드 로빈 스케줄링 |
5. 자주 묻는 질문 (Q&A)
Q. 이중 연결 리스트에서 더미 헤드/타일(Sentinel Node)을 두는 이유는 무엇인가요?
A. 리스트가 비어있거나, 맨 앞/맨 뒤 노드를 삽입·삭제할 때 발생하는 예외 처리 조건문(if self.head is None 등)을 제거하여 코드를 간결하고 오류 없게 만듭니다.