양방향 연결리스트 Doubly Linked List

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록

자료구조 양방향연결리스트 삽입-삭제-탐색 연산 - YouTube

 

양 끝이 연결된 원형 양방향 연결리스트 Circularly Doubly Linked List로 관리하면 편하다.

빈 노드 = 더미노드 dummy node를 head 노드로 설정한다. (더미노드의 key 값은 None)

즉 양방향 연결리스트의 초기 상태에서 더미노드는 자기 자신을 가리킨다. 

 

splice 연산

splice(a, b, x): a부터 b까지를 잘라 x 다음에 넣는다.

splice 연산을 위한 전제조건

1. a -> ... -> b

2. a와 b 사이에 head node가 있으면 안 됨.

3. a와 b 사이에 x 노드가 있으면 안 됨.

    def splice(self, a, b, x):  # 세 개의 노드 a, b, x
        if a == None or b == None or x == None:
            return
        #  a부터 b까지 잘라내기
        a.prev.next = b.next
        b.next.prev = a.prev

        # 잘라낸 부분을 x 다음에 넣기
        x.next.prev = b
        b.next = x.next
        a.prev = x
        x.next = a

splice 연산을 이용하면 이동, 탐색, 삽입, 삭제 연산을 구현할 때 훨씬 편해진다.

 

이동연산

- moveAfter(a, x)

노드 a를 노드 x 다음으로 이동. 

splice 연산 이용

--> splice(a, a, x)

 

- moveBefore(a, x)

노드 a를 노드 x 전으로 이동. 

--> splice(a, a, x.prev)

 

- insertAfter(x, key)

x 노드 다음에 key를 갖는 노드를 집어넣음

--> moveAfter(Node(key), x)

 

- insertBefore(x, key)

x 노드 전에 key를 갖는 노드를 집어넣음

--> moveBefore(Node(key), x)

 

 

삽입연산

- pushFront(key)

연결리스트의 맨 앞에 key를 갖는 노드를 집어넣음

--> insertAfter(self.head, key)

self.head (더미노드) 다음에 key를 갖는 노드를 집어넣는다.

 

- pushBack(key)

연결리스트의 맨 뒤에 key를 갖는 노드를 집어넣음

--> insertBefore(self.head, key)

self.head (더미노드) 이전에 key를 갖는 노드를 집어넣는다.

*원형양방향연결리스트로 관리하기 때문에 self.head의 이전 노드는 맨 끝 노드이다. 

 

삭제연산

remove(x)

x가 담긴 노드를 지우고 x를 리턴

 

deleteNode(x)

노드 x를 지움

    def deleteNode(self, x):
        if x == None or x == self.head:
            return
        x.prev.next, x.next.prev = x.next, x.prev

 

popFront()

리스트의 가장 앞 노드를 지우고 리턴

    def popFront(self):
        if self.head.next == self.head:  # 비어 있는 경우는 제외
            return None
        key = self.head.next.key
        self.deleteNode(self.head.next)
        return key

 

 

popBack()

리스트의 가장 뒤 노드를 지우고 리턴

    def popBack(self):
        if self.head.prev == self.head:
            return None
        key = self.head.prev.key
        self.deleteNode(self.head.prev)
        return key

 

탐색연산

search(self, key)

    def search(self, key):
        v = self.head  # dummy node
        while v.next != self.head:
            if v.key == key:
                return v
            v = v.next
        if v.key == key:
            return v
        return None

 

first()

가장 앞 노드 리턴

비어 있는 경우 None

    def first(self):  # 가장 앞 노드 리턴, 빈 리스트면 None
        if self.head.next == self.head:
            return None
        else:
            return self.head.next

 

last()

가장 뒷 노드 리턴

비어 있는 경우 None

    def last(self):  # 가장 뒷 노드 리턴, 빈 리스트면 None
        if self.head.next == self.head:
            return None
        else:
            return self.head.prev

 

그 외 join, split 연산도 직접 구현해볼것!