오래 전 자료구조 시간에 배운 Linked List에 대한 개념이 머릿속에서 모호해져서, 파이썬으로 직접 구현하며 개념을 상기해보려 한다.
Linked list
What is Linked list?
Linked list(연결 리스트)는 데이터를 노드(Node)라는 단위로 저장하는 자료구조다. 각 노드는 데이터 필드와 다음 노드를 가리키는 포인터로 구성되어 있으며, 이러한 노드들이 일렬로 연결되어 있는 형태를 띄고 있다. Linked list의 주요 특징은 삽입과 삭제가 용이하다는 점이다. 배열과 달리 미리 할당된 메모리 공간이 필요 없으며, 필요한 만큼 메모리를 할당받을 수 있다.
Linked list는 주로 다음과 같은 연산을 지원한다:
- 삽입(Insertion): 리스트의 앞, 중간, 끝에 새로운 노드를 삽입할 수 있음
- 삭제(Deletion): 특정 노드를 리스트에서 제거할 수 있음
- 탐색(Search): 리스트를 순회하며 특정 값을 가진 노드를 찾을 수 있음
Code implementation
linked list를 파이썬으로 직접 구현하면 아래와 같을 것입니다 ㅎ
class Node:
def __init__(self, val):
self.val = val
self.next = None
class SingleLinkedList:
def __init__(self):
self.head = None
def insertAtHead(self, val):
node = ListNode(val)
node.next = self.head
self.head = node
def insertBack(self, val):
node = ListNode(val)
crnt_node = self.head
while crnt_node.next:
crnt_node = crnt_node.next
crnt_node.next = node
def findNode(self, val):
crnt_node = self.head
while crnt_node is not None:
if crnt_node.val == val:
return crnt_node
crnt_node = crnt_node.next
raise RuntimeError('LinkedList: empty')
def insertAfter(self, node, val):
new_node = ListNode(val)
new_node.next = node.next
node.next = new_node
def popAfter(self, prev_node):
if prev_node.next is not None:
prev_node.next = prev_node.next.next
간단하게 코드에 대한 설명을 하자면 아래와 같습니다.
- Node 클래스는 연결 리스트의 각 노드를 나타냅니다. 각 노드는 값(
val)과 다음 노드를 가리키는 포인터(next)를 가집니다.SingleLinkedList클래스는 단일 연결 리스트를 나타냅니다.insertAtHead메서드는 리스트의 맨 앞에 새로운 노드를 삽입합니다.insertBack메서드는 리스트의 맨 뒤에 새로운 노드를 삽입합니다.findNode메서드는 리스트를 순회하며 특정 값을 가진 노드를 찾습니다.insertAfter메서드는 특정 노드 뒤에 새로운 노드를 삽입합니다.popAfter메서드는 특정 노드 뒤의 노드를 삭제합니다.
Double Linked list
What is Double Linked list?
Double Linked list(이중 연결 리스트)는 각 노드가 두 개의 포인터를 가지는 자료구조다. 하나는 다음 노드를 가리키고 다른 하나는 이전 노드를 가리킨다. 이러한 구조 덕분에 양방향으로 리스트를 순회할 수 있어 단일 연결 리스트에 비해 노드의 삽입과 삭제가 더 효율적이다.
Double Linked list의 주요 특징은 다음과 같다.
- 양방향 순회: 리스트의 앞과 뒤 어느 방향으로든 순회가 가능
- 더 빠른 삽입과 삭제: 특정 노드의 앞이나 뒤에 노드를 삽입하거나 삭제할 때, 추가적인 포인터 조작이 필요 없음
Code implementation
double linked list를 파이썬으로 직접 구현하면 아래와 같을 것입니다 ㅎ
class Node:
def __init__(self, item):
self.data = item
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.nodeCount = 0
self.head = Node(None)
self.tail = Node(None)
self.head.prev = None
self.head.next = self.tail
self.tail.prev = self.head
self.tail.next = None
def __repr__(self):
if self.nodeCount == 0:
return 'LinkedList: empty'
s = ''
curr = self.head
while curr.next.next:
curr = curr.next
s += repr(curr.data)
if curr.next.next is not None:
s += ' -> '
return s
def getLength(self):
return self.nodeCount
def traverse(self):
result = []
curr = self.head
while curr.next.next:
curr = curr.next
result.append(curr.data)
return result
def reverse(self):
result = []
curr = self.tail
while curr.prev.prev:
curr = curr.prev
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 0 or pos > self.nodeCount:
return None
if pos > self.nodeCount // 2:
i = 0
curr = self.tail
while i < self.nodeCount - pos + 1:
curr = curr.prev
i += 1
else:
i = 0
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def insertAfter(self, prev, newNode):
next = prev.next
newNode.prev = prev
newNode.next = next
prev.next = newNode
next.prev = newNode
self.nodeCount += 1
return True
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
prev = self.getAt(pos - 1)
return self.insertAfter(prev, newNode)
def popAfter(self, prev):
curr = prev.next
next = curr.next
prev.next = next
next.prev = prev
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError('Index out of range')
prev = self.getAt(pos - 1)
return self.popAfter(prev)
def concat(self, L):
self.tail.prev.next = L.head.next
L.head.next.prev = self.tail.prev
self.tail = L.tail
self.nodeCount += L.nodeCount
이번에도 간단하게 코드에 대한 설명을 하자면 아래와 같습니다.
- Node 클래스는 이중 연결 리스트의 각 노드를 나타냅니다. 각 노드는 값(
data), 이전 노드를 가리키는 포인터(prev), 다음 노드를 가리키는 포인터(next)를 가집니다.DoublyLinkedList클래스는 이중 연결 리스트를 나타냅니다.__repr__메서드는 리스트의 모든 노드를 문자열로 반환합니다.getLength메서드는 리스트의 길이를 반환합니다.traverse메서드는 리스트를 순회하며 모든 노드의 값을 리스트로 반환합니다.reverse메서드는 리스트를 역순으로 순회하며 모든 노드의 값을 리스트로 반환합니다.getAt메서드는 특정 위치에 있는 노드를 반환합니다.insertAfter메서드는 특정 노드 뒤에 새로운 노드를 삽입합니다.insertAt메서드는 특정 위치에 새로운 노드를 삽입합니다.popAfter메서드는 특정 노드 뒤의 노드를 삭제합니다.popAt메서드는 특정 위치의 노드를 삭제합니다.concat메서드는 두 리스트를 연결합니다.
마무리
실제로 해당 개념들이 어떤 상황에서 활용되면 좋은지 알아보자 :)
Linked List 활용
-
동적 메모리 할당: 배열과 달리 미리 크기를 정해놓지 않아도 되기 때문에, 동적으로 크기가 변하는 데이터를 처리할 때 유용하다. 예를 들어, 메모리 관리, 객체 풀(pool) 등에서 사용된다.
-
데이터 삽입/삭제가 빈번한 경우: 특정 위치에 데이터를 삽입하거나 삭제할 때 배열보다 효율적이다. 삽입/삭제 시에 모든 요소를 이동시킬 필요 없이 포인터만 조작하면 되기 때문이다.
-
스택과 큐 구현: Linked List는 스택과 큐 같은 자료구조를 구현하는 데 자주 사용된다. 스택에서는 후입선출(LIFO), 큐에서는 선입선출(FIFO) 방식으로 데이터를 처리할 수 있다.
-
그래프 및 트리 구현: 그래프와 트리 같은 복잡한 자료구조도 Linked List를 사용해서 구현할 수 있다. 특히, 각 노드가 여러 자식 노드를 가질 수 있는 상황에서 유용하다.
Double Linked List 활용
-
양방향 순회: 이중 연결 리스트는 앞뒤로 자유롭게 순회할 수 있어서, 양방향 탐색이 필요한 경우에 적합하다. 예를 들어, 뒤로 가기/앞으로 가기 기능이 있는 웹 브라우저의 히스토리 관리에 사용된다.
-
이중 연결 리스트 기반 자료구조: Deque(양쪽 끝에서 삽입과 삭제가 가능한 큐), LRU(Least Recently Used) 캐시 등에서 사용된다. LRU 캐시는 최근에 사용된 적이 없는 데이터를 제거하는 방식의 캐시 알고리즘인데, 이중 연결 리스트를 사용하면 효율적으로 구현할 수 있다.
-
텍스트 편집기: 텍스트 편집기에서 커서의 이동, 삽입, 삭제 같은 연산을 빠르게 처리하기 위해 이중 연결 리스트를 사용한다. 커서가 문장의 중간에 있을 때도 효율적으로 삽입/삭제가 가능하기 때문이다.
이처럼 Linked List와 Double Linked List는 각각의 장점을 활용하면, 다양한 상황에서 효율적인 데이터 처리를 가능하게 할 수 있다.
