개발/Python

[Python] 파이썬: 링크드리스트(Linked List) - 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List)

일요일좋아하는사람 2025. 5. 12. 20:27
728x90
반응형

파이썬에서 링크드 리스트(Linked List)는 데이터 구조 중 하나로, 배열과는 달리 요소들이 메모리상에 연속적으로 저장되지 않고, 각 요소가 다음 요소에 대한 참조(포인터)를 가지고 있는 구조입니다. 파이썬 자체에서는 내장 자료형으로 링크드 리스트를 제공하지 않지만, 클래스를 활용하여 직접 구현할 수 있습니다. 이 글에서는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List) 등 다양한 형태의 링크드 리스트에 대해 설명하고, 각 구조의 특징과 사용법, 구현 방법, 옵션 등을 자세히 다루겠습니다.

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

역할

단일 연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지는 구조입니다. 데이터를 순차적으로 저장하면서 앞에서부터 끝까지 한 방향으로만 접근할 수 있습니다.

사용법

클래스를 이용해 Node와 LinkedList를 구현합니다.

Node 클래스

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

LinkedList 클래스

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

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

    def print_list(self):
        curr_node = self.head
        while curr_node:
            print(curr_node.data, end=" -> ")
            curr_node = curr_node.next
        print("None")

예제 및 결과

sll = SinglyLinkedList()
sll.append(10)
sll.append(20)
sll.append(30)
sll.print_list()

결과:

10 -> 20 -> 30 -> None

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

역할

이중 연결 리스트는 각 노드가 다음 노드뿐만 아니라 이전 노드에 대한 포인터도 가지고 있어 양방향으로 탐색이 가능합니다.

사용법

Node 클래스에서 prev 포인터를 추가하고, 리스트 조작 메서드를 구현합니다.

Node 클래스

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

DoublyLinkedList 클래스

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

    def append(self, data):
        new_node = DNode(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def print_forward(self):
        node = self.head
        while node:
            print(node.data, end=" <-> ")
            node = node.next
        print("None")

    def print_backward(self):
        node = self.head
        while node and node.next:
            node = node.next
        while node:
            print(node.data, end=" <-> ")
            node = node.prev
        print("None")

예제 및 결과

dll = DoublyLinkedList()
dll.append(100)
dll.append(200)
dll.append(300)
dll.print_forward()
dll.print_backward()

결과:

100 <-> 200 <-> 300 <-> None
300 <-> 200 <-> 100 <-> None

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

역할

원형 연결 리스트는 마지막 노드가 다시 처음 노드를 가리키도록 하여 리스트의 끝과 처음이 연결된 구조입니다. 반복적인 순회에 유리합니다.

사용법

마지막 노드의 next가 head를 가리키게 구현합니다.

Node 클래스

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

CircularLinkedList 클래스

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

    def append(self, data):
        new_node = CNode(data)
        if not self.head:
            self.head = new_node
            self.head.next = self.head
            return
        temp = self.head
        while temp.next != self.head:
            temp = temp.next
        temp.next = new_node
        new_node.next = self.head

    def print_list(self):
        if not self.head:
            return
        temp = self.head
        while True:
            print(temp.data, end=" -> ")
            temp = temp.next
            if temp == self.head:
                break
        print("(head)")

예제 및 결과

cll = CircularLinkedList()
cll.append(5)
cll.append(15)
cll.append(25)
cll.print_list()

결과:

5 -> 15 -> 25 -> (head)

이 글에서는 파이썬으로 구현할 수 있는 다양한 링크드 리스트 구조와 그 사용법을 알아보았습니다. 각 구조는 특정 상황에서 유용하게 사용될 수 있으며, 자료의 삽입, 삭제, 순회 방식에 따라 적절한 리스트 구조를 선택하는 것이 중요합니다.

728x90
반응형