자료구조: Linked List

Linked List?

단순한 선형 배열(리스트)을 선언하면 메모리를 연속적으로 할당한다. 만약, 배열 내의 값 삭제가 필요하거나 추가가 필요한 경우 값들의 자리 교체가 필요하다. 이와 달리 연결 리스트는 연속적인 공간을 사용하지 않고, 각각의 노드들을 연결한 구조로 연결되어 중간의 값 삭제가 빈번하게 일어나는 자료를 관리하기에 보다 효율적이다.

 

---

•  

Single Linked List

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


class SingleLinkedList:
    def __init__(self, data):
        self.head = Node(data)

    def add(self, data):
        node = self.head
        while node.next:
            node = node.next
        node.next = Node(data)

    def delete(self, data):
        if self.head is None:
            return -1

        if self.head.data == data:
            temp, self.head = self.head, self.head.next
            del temp
        else:
            node = self.head
            while node.next:
                if node.next.data == data:
                    temp, node.next = node.next, node.next.next
                    del temp
                    break
                else:
                    node = node.next

    def display(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next

• add, delete, display 메소드를 구현하여 단순 연결 리스트 클래스를 구현하였다.
• 단순 연결 리스트는 next(tail)을 통해 각 리스트에 접근할 수 있는 구조적 한계를 가지고 있다.
• 이외의 값을 탐색하는 메소드를 추가하여 다양한 방면으로 활용할 수 있다.

 

Double Linked List

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


class DoubleLinkedList:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head
        self.num_of_node = 1

    def add_first(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node
        self.num_of_node += 1

    def add_last(self, data):
        new_node = Node(data)
        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node
        self.num_of_node += 1

    def delete(self, data):
        if self.head is None:
            return False

        if self.head.data == data:
            temp, self.head = self.head, self.head.next
            del temp
        node = self.head
        while node.next:
            if node.next.data == data:
                temp, node.next = node.next, node.next.next
                node.next.prev = node
                del temp
                return True
            node = node.next
        return False

    def display(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next

    def display_rev(self):
        node = self.tail
        while node:
            print(node.data)
            node = node.prev

    def ins_front(self, n, data):
        if not n:
            self.add_first(data)
            return True
        elif n == self.num_of_node - 1:
            self.add_last(data)
            return True
        else:
            if self.num_of_node < n:
                return False

            node = self.head.next
            while node.next:
                node = node.next

            new_node = Node(data)
            new_node.next = node.next
            node.next.prev = new_node
            node.next = new_node
            new_node.prev = node
            self.num_of_node += 1
            return True
    
    def ins_back(self, n, data):
        if not n:
            self.add_last(data)
            return True
        elif n == self.num_of_node - 1:
            self.add_first(data)
            return True
        else:
            if self.num_of_node < n:
                return False

            node = self.tail.prev
            while node.next:
                node = node.prev

            new_node = Node(data)
            new_node.prev = node.prev
            node.next.next = new_node
            node.prev = new_node
            new_node.next = node
            self.num_of_node += 1
            return True

• 단순 연결 리스트와 달리 이중 연결 리스트는 prev, next를 통해 정방향 역방향으로 추가가 가능하다.
• 이를 위해 Node 클래스에 prev 멤버를 추가하고, head, prev를 통해 삽입 삭제가 가능한 메소드들을 추가하여 구현하였다.