더블 링크드리스트 (이중 연결리스트)

더블 링크드리스트 (이중 연결리스트)

이중 연결리스트는 한 노드에서 뒤로도 이동하고 앞으로도 이동할 수 있는 연결리스트를 의미합니다.

따라서 Node class에 데이터에 대한 정보와 그 다음 노드에 대한 정보, 그리고 추가로 그 이전에 노드에 대한 정보도 담아 두어야 합니다.

그리고 여기 이중 연결리스트에서는 head 와 tail 부분에 dummy node를 하나씩 추가로 두어 모든 노드의 생김새가 똑같도록 하였습니다.

이 외에 부분은 기본 연결리스트와 거의 동일하며 코드가 조금 더 간결해 진 것을 볼 수 있습니다.

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 'DoubleLinkedList is empty' s = '' curr = self.head.next while curr.next is not None: s += repr(curr.data) if curr.next is not self.tail: s += ' -> ' curr = curr.next return s def traverse(self): result = [] curr = self.head while curr.next.next: curr = curr.next 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 after=curr.next prev.next=after after.prev=prev data=curr.data self.nodeCount-=1 del curr return data def popBefore(self, next): curr=next.prev prev=curr.prev prev.next=next next.prev=prev data=curr.data self.nodeCount-=1 del curr return data def popAt(self, pos): if pos<1 or pos>self.nodeCount: raise IndexError if pos>(self.nodeCount//2): if pos==self.nodeCount: next=self.tail else: next=self.getAt(pos+1) return self.popBefore(next) if pos<=(self.nodeCount//2): if pos==1: prev=self.head else: 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

from http://polarmin.tistory.com/9 by ccl(A) rewrite - 2021-08-23 00:00:21