- 메모리 비연속: 각 노드가 메모리 어디에나 위치할 수 있다
- 삽입/삭제: 포인터만 변경하면 되므로 위치를 알면 \(O(1)\)
- 탐색: 처음부터 순서대로 따라가야 하므로 \(O(N)\)
- 단방향(Singly), 양방향(Doubly), 원형(Circular) 연결 리스트가 있다
- 연결 리스트는 각 노드가 한 줄로 연결되어 있는 자료 구조다.
- 각 노드는 (데이터, 포인터) 형태를 가진다.
- 포인터: 다음 노드의 메모리 주소를 가리키는 목적으로 사용된다.
- 연결성: 각 노드의 포인터는 다음 혹은 이전 노드를 가리킨다.
- 연결 리스트를 이용하면 다양한 자료구조를 구현할 수 있다.
- 예시) 스택, 큐 등을 구현 가능
- Python은 연결 리스트를 활용하는 자료구조를 제공한다.
- 연결 리스트를 실제 구현해야 하는 경우는 적지만, 그 원리 이해는 자료 구조와 클래스를 작성하는데 도움이 된다.
- 삽입과 삭제가 \(O(1)\) 에 가능하여 잦은 변경이 필요한 데이터 관리에 유리하다.
- 크기를 미리 정하지 않아도 되므로 동적 메모리 관리에 적합하다.
- 스택, 큐, 덱 등 다양한 자료구조의 내부 구현 기반이 된다.
- 포인터 기반 구조를 이해하면 파이썬 내부 동작 원리를 파악하는 데 도움이 된다.
- 연결 리스트와 배열(array)을 비교하여 장단점을 이해할 필요가 있다.
- 특정 위치의 데이터를 삭제할 때, 일반적인 배열에서는 \(O(N)\) 만큼의 시간이 소요된다.
- 하지만, 연결 리스트를 이용하면 단순히 연결만 끊어주면 된다.
- 따라서 삭제할 위치를 정확히 알고 있는 경우 \(O(1)\) 의 시간이 소요된다.
- 하지만 삭제할 위치를 정확히 알아내기 위해 앞의 코드를 자세히 보게 되는 소요 시간이 증가할 수 있다.
- 배열에 새로운 원소를 삽입할 때, 최악의 경우 시간 복잡도를 계산하여라.
- 예시) 배열에서 인덱스 3에 원소 “59”를 삽입할 경우, 인덱스 4 이후의 공간에 있는 데이터를 한칸씩 밀어내는 \(O(n)\) 만큼 소요
- 배열에 존재하는 원소를 삭제할 때, 최악의 경우 시간 복잡도를 계산하여라.
- 예시) 배열에서 인덱스 3에 해당하는 원소를 삭제한 후 데이터를 한칸 씩 당겨 이동 시키는 \(O(n)\) 만큼 소요
- 따라서, 최악의 경우 시간 복잡도는 \(O(N)\) 이다.
- 삽입할 위치를 알고 있다면, 물리적인 위치를 한 칸씩 옮기지 않아도 삽입할 수 있다.
- 인덱스 2의 위치에 원소를 삽입할 경우 인덱스 1의 Node에서 인덱스 2에 위치할 데이터를 가리키고 인덱스 2의 node가 인덱스 3의 node를 가리키도록 만들면 된다.
- 삭제할 위치를 알고 을 경우 연결 리스트 사용
- 인덱스 2의 위치에 원소를 삭제할 경우 인덱스 1의 Node가 인덱스 3의 node를 가리키게 만들면 됨
- 뒤에 붙일 때는 남는 공간에 마지막 노드의 다음 위치에 원소를 할당 시키면 된다.
- 마지막 위치에 새로운 원소를 추가
append는 마지막 노드까지 순회 후 추가하므로 \(O(N)\)이다. 꼬리(tail) 포인터를 유지하면 \(O(1)\)로 개선된다.search(index)는 head부터 index번 이동하므로 \(O(N)\)이다.insert(0, data)는 head를 교체하므로 \(O(1)\)이다. 중간 삽입은 search가 선행되어 \(O(N)\)이다.- Python에서 직접 구현할 일은 드물지만,
collections.deque가 내부적으로 이중 연결 리스트다. - 운영체제 메모리 관리: 가용 메모리 블록을 연결 리스트로 관리하여 동적 할당을 처리한다.
- 실행 취소(Undo) 기능: 편집 이력을 연결 리스트로 저장하여 이전 상태로 되돌린다.
- 해시 테이블 충돌 처리: 같은 해시값을 가진 원소를 연결 리스트(체이닝)로 관리한다.
- 덱(Deque) 구현: 양방향 연결 리스트로 양쪽 끝 삽입/삭제를 \(O(1)\) 에 처리한다.
- LRU 캐시: 최근 사용 순서를 연결 리스트로 관리하여 \(O(1)\) 캐시 교체를 구현한다.
1 개요
정의: 연결 리스트 (Linked List)
연결 리스트는 각 노드가 (데이터 + 다음 노드의 주소) 쌍으로 구성되어 포인터로 연결된 자료구조다.
직관적 이해: 기차 편성과 같다. 각 객차(노드)는 앞뒤 객차와 연결 고리(포인터)로 이어져 있다. 중간에 객차를 추가하려면 연결 고리만 바꾸면 되고, 물리적으로 이동할 필요가 없다. 반면 5번째 객차를 찾으려면 1번부터 순서대로 따라가야 한다.
메모리 구조 (비연속 할당):
노드1 노드2 노드3
┌────┬────┐ ┌────┬────┐ ┌────┬────┐
│ 3 │ ──┼─→│ 5 │ ──┼─→│ 9 │None│
└────┴────┘ └────┴────┘ └────┴────┘
주소:0x100 주소:0x340 주소:0x520
(data)(next) (data)(next) (data)(next)각 노드의 메모리 주소는 불연속적이다. next 포인터가 다음 노드의 주소를 직접 가리킨다.
2 왜 필요한가
3 연결 리스트(Linked List) vs. 배열(Array)
3.1 배열의 삽입 연산
3.2 배열의 삭제 연산
3.3 연결 리스트(Linked List)의 삽입(Insert) 연산
3.4 연결 리스트(Linked List)의 삭제(Delete) 연산
3.5 연결 리스트(Linked List)의 붙이기(Append) 연산
아래 코드는 Python 클래스로 단방향 연결 리스트를 직접 구현하며, 추가(append), 삽입(insert), 삭제(remove), 조회(search) 연산을 포함한다.
#| message: false
#| code-fold: true
class Node:
def __init__(self, data):
self.data = data # 데이터 할당
self.next = None # 다음 노드
class LinkedList:
def __init__(self):
self.head = None # 첫 번째 node
# 가장 뒤에 노드 삽입
def append(self, data):
if self.head == None: # 헤드(head)가 비어있는 경우
self.head = Node(data)
return
currrent = self.head # 그렇지 않다면 마지막 노드에 새로운 노드 추가
while currrent.next is not None: # 다음 노드가 없을 때까지
currrent = currrent.next # 다음 원소로 넘어감
currrent.next = Node(data) # 다음 노드가 없으면 새로운 데이터를 추가
# 모든 노드를 하나씩 출력
def show(self):
currrent = self.head
while currrent is not None:
print(currrent.data, end=" ")
currrent = currrent.next
# 특정 인덱스(index)의 노드 찾기
def search(self, index):
node = self.head
for _ in range(index):
node = node.next
return node
# 특정 인덱스(index)에 노드 삽입
def insert(self, index, data):
new = Node(data)
# 첫 위치에 추가하는 경우
if index == 0:
new.next = self.head
self.head = new
return
# 삽입할 위치의 앞 노드
node = self.search(index - 1)
next = node.next
node.next = new
new.next = next
# 특정 인덱스(index)의 노드 삭제
def remove(self, index):
# 첫 위치를 삭제하는 경우
if index == 0:
self.head = self.head.next
return
# 삭제할 위치의 앞 노드
front = self.search(index - 1)
front.next = front.next.next
linked_list = LinkedList()
data_list = [3, 5, 9, 8, 5, 6, 1, 7]
for data in data_list:
linked_list.append(data)
print("전체 노드 출력:", end=" ")
linked_list.show()
linked_list.insert(4, 4)
print("\n전체 노드 출력:", end=" ")
linked_list.show()
linked_list.remove(7)
print("\n전체 노드 출력:", end=" ")
linked_list.show()
linked_list.insert(7, 2)
print("\n전체 노드 출력:", end=" ")
linked_list.show()
# 출력:
# 전체 노드 출력: 3 5 9 8 5 6 1 7
# 전체 노드 출력: 3 5 9 8 4 5 6 1 7
# 전체 노드 출력: 3 5 9 8 4 5 6 7
# 전체 노드 출력: 3 5 9 8 4 5 6 2 7
핵심 포인트