양방향 연결 리스트

플랫폼: 프로그래머스
강의명: 어서와! 자료구조와 알고리즘은 처음이지?
강사명: 이시윤

---

1. 양방향 연결 리스트

이중 연결 리스트라고도 한다.

1) Node 확장

class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.prev = None
        self.next = None

2) 더미 노드 추가

class DoublyLinkedList:
    def __init__(self) -> None:
        self.node_cnt = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.next = self.tail
        self.tail.prev = self.head

---

2. 순회, 역순회

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

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

---

3. 삽입

    def insert_after(self, prev: Node, new_node: Node) -> bool:
        next = prev.next
        new_node.prev = prev
        new_node.next = next
        prev.next = new_node
        next.prev = new_node
        self.node_cnt += 1
        return True

---

4. 특정 위치의 노드 찾기

    def get_at(self, pos: int) -> Node:
        if pos < 1 or pos > self.node_cnt + 1:
            raise IndexError

        if pos > self.node_cnt // 2:
            cur = self.tail
            for _ in range(self.node_cnt - pos + 1):
                cur = cur.prev
        else:
            cur = self.head
            for _ in range(pos):
                cur = cur.next
        return cur

---

5. 특정 위치에 노드 삽입하기

    def insert_at(self, pos: int, new_node: Node) -> bool:
        prev = self.get_at(pos-1)
        return self.insert_after(prev, new_node)

---

6. 과제

insert_before 메소드

    def insert_before(self, next: Node, new_node: Node) -> bool:
        prev = next.prev
        prev.next = new_node
        new_node.prev = prev
        new_node.next = next
        next.prev = new_node
        self.node_cnt += 1
        return True

pop_after 메소드

    def pop_after(self, prev: Node) -> int:
        res = prev.next.data
        next = prev.next.next
        prev.next = next
        next.prev = prev
        self.node_cnt -= 1
        return res

pop_before 메소드

    def pop_before(self, next: Node) -> int:
        res = next.prev.data
        prev = next.prev.prev
        prev.next = next
        next.prev = prev
        self.node_cnt -= 1
        return res