[자료구조] Double Linked List(양 방향 연결리스트) python class 구현하기

[자료구조] Double Linked List(양 방향 연결리스트) python class 구현하기

 

살펴볼 주요 개념:

- 양 방향 연결리스트의 특징

- 양 방향 연결리스트 클래스 구현(Node, Double Linked List)

 

1. 양 방향 연결리스트의 특징

양 방향 연결리스트는 이중 연결 리스트, 원형 연결 리스트로 나누어 진다.

여기서는 원형 연결 리스트만을 살펴볼 것이다.

 

양 방향 연결리스트는 tail 노드를 알지 못해도 순차적인 탐색 연산이 필요 없다.

삽입될 앞 뒤의 노드만 알고 있다면, 상수 시간 내에 삽입 또는 삭제 연산이 가능하다.

 

위 사진은 한 방향이지만, 양 방향으로 구성되어 있는 것을 생각하면 되겠다.

 

원형 연결리스트의 맨 앞 노드는 '더미 노드'이다.

원형 연결리스트의 순서를 정확하게 매길 수 없는 특징 때문에, head 노드를 정확하게 설정할 수 없다.

따라서 None을 키로 하는 더미 노드를 헤드 포인터가 가리키게 하고, 더미 노드를 헤드 노드로 설정하는 것이다.

헤드 노드인 더미 노드르 중심으로 나머지 노드들이 원형으로 연결되어 있는 것이다.

 

위와 같은 특징으로 인해 한 방향 연결 리스트와는 다른 메소드 들이 들어간다.

삽입, 삭제, 탐색 연산의 과정이 다르게 된다.

 

2. Double Linked List Class 구현

 

(1) Node Class

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

    def __str__(self):
        return str(self.key) # print(v)를 대신하는 함수

한 방향 연결리스트의 것과 같지만 next와 prev를 두어 양 방향으로 링크를 설정할 수 있게 했다.

 

 

 

(2) Double Linked List

 

1) init

class doubleLinkedList:
    def __init__(self):
        self.head = Node()
        self.size = 0

자기 자신을 가리키는 노드를 헤드로 설정한다. 더미 노드를 처음 만드는 것이다.

 

2) splice 메소드

    def splice(self, a, b, x):
        ap, bn, xn = a.prev, b.next, x.next
        ap.next = bn
        bn.next = ap
        x.next = a
        a.prev = x
        b.next = xn
        xn.prev = b

Double Linked List는 splice 연산이 매우 중요하다. 삽입, 삭제를 이 연산을 통해 해결하기 때문이다.

파라미터 a, b, x의 의미는 다음과 같다.

 

a노드와 b노드 구간을 잘라서 x의 다음 자리에 추가하는 것이다.

 

splice 연산은 다음 조건을 모두 충족해야 한다.

1. a의 next를 따라가다 보면 b가 나와야 한다.

2. a, b 사이에 head 노드(더미노드)가 없다.

3. a 노드와 b 노드 사이에 x 노드가 존재하지 않는다.

 

 

 

 

3) moveAfter, moveBefore, insertAfter, insertBefore, pushFront, pushBack

    def moveAfter(self, a, x):
        doubleLinkedList.splice(a, a, x)
    
    def moveBefore(self, a, x):
        doubleLinkedList.splice(a, a, x.prev)

    def insertAfter(x, key):
        doubleLinkedList.moveAfter(Node(key), x)

    def insertBefore(x, key):
        doubleLinkedList.moveBefore(Node(key), x)
  
    def pushFront(self, key):
        doubleLinkedList.insertAfter(self.head, key)
  
    def pushBack(self, key):
        doubleLinkedList.insertBefore(self.head, key)

splice 연산을 활용하면 6가지의 연산을 진행할 수 있다.

 

a를 x 뒤에 위치시키는 moveAfter,

a를 x의 앞에 위치시키는 moveBefore

새로운 key값을 노드화 시켜서 x 뒤에 위치시키는 insertAfter

새로운 key값을 노드화 시켜서 x 앞에 위치시키는 insertBefore

새로운 key값을 노드화 시켜서 맨 앞에 위치시키는 pushFront

새로운 key값을 노드화 시켜서 맨 뒤에 위치시키는 pushBack

 

 

4) search

    def search(self, key):
        v = self.head # 더미노드 부터
        while v.next != self.head:
            if v.key == key:
                return v
            v = v.next
        print("키값이 존재하지 않습니다.")
        return None # 키값 없음

더미노드부터 차례로 찾는 search 함수이다. 

 

 

5) remove

    def remove(self, key):
        x = self.search(key)
        if x == None:
            print("삭제할 키 값이 존재하지 않습니다.")
            return 
        else:
            x.prev.next = x.next
            x.next.prev = x.prev
            del x

 

 

6) iterator

    def __iterator__(self):
        v = self.head
        while v != None:
            yield v  # 리턴 같은 역할
            v = v.next