양방향 연결 리스트(Doubly Linked Lists)

1 양방향 연결 리스트

• 한 쪽으로만 링크를 연결하지 말고, 양 쪽으로! → 앞으로도 뒤로도 진행 가능
  
• 복잡해 보이지만 막상 코딩하면 보다 간단하다
• 단방향 연결리스트와 다르게 마지막 노드에 대한 연산도 빨라질 수 있다
• 리스트 처음과 끝에 dummy node를 둔다

2 자료구조 정의

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

3 연산 정의

3.1 리스트 순회

def traverse(self):
    result = []
    curr = self.head
    while curr.next.next:
        curr = curr.next
        result.append(curr.data)
    return result

3.2 리스트 역순회

def reverse(self):
    result = []
    curr = self.tail
    while curr.prev.prev:
        curr = curr.prev
        result.append(curr.data)
    return result

3.3 원소의 삽입

• 리스트가 많이 길어지면 앞에서부터 찾아야하기 때문에 부담이 커진다 → getAt()을 수정하자
  

1. insertAfter()

   

   1. next = prev.next
   2. newNode.prev = prev
   3. newNode.next = next
   4. prev.next = newNode
   5. next.prev = newNode

   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

2. insertBefore (*)

   • insertAfter와 반대로 하면 된다

   def insertBefore(self, next, newNode):
           prev = next.prev
           newNode.prev = prev
           newNode.next = next
           prev.next = newNode
           next.prev = newNode
           self.nodeCount += 1
           return True

3.4 특정 원소 얻어내기

• pos의 위치에 따라 head, tail 중 탐색을 시작할 위치를 선정한다
  • 연결 리스트가 길어지면 head부터 탐색하기에 부담이 생길 수 있다

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

3.5 원소 삭제 (*)

1. popAfter

     def popAfter(self, prev):
         # pop할 것이 없는 경우
         if self.nodeCount < 1:
             return None
         
         popNode = prev.next
         
         prev.next = popNode.next
         popNode.next.prev = prev
         
         self.nodeCount -= 1
         return popNode.data

2. popBefore

   def popBefore(self, next):
         if self.nodeCount < 1:
             return None
         
         popNode = next.prev
         
         next.prev = popNode.prev
         popNode.prev.next = next
         
         self.nodeCount -= 1
         return popNode.data

3. popAt

   def popAt(self, pos):
       if pos < 1 or pos > self.nodeCount:
           raise IndexError
       
       # pos 위치 찾기
       prev = self.getAt(pos - 1)
       return self.popAfter(prev)

3.6 두 리스트 합치기 (*)

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