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

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

• 한 쪽으로만 링크를 연결하지 말고, 양쪽으로!
  • 앞으로도(다음 node) 뒤로도 (이전 node) 진행 가능
• Node의 구조 확장

class Node:
    def __init__(self, item):
        self.item = item
        self.prev = None
        self.next = None

• 리스트 처음과 끝에 dummy node를 둔다.
  • 데이터를 담고 있는 node들은 모두 같은 모양

class Node:
    def __init__(self, item):
        self.item = item
        self.prev = None
        self.next = None

class DoubleLinkedList:
    def __init__(self, item):
        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

• 리스트 순회

class Node:
    def __init__(self, item):
        self.item = item
        self.prev = None
        self.next = None

class DoubleLinkedList:
    def __init__(self, item):
        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 traverse(self):
    result = []
    curr = self.head
    while curr.next.next:
        curr = curr.next
        result.append(curr.data)
    return result

• 리스트 역순회

class Node:
    def __init__(self, item):
        self.item = item
        self.prev = None
        self.next = None

class DoubleLinkedList:
    def __init__(self, item):
        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 traverse(self):
    result = []
    curr = self.head
    while curr.next.next:
        curr = curr.next
        result.append(curr.data)
    return result

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

• 원소의 삽입
  • prev외 prev의 next노드를 검색
  • newNode.prev를 prev.next에
  • newNode의 next를 next.prev에 연결
  • prev의 next를 newNode로
  • next의 prev를 newNode로
  • nodeCount += 1

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 getAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
        return None
    i = 0
    curr = self.head
    while i < pos:
        curr = curr.next
        i += 1
    return curr

• 원소의 삽입
  • 📌 리스트 마지막에 원소를 삽입하면?
    • pos를 self.nodeCount // 2 기준으로 앞에서부터 찾을지 뒤에서부터 찾을지 계선하기

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 inserBefore(self, next, newNode)
  • def pop After(self,prev)
  • def popBefore(self, next)
  • def popAt(self, pos)

---

10강 실습: (1) 양방향 연결 리스트 역방향 순회

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

10강 실습: (2) 양방향 연결 리스트 노드 삽입

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

10강 실습: (3) 양방향 연결 리스트 노드 삭제

   def popAfter(self, prev):
        if prev == self.tail:
            return None
        target = prev.next
        prev.next = target.next
        target.next.prev = prev
        self.nodeCount -= 1
        return target.data
        

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

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        
        if pos == 1:
            return self.popAfter(self.head)
        else:
            return self.popAfter(self.getAt(pos-1))

10강 실습: (4) 양방향 연결 리스트의 병합

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