연결 리스트 핸드북
1. 생성 배경 및 의의
연결 리스트는 배열처럼 연속적 메모리에 의존하지 않고, 노드(node) 간 포인터로만 연결되어 유연한 삽입·삭제를 가능하게 하기 위해 개발되었다1. 1953년 피터 런(Peter Luhn)이 최초로 현대적 형태의 체이닝 해시 테이블에 도입했고, 이후 1955–56년 RAND 연구소에서 정보 처리 언어(IPL) 설계 시 주요 자료구조로 활용되며 대중화되었다2.
2. 구조
연결 리스트는 노드의 연쇄로 구성된다3:
- 각 노드는 데이터(
data)와 다음 노드를 가리키는 포인터(next)를 포함 - 리스트 시작 지점을 가리키는 헤드(head) 포인터
- 마지막 노드의
next는NULL로 종료 표시
struct Node {
int data; // 데이터
struct Node *next; // 다음 노드 주소
};3. 종류
| 형태 | 설명 |
|---|---|
| 단일 연결 리스트 (Singly Linked List) | 한 방향(다음)으로만 연결된 가장 기본적인 형태4. |
| 이중 연결 리스트 (Doubly Linked List) | 앞·뒤 두 방향으로 연결되어 양방향 탐색 가능4. |
| 원형 연결 리스트 (Circular Linked List) | 마지막 노드가 첫 노드를 가리켜 순환 구조를 형성4. |
| 다중 레벨 리스트 (Multilevel Linked List) | 노드당 자식 리스트를 가리키는 포인터 추가로 계층적 구조 지원4. |
| 스킵 리스트 (Skip List) | 여러 레벨 포인터로 탐색 속도 향상(확률적 구조)4. |
4. 주요 연산 및 시간 복잡도
연결 리스트의 기본 연산과 시간·공간 복잡도는 다음과 같다56:
| 연산 | 시간 복잡도 | 공간 복잡도 |
|---|---|---|
| 추가(앞) | O(1) | O(1) |
| 추가(끝) | O(n) | O(1) |
| 삭제(앞) | O(1) | O(1) |
| 삭제(끝) | O(n) | O(1) |
| 특정 위치 삽입/삭제 | O(n) | O(1) |
| 탐색(Search) | O(n) | O(1) |
- 순회(Traversal): 모든 노드 방문, O(n)
- 삽입(Insert): 위치에 따라 O(1)~O(n)
- 삭제(Delete): 위치에 따라 O(1)~O(n)
- 탐색(Search): 원하는 값 찾기까지 최대 O(n)
5. 장·단점
장점
- 동적 크기 조정 가능, 빈틈없이 메모리 활용
- 중간 삽입·삭제 시 포인터만 업데이트해 O(1) 달성
- 스택·큐·그래프 인접 리스트 등 다양한 자료구조 구현 기반1
단점
- 임의 인덱스 접근 불가, 순차 탐색만 가능
- 포인터 오버헤드로 메모리 사용량 증가
- 캐시 현지성(cache locality) 낮음
6. 활용 사례
- 자료구조 구현: 스택, 큐, 덱, 해시 테이블 체이닝
- 그래프 표현: 인접 리스트
- 메모리 관리: OS의 빈 블록 리스트
- 실생활 응용: 웹 브라우저 이전/다음 페이지, 음악 플레이어 재생 리스트7
핸드북 형태로 연결 리스트의 개념, 구조, 종류, 연산 및 활용을 종합적으로 정리하였다.
파이썬 코드
class Node:
"""
연결 리스트의 노드 클래스.
data: 노드가 저장하는 값
next: 다음 노드를 가리키는 포인터
"""
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
"""
단일 연결 리스트 클래스.
head: 리스트의 첫 노드를 가리키는 포인터
"""
def __init__(self):
self.head = None
def is_empty(self):
"""리스트가 비어 있는지 확인"""
return self.head is None
def prepend(self, data):
"""
리스트 맨 앞에 새 노드 추가
시간 복잡도: O(1)
"""
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def append(self, data):
"""
리스트 맨 뒤에 새 노드 추가
시간 복잡도: O(n)
"""
new_node = Node(data)
if self.is_empty():
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def find(self, key):
"""
키 값이 첫 등장하는 노드를 반환. 없으면 None 반환
시간 복잡도: O(n)
"""
current = self.head
while current:
if current.data == key:
return current
current = current.next
return None
def delete(self, key):
"""
첫 번째로 찾은 키 값을 갖는 노드를 삭제
시간 복잡도: O(n)
"""
current = self.head
prev = None
while current and current.data != key:
prev = current
current = current.next
if current is None:
return False # 키 없음
if prev is None:
# 삭제할 노드가 헤드인 경우
self.head = current.next
else:
prev.next = current.next
return True
def __iter__(self):
"""이터레이터 지원: for node in linked_list"""
current = self.head
while current:
yield current.data
current = current.next
def __repr__(self):
"""리스트 전체를 문자열로 표현"""
return "->".join(str(data) for data in self)
# 사용 예시
if __name__ == "__main__":
ll = LinkedList()
ll.append(10)
ll.prepend(5)
ll.append(15)
print("리스트 내용:", ll) # 출력: 리스트 내용: 5->10->15
print("찾기(10):", ll.find(10)) # 출력: Node 객체 (data=10)
ll.delete(10)
print("삭제 후:", ll) # 출력: 삭제 후: 5->15
⁂