[자료구조] Double Linked List (이중 연결 리스트) 구현

Double Linked List

# Single Linked List

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


class DoubleLinkedList:
    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None, self.head)
        self.head.next = self.tail
        self.size = 0

    def list_size(self):
        return self.size

    def is_empty(self):
        if self.size != 0:
            return False
        else:
            return True

    def select_node(self, idx):
        if idx >= self.size:
            print("Index Error")
            return None
        if idx == 0:
            return self.head
        if idx == self.size:
            return self.tail
        # head와 tail중 더 가까운것 찾기
        if idx >= self.size//2:
            target = self.head
            for _ in range(idx):
                target = target.next
            return target
        else:
            target = self.tail
            for _ in range(self.size - idx):
                target = target.prev
            return target

    def insert_first(self, item):
        if self.is_empty():
            self.head = Node(item)
            self.tail = Node(None, self.head)
            self.head.next = self.tail
        else:
            tmp = self.head
            self.head = Node(item, None, self.head)
        self.size += 1

    def append(self, item):
        if self.is_empty():
            self.head = Node(item)
            self.tail = Node(None, self.head)
            self.head.next = self.tail
        else:
            tmp = self.tail.prev
            new_node = Node(item, tmp, self.tail)
            tmp.next = new_node
            self.tail.prev = new_node
        self.size += 1

    def insert(self, item, idx):
        if self.is_empty():
            self.head = Node(item)
            self.tail = Node(None, self.head)
            self.head.next = self.tail
            self.size += 1
        elif idx == 0:
            self.insert_first(self, item)
        else:
            tmp = self.select_node(idx)
            if tmp == None:
                return
            if tmp == self.head:
                self.insert_first(item)
            elif tmp == self.tail:
                self.append(item)
            else:
                tmp_prev = tmp.prev
                new_node = Node(item, tmp_prev, tmp)
                tmp_prev.next = new_node
                tmp.prev = new_node
            self.size += 1

    def delete(self, idx):
        if self.is_empty():
            print('Underflow: Empty Linked List Error')
            return
        else:
            tmp = self.select_node(idx)
            if tmp == None:
                return
            elif tmp == self.head:
                tmp = self.head
                self.head = self.head.next
            elif tmp == self.tail:
                tmp == self.tail
                self.tail = self.tail.prev
            else:
                tmp.prev.next = tmp.next
                tmp.next.prev = tmp.prev
            del(tmp)
            self.size -= 1

    def print_list(self):
        target = self.head
        while target != self.tail:
            if target.next != self.tail:
                print(target.item, '<=> ', end='')
                target = target.next
            else:
                print(target.item)
                target = target.next


double_linked_list = DoubleLinkedList()

print('<insert>')
for i in range(5):
    double_linked_list.insert_first(i)
double_linked_list.print_list()
print('size : ', double_linked_list.list_size())
print()

print('<delete>')
for i in range(5):
    double_linked_list.delete(0)
    double_linked_list.print_list()
print('size : ', double_linked_list.list_size())


"""
<결과>
<insert>
4 <=> 3 <=> 2 <=> 1 <=> 0
size :  5

<delete>
3 <=> 2 <=> 1 <=> 0
2 <=> 1 <=> 0
1 <=> 0
0
size :  0
"""

Single Linked List (단순 연결 리스트) 와는 달리 previous node와 next node 모두를 link하고있어 탐색이 더 빠르다. 단순연결리스트에서는 원하는 target을 찾기 위해 head부터 다 보아야 했지만 이중연결리스트에서는 head와 tail중 더 가까운 값부터 탐색하므로 더 빠르다.

 

참고자료

• 공대생의 차고