1. 양방향 연결리스트의 특징
노드들을 한 쪽 방향으로만 연결시킨 자료구조인 한방향 연결리스트의 단점을 보완한 자료구조
한쪽으로만 이동할 수 있었던 한방향 연결리스트에 반대쪽으로 이동할 수 있게 링크를 추가해 양쪽방향으로 이동할 수 있게 만들었다. 첫 노드는 항상 dummy노드가 되어 리스트의 처음을 구분할 수 있게 한다.
2. 양방향 연결리스트의 장점
○장점 1. 한 방향으로만 탐색해야 하는 한방향 연결리스트와 달리 두 방향으로 탐색을 할 수 있어 효율적이다.
○단점
1. 단방향 연결리스트에 비해 메모리를 많이 차지한다.
3. 양방향 연결리스트 구현
class Node:
def __init__(self, key=None):
self.key = key
self.prev = self
self.next = self
def __str__(self):
return str(self.key)
class DoublyLinkedList:
def __init__(self):
self.head = Node() # create an empty list with only dummy node
def __iter__(self):
v = self.head.next
while v != self.head:
yield v
v = v.next
def __str__(self):
return " -> ".join(str(v.key) for v in self)
def printList(self):
v = self.head.next
print("h -> ", end="")
while v != self.head:
print(str(v.key)+" -> ", end="")
v = v.next
print("h")
def splice(self,a,b,x):
if a==None or b==None or x==None:
return
ap=a.prev
bn=b.next
#cut
ap.next=bn
bn.prev=ap
#insert[a..b] after x
xn=x.next
xn.prev=b
b.next=xn
a.prev=x
x.next=a
def moveAfter(self,a,x):
self.splice(a,a,x)
def moveBefore(self,a,x):
self.splice(a,a,x.prev)
def insertBefore(self,x,key):
self.moveBefore(Node(key),x)
def insertAfter(self,x,key):
self.moveAfter(Node(key),x)
def pushFront(self,key):
self.insertAfter(self.head,key)
def pushBack(self,key):
self.insertBefore(self.head,key)
def deleteNode(self,x):
if x==None or x==self.head:
return
x.prev.next,x.next.prev=x.next,x.prev
def popFront(self):#None 이면 empty
if self.isEmpty():
return None
key=self.head.next.key
self.deleteNode(self.head.next)
return key
def popBack(self):#None 이면 empty
if self.isEmpty():
return None
key=self.head.prev.key
self.deleteNode(self.head.prev)
return key
def search(self,key):#노드 리턴 None 리턴하면 찾는 값이 없다
v=self.head.next
while v!=self.head:
if v.key==key:
return v
v=v.next
return None
4. splice(a,b,x) 함수
노드a 부터 노드b까지를 떼서 노드x뒤에 붙이는 함수이다. 다른 함수에 이용된다.
조건 1 : 노드a와 b가 동일하거나 a다음에b 이어야한다.
조건 2 : head노드와 x는 a와 b사이에 있을 수 없다.
5. 시간복잡도
moveAfter(Before) : O(1)
insertAfter(Before) : O(1)
pushFront(Back) : O(1)
popFront(Back) : O(1)
deleteNode : O(1)
search : O(n)
6. 함수 추가
def findMax(self): #제일 큰 key리턴 None 리턴하면 empty
if self.isEmpty():
return None
temp=self.head.next
v=temp.key
while temp.next!=self.head:
if v>temp.next.key:
temp=temp.next
else:
v=temp.next.key
temp=temp.next
return v
def deleteMax(self): #제일 큰 key 리턴 None 리턴하면 empty
if self.isEmpty():
return None
v=self.findMax()
self.deleteNode(self.search(self.findMax()))
return v
def sort(self): #큰 순서대로 정렬하는 함수, 연결리스트를 리턴한다.
L_sorted=DoublyLinkedList()
while self.findMax()!=None:
L_sorted.pushFront(self.deleteMax())
return L_sorted
def isEmpty(self): #empty 면 True 리턴, 아니면 False 리턴
if self.head.next==self.head:
return True
else:
return False