10강 요약
이전의 단방향 연결리스트와 다르게 이전노드도 이어서 이동할 수있고, 헤드에만 더미노드를 넣었던 반면 tail에도 더미너드를 두어 좀더 수월하게 사이드 조건들을 처리할 수 있다.
10강 내용
1.노드 구조
2.리스트 구조
3.달라진getAt
4.insertAfter
노드 구조
class Node:
def __init__(self, item):
self.data = item
self.prev = None
self.next = None노드로 next와 더블어 이전 노드를 참조하는 prev가 추가되었다
리스트 구조
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
마지막 더미노드인 self.tail이 추가되었다.
달라진 getAt
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연결리스트와 유사하지만 tail을 사용하는 만큼 효율을 증가시키기 위해 2가지의 경우로 나누어서 노드를 구한다.
if문은 pos를 이용하여 노드가 중간뒤에 나오는지 구분한다.
중간 뒤쪽에 나오는걸 아는데도 head부터 따라가는것이 손해다. 반대로 tail부터 따라가는것이 훨씬 효율적이다.
따라서 중간보다 앞이면 head에서, 뒤면 tail에서 노드를 찾아간다.
insertAfter
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)next만 조절하는것이아니라 prev도 노드에 연결해야한다.
단일 연결리스트와 마찬가지로 새로운 노드의 prev와 next부터 먼저 조절하고 난 다음 prev와 next의 prev,next를 수정해야 연결을 유지할 수 있다.
문제
역방향 순회
def reverse(self):
answer = []
curr = self.tail
while curr.prev.prev:
curr = curr.prev
answer.append(curr.data)
return answerwhile의 조건문이 달라져야한다. taildummy가 추가된 만큼 이전노드의 prev를 확인해야한다.
앞에 노드 삽입
def insertBefore(self, next, newNode):
prev = next.prev
newNode.prev=prev
newNode.next=next
next.prev=newNode
prev.next=newNode
self.nodeCount += 1
return True 뒤에노드로 부터 앞의 노드(prev의 prev)를 얻고 insertAfter와 같은 방법으로 연결할 수 있다.
노드 삭제
이전 노드로 삭제
def popAfter(self, prev):
delNode = prev.next
next = delNode.next
next.prev=prev
prev.next=next
self.nodeCount -= 1
return delNode.data이후 노드로 삭제
def popBefore(self, next):
delNode = next.prev
prev = delNode.prev
next.prev = prev
prev.next = next
self.nodeCount -= 1
return delNode.data이전노드 이후노드를 구함
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
prev = self.getAt(pos-1)
next = self.getAt(pos+1)
return self.popBefore(next) def getAt(self, pos):
if pos < 0 or pos > self.nodeCount+1:
return None마지막으로 수정해주어야 popBefore()가 정상작동된다. 생각해보면 당연하다
head와 tail 양쪽 모드 dummy노드를 추가하였고 각각 0번째, N+1번째인덱스를 차지하는 노드다.
GitHub
