[자료구조] #4_3 링크드 리스트
** 더블 링크드 리스트(Doubly Linked List)
- 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
class Node:
def __init__(self, data, prev=None, next=None):
self.prev = prev # 앞 노드와의 연결 정보
self.data = data
self.next = next
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
self.tail = self.head
def insert(self, data):
if self.head == None:
self.head = Node(data)
self.tail = self.head
else:
node = self.head
while node.next:
node = node.next
new = Node(data)
node.next = new
new.prev = node
self.tail = new
def desc(self):
node = self.head
while node:
print (node.data)
node = node.next
** 더블 링크드 리스트로 다양한 기능 구현
1) 검색
class Node:
def __init__(self, data, prev=None, next=None):
...
class NodeMgmt:
def __init__(self, data):
...
def insert(self, data):
...
def desc(self):
...
def search_from_head(self, data): # 탐색 방향: 앞 -> 뒤
if self.head == None:
return False
node = self.head
while node:
if node.data == data:
return node
else:
node = node.next
return False
def search_from_tail(self, data): # 탐색 방향: 앞 <- 뒤
if self.head == None:
return False
node = self.tail
while node:
if node.data == data:
return node
else:
node = node.prev
return False
2) 삽입
def insert_before(self, data, before_data): # 특정 노드 앞에 삽입
if self.head == None:
self.head = Node(data)
return True
else:
node = self.tail
while node.data != before_data:
node = node.prev
if node == None:
return False
new = Node(data)
before_new = node.prev
before_new.next = new
new.next = node
return True
def insert_after(self, data, after_data): # 특정 노드 뒤에 삽입
if self.head == None:
self.head = Node(data)
return True
else:
node = self.head
while node.data != after_data:
node = node.next
if node == None:
return False
new = Node(data)
after_new = node.next
new.next = after_new
new.prev = node
node.next = new
if new.next == None:
self.tail = new
return True
def insert(self, data): # 맨 뒤에 추가
if self.head == None:
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
new = Node(data)
node.next = new
new.prev = node
self.tail = new