더블 링크드 리스트(Double linked list)

링크드 리스트를 업그레이드한 더블 링크드 리스트를 살펴보겠습니다.

 

더블 링크드 리스트는 양방향으로 포인터를 연결한 이중 구조로 이루어져 있습니다. 

하나의 데이터당 Prev pointer, Next pointer를 가지게 됩니다. 

구조상 양쪽으로 데이터를 연결하게 되어서 양방향으로 탐색하기가 좋습니다. 즉, 탐색이 좀 더 쉬워집니다.

다만, 기본적인 링크드 리스트보다 데이터당 한자리를 더 써야 하므로 좀 더 무겁습니다.

구현도 링크드 리스트보다 좀 더 복잡합니다.

그렇지만 양방향으로 탐색이 가능하다는 장점과 큰 틀로 구현 해놓으면 관리를 할 수 있는 수준이기에 많이 쓰입니다.

달라지는 점은 prev pointer 가 있다는 것이고 그에 따른 코드가 추가된다는 것 빼고는 링크드 리스트와 다를 게 없습니다. 링크드 리스트의 구현을 보시려면 아래 포스팅을 참고해주시면 감사하겠습니다.

 

[자료구조]링크드 리스트(Linked list)

 

파이썬으로 구현

더블 링크드 리스트는 양방향으로 연결되는 대칭적 구조입니다.

전체 구조가 양쪽 모두 똑같이 존재해야 하는게 주요 특징입니다. 그렇기 때문에 head=tail로 됩니다. 

node를 추가할 때도 prev 와 next를 연결시켜줘야 합니다. 제거할 때도 prev와 next 수정을 합니다.

class Node:
    def __init__(self, data,prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next
    
class NodeMg:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head      #어느쪽이든 맨 끝은 head
        
    def add(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new
        
    def output(self):              #head를 정하면 양쪽으로 포인터가 모두 있으므로 next로 출력
        node = self.head
        while node:
            print (node.data)
            node = node.next
    
    def search_from_head(self,data):
        if self.head == None:
            return False
        node = self.head
        while node:
            if node.data==data:
                return node
            else:
                node = node.next
        return False
    
    def search_from_tail(self,data):
        if self.head == None:
            return False
        node = self.tail
        while node:
            if node.data==data:
                return node
            else:
                node = node.prev
        return False
    
    
    def delete(self, data):
        if self.head == None:
            print ("No Node")
            return
        
        if self.head.data == data:
            temp_save = self.head
            self.head = self.head.next
            del temp_save
        else:
            node = self.head
            while node.next:
                if node.next.data == data:
                    temp_save = node.next
                    node.next = node.next.next
                    node.next.prev = node.next.prev.prev
                    del temp_save
                    return
                else:
                    node = node.next

숫자 10개를 넣고 해보면 다음과 같이 나옵니다.

dl_list = NodeMg(0)
for data in range(1, 10):
    dl_list.add(data)
dl_list.output()
0
1
2
3
4
5
6
7
8
9

dl_list.delete(2)
dl_list.output()
0
1
3
4
5
6
7
8
9

node = dllist.search_from_head(3)
node.data
>>> 3
node.prev.data
>>> 1
node.next.data
>>> 4

 

지금까지의 코드는 기본 틀이고 이걸 응용해서 많은걸 할 수 있습니다. 

도움이 되셨길 바랍니다.

이상으로 포스팅을 마치겠습니다.