이중 연결 리스트(Doubly Linked List)는 각 노드가 두 개의 포인터를 가지고 있는 선형 자료 구조이다. 한 포인터는 다음 노드를 가리키고, 다른 포인터는 이전 노드를 가리킨다. 이를 통해 리스트를 양방향으로 순회할 수 있다. 이중 연결 리스트는 단일 연결 리스트(Singly Linked List)에 비해 더 많은 메모리를 사용하지만, 삽입 및 삭제 연산이 더 유연하고 효율적이다.
구조
- 노드 (Node): 이중 연결 리스트의 기본 구성 요소로, 데이터와 두 개의 포인터(이전 노드와 다음 노드를 가리키는 포인터)를 포함한다.
- 데이터 (Data): 노드가 저장하는 값.
- 이전 (Prev): 이전 노드를 가리키는 포인터.
- 다음 (Next): 다음 노드를 가리키는 포인터.
- 헤드 (Head): 리스트의 첫 번째 노드를 가리키는 포인터. 리스트의 시작점이다.
- 꼬리 (Tail): 리스트의 마지막 노드를 가리키는 포인터. 리스트의 끝점이다.
이중 연결 리스트의 주요 연산
- 삽입 (Insertion):
- 앞쪽 삽입 (Insert at the Beginning): 새 노드를 헤드 앞에 추가하고, 헤드를 새 노드로 갱신한다.
- 끝쪽 삽입 (Insert at the End): 새 노드를 리스트의 끝에 추가한다.
- 중간 삽입 (Insert in the Middle): 특정 위치에 새 노드를 삽입한다.
- 삭제 (Deletion):
- 앞쪽 삭제 (Delete from the Beginning): 첫 번째 노드를 삭제하고, 헤드를 다음 노드로 갱신한다.
- 끝쪽 삭제 (Delete from the End): 마지막 노드를 삭제한다.
- 중간 삭제 (Delete in the Middle): 특정 위치의 노드를 삭제한다.
- 탐색 (Search): 리스트를 순회하면서 특정 값을 가진 노드를 찾는다.
- 길이 반환 (Get Length): 리스트에 포함된 노드의 개수를 반환한다.
- 출력 (Display): 리스트의 모든 노드를 순서대로 출력한다.
이중 연결 리스트의 장단점
장점:
- 양방향 순회 가능: 이전 노드를 가리키는 포인터가 있어 양방향으로 리스트를 순회할 수 있다.
- 삽입과 삭제가 용이: 단일 연결 리스트에 비해 중간에 노드를 삽입하거나 삭제하는 연산이 더 간단하고 효율적이다.
단점:
- 추가 메모리 사용: 각 노드가 두 개의 포인터(이전과 다음)를 저장해야 하므로 추가 메모리를 사용한다.
- 구현 복잡도 증가: 단일 연결 리스트에 비해 구조가 복잡하여 구현이 더 어렵다.
이중 연결 리스트의 활용 예
- 이중 방향 순회가 필요한 경우: 양방향 순회가 필요한 경우에 유용하다. 예를 들어, 웹 브라우저의 앞뒤 탐색 기능, 이미지 뷰어에서 이전 및 다음 이미지 보기 등.
- 삽입 및 삭제 연산이 빈번한 경우: 중간 삽입과 삭제가 빈번하게 일어나는 경우 단일 연결 리스트보다 효율적이다.
- 캐시 구현: LRU(Least Recently Used) 캐시와 같은 알고리즘에서 사용될 수 있다.
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insertBeginning(self, data):
new_node = Node(data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
else:
self.tail = new_node
self.head = new_node
def insertEnd(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
return
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
def insertMiddle(self, data, index):
if index < 0:
print("Invalid position")
return
new_node = Node(data)
if index == 0:
self.insertBeginning(data)
return
cur = self.head
for i in range(index - 1):
if cur is None:
print("Index out of bounds")
return
cur = cur.next
if cur is None:
print("Index out of bounds")
return
new_node.next = cur.next
new_node.prev = cur
if cur.next is not None:
cur.next.prev = new_node
cur.next = new_node
if new_node.next is None:
self.tail = new_node
def deleteNode(self, key):
temp = self.head
while temp is not None:
if temp.data == key:
if temp.prev is not None:
temp.prev.next = temp.next
else:
self.head = temp.next
if temp.next is not None:
temp.next.prev = temp.prev
else:
self.tail = temp.prev
return
temp = temp.next
print("Key not found")
def search(self, key):
cur = self.head
while cur is not None:
if cur.data == key:
return True
cur = cur.next
return False
def getLength(self) -> int:
count = 0
cur = self.head
while cur:
count += 1
cur = cur.next
return count
def display(self):
cur = self.head
while cur:
print(cur.data, end=" <-> ")
cur = cur.next
print("None")
# Example usage
dll = DoublyLinkedList()
dll.insertEnd(10)
dll.insertEnd(20)
dll.insertBeginning(5)
dll.insertMiddle(2, 15) # Insert 15 at position 2
dll.display() # Output: 5 <-> 10 <-> 15 <-> 20 <-> None
print(dll.search(10)) # Output: True
print(dll.getLength()) # Output: 4
dll.deleteNode(10)
dll.display() # Output: 5 <-> 15 <-> 20 <-> None
코드 설명
Node 클래스
- data: 노드가 저장하는 데이터.
- next: 다음 노드를 가리키는 포인터.
- prev: 이전 노드를 가리키는 포인터.
DoublyLinkedList 클래스
초기화
- head: 리스트의 첫 번째 노드를 가리킨다.
- tail: 리스트의 마지막 노드를 가리킨다.
insertBeginning 메서드
- 리스트의 맨 앞에 노드를 삽입합니다.
- 새로운 노드를 head로 설정하고, 기존 head의 prev 포인터를 업데이트한다.
- 리스트가 비어있을 경우, tail도 업데이트한다.
insertEnd 메서드
- 리스트의 끝에 노드를 삽입한다.
- 리스트가 비어있을 경우, head와 tail을 새로운 노드로 설정한다.
- 그렇지 않은 경우, tail을 업데이트하고, 새로운 노드의 prev를 설정한다.
insertMiddle 메서드
- 리스트의 특정 위치에 노드를 삽입한다.
- 인덱스가 0일 경우, insertBeginning 메서드를 호출한다.
- 인덱스가 리스트의 범위를 벗어나지 않도록 검사하고, 삽입 위치에 따라 next와 prev 포인터를 업데이트한다.
deleteNode 메서드
- 특정 값을 가진 노드를 삭제한다.
- 삭제할 노드의 prev와 next 포인터를 업데이트하여 노드를 리스트에서 제거한다.
search 메서드
- 리스트에서 특정 값을 가진 노드를 검색한다.
getLength 메서드
- 리스트의 노드 개수를 반환한다.
display 메서드
- 리스트의 모든 노드를 순서대로 출력한다.
모든 코드는 github에 저장되어 있습니다.
https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms
728x90
'Data structure & Algorithms study' 카테고리의 다른 글
연결 리스트 기반 스택 (Linked List-based Stack) (0) | 2024.06.30 |
---|---|
원형 연결 리스트 (Circular Linked List) (0) | 2024.06.29 |
단일 연결 리스트 (Singly Linked List) (0) | 2024.05.27 |
덱 (Deque) (0) | 2024.05.27 |
원형 큐(Circular Queue) (0) | 2024.05.26 |