[파이썬] 연결 리스트 (Linked Lists)의 종류와 특징

01 Sep 2023

python

연결 리스트(Linked Lists)는 데이터 요소들을 순서대로 연결하여 저장하는 자료 구조입니다. 이러한 자료 구조에는 다양한 종류와 특징이 있습니다. 이번 글에서는 파이썬에서 연결 리스트의 종류와 특징을 알아보도록 하겠습니다.

1. 단일 연결 리스트 (Singly Linked List)

단일 연결 리스트는 각 노드가 다음 노드를 가리키는 포인터를 가지고 있는 연결 리스트입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다. 이러한 구조로 인해 데이터 요소들이 순차적으로 저장되며, 삽입과 삭제 연산이 빠르게 이루어집니다. 하지만 특정 위치의 데이터에 접근하기 위해서는 처음부터 순차적으로 접근해야 하기 때문에 검색 연산에는 시간이 오래 걸릴 수 있습니다.

예제 코드

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

2. 이중 연결 리스트 (Doubly Linked List)

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있는 연결 리스트입니다. 각 노드는 데이터, 이전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터로 이루어져 있습니다. 이중 연결 리스트의 가장 큰 특징은 양방향으로 탐색이 가능하다는 것입니다. 따라서 데이터 요소들을 양방향으로 삽입, 삭제하는 것이 가능합니다. 하지만 이중 연결 리스트는 단일 연결 리스트보다 더 많은 메모리를 사용하고, 구현이 복잡하다는 단점이 있습니다.

예제 코드

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.prev = current

3. 원형 연결 리스트 (Circular Linked List)

원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 연결 리스트입니다. 따라서 마지막 노드 이후에 첫 번째 노드가 오게 되어 순환을 형성합니다. 이러한 구조로 인해 연결 리스트의 끝에 도달했을 때 첫 번째 노드로 다시 이동하여 연산을 계속할 수 있습니다. 원형 연결 리스트는 특히 순환적인 구조가 필요한 경우 유용하게 사용됩니다.

예제 코드

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

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.head.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

연결 리스트는 파이썬에서 유용하게 활용되는 자료 구조 중 하나입니다. 위에서 소개한 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 각각의 특징을 이해하고 적절하게 활용하면 데이터를 효율적으로 관리할 수 있습니다.