[python] 자료구조 - 링크드 리스트(Linked List)

링크드 리스트(Linked List)

 

출처: https://en.wikipedia.org/wiki/Linked_list

 

배열은 정해진 공간에 데이터를 순차적으로 적재한다. 반면, 링크드 리스트는 노드가 다음 노드(데이터)의 주소값을 가지고 있다. 따라서 배열이 공간의 크기를 미리 할당 해줘야 한다는 단점을 해결할 수 있다. 단, 저장 측면에서는 비효율적이다.

 

 

 

구조

 

노드(Node): 데이터를 저장하는 단위 (데이터와 포인터로 구성)

 

포인터(Pointer): 각각의 노드 안에서 다음 노드의 주소(위치)를 가짐

 

 

위 이미지에서 정사각형 두개가 붙은 구조가 하나의 노드이고,

화살표가 포인터다. 즉 여러개의 노드들이 연결된 구조다.

 

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


class LinkedList:
    def __init__(self, value=None):
        if value is None:
            self.head = None
            self.tail = None
        else:
            self.head = Node(value)
            self.tail = self.head

    def add(self, value):
        if self.head is None:
            self.head = Node(value)
            self.tail = self.head
        else:
            new_node = Node(value)
            self.tail.next = new_node
            self.tail = new_node

    def delete(self, value):
        node = self.head
        prev = None

        while node is not None:
            if node.value == value:
                if node == self.head:
                    self.head = self.head.next
                else:
                    prev.next = node.next

                return True

            prev = node
            node = node.next

        return False

    def show(self):
        node = self.head

        while node is not None:
            print(node.value, end=' ')
            node = node.next

        print()

    def reverse(self):
        node = self.head
        new_head = None

        while node is not None:
            prev = new_head
            new_head = node
            node = node.next
            new_head.next = prev

        self.tail = self.head
        self.head = new_head


linked_list = LinkedList()

for i in range(10):
    linked_list.add(i)
linked_list.show()

linked_list.reverse()
linked_list.show()

for i in range(10, 0, -1):
    linked_list.delete(i)
    linked_list.show()

 

2021.12.06. 코드 수정