파이썬 링크드 리스트 사용법

Python 연결 리스트

이해하기

연결 리스트는 정렬된 객체의 모음이다.
연결 리스트는 일반적인 리스트와는 다르게 데이터를 메모리에 저장한다.
리스트는 데이터의 참조를 연속적인 메모리 블록에 저장하지만, 연결 리스트는 자체 요소의 일부로 데이터의 참조를 저장한다.
각 노드는 두 개의 필드를 가진다:
1. 데이터: 노드에 저장되는 값
2. 다음: 리스트의 다음 노드를 가리키는 참조
연결 리스트의 첫 번째 노드는 “head”로 불리며, 리스트 순회의 시작점으로 사용된다.
마지막 노드는 다음 참조가 “None”을 가리키도록 설정하여 리스트의 끝을 결정한다.

collections.deque 소개

collections.deque는 파이썬에서 연결 리스트를 사용하기 위한 모듈이다.
이 모듈은 양방향 연결 리스트로 구현되어 있어서 앞과 뒤에서 모두 데이터의 삽입과 삭제가 가능하다.
큐와 스택을 구현하는 데에도 사용할 수 있다.

직접 만드는 연결 리스트

연결 리스트 생성

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

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

연결 리스트 순회

def traverse(self):
    current = self.head

    while current:
        print(current.data)
        current = current.next

새 노드 삽입

def insert(self, data):
    new_node = Node(data)

    if self.head is None:
        self.head = new_node
    else:
        current = self.head

        while current.next:
            current = current.next

        current.next = new_node

노드 삭제

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

    if self.head.data == data:
        self.head = self.head.next
        return

    current = self.head

    while current.next:
        if current.next.data == data:
            current.next = current.next.next
            return

        current = current.next

고급 연결 리스트 활용

양방향 연결 리스트 사용

collections.deque를 사용하여 양방향 연결 리스트를 생성할 수 있다.
아래는 사용 예시이다.

from collections import deque

d = deque()
d.append(1)
d.append(2)
d.append(3)
d.appendleft(0)
print(d)  # deque([0, 1, 2, 3])

d.pop()
d.popleft()
print(d)  # deque([1, 2])

원형 연결 리스트 사용

원형 연결 리스트는 마지막 노드의 다음 참조가 첫 번째 노드를 가리키는 리스트이다.
다음과 같이 원형 연결 리스트를 만들 수 있다.

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

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

    def insert(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head

            while current.next != self.head:
                current = current.next

            current.next = new_node
            new_node.next = self.head

결론

연결 리스트는 정렬된 객체의 모음이다.
연결 리스트는 리스트와는 다르게 데이터를 메모리에 저장한다.
collections.deque를 사용하여 연결 리스트를 구현할 수 있다.
직접 연결 리스트를 만들 수도 있다.
양방향 연결 리스트와 원형 연결 리스트는 고급 연결 리스트의 한 종류이다.