Python 단일 연결 목록 구현

Python에서 단일 연결 목록을 구현하는 방법을 알아보세요. 동적 메모리 할당, 노드 작업, 삽입, 순회 및 삭제를 살펴보세요.

개요

연결된 목록은 요소가 인접한 메모리 위치에 저장되지 않는 선형 데이터 구조입니다. 대신, 각 요소(노드라고 함)는 시퀀스의 다음 노드에 대한 참조를 포함하는 별도의 개체입니다.

기존 배열에 비해 연결된 목록의 주요 이점은 동적 크기 조정과 처음에 일정한 O(1) 시간에 요소를 삽입하거나 삭제할 수 있는 기능입니다. 그러나 인덱스로 요소에 액세스하려면 선형 순회가 필요하므로 O(n) 시간이 걸립니다.

Python에서는 데이터 및 참조 포인터를 저장하는 Node 클래스와 헤드 노드, 헤드 또는 테일 삽입 및 삭제를 관리하는 LinkedList 클래스를 정의하여 연결 목록을 구현합니다.

코드 및 실행 출력

Python의 단일 연결 목록 구현으로 노드 생성, 추가 및 목록 순회를 보여줍니다.

linked_list.py

에디터에서 사용해 보세요

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

class LinkedList:
    def __init__(self):
        self.head = None
        
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        
    def delete(self, key):
        curr = self.head
        if curr and curr.data == key:
            self.head = curr.next
            curr = None
            return
        prev = None
        while curr and curr.data != key:
            prev = curr
            curr = curr.next
        if not curr:
            return
        prev.next = curr.next
        curr = None
        
    def display(self):
        elements = []
        curr = self.head
        while curr:
            elements.append(str(curr.data))
            curr = curr.next
        print(" -> ".join(elements) + " -> None")

# Instantiate and build the linked list
llist = LinkedList()
llist.append("Node A")
llist.append("Node B")
llist.append("Node C")
print("Initial Linked List:")
llist.display()

print("Deleting 'Node B':")
llist.delete("Node B")
llist.display()

터미널 출력

Initial Linked List:
Node A -> Node B -> Node C -> None
Deleting 'Node B':
Node A -> Node C -> None

단계별 구현

텍스트 편집기에서 실행 취소-다시 실행 기능 구현
그래프, 스택, 큐와 같은 복잡한 데이터 구조 구축
삽입 및 삭제 빈도가 조회 작업보다 많은 목록 관리

자주 묻는 질문

단일 연결 목록과 이중 연결 목록의 차이점은 무엇입니까?

단일 연결 목록에서는 각 노드가 다음 노드만 가리킵니다. 이중 연결 목록에서 각 노드에는 다음 노드와 이전 노드에 대한 참조가 포함되어 있어 추가 메모리를 사용하여 양방향 탐색이 가능합니다.

Python에 LinkedList 클래스가 내장되어 있지 않은 이유는 무엇입니까?

Python 배열(목록)은 동적 배열로 구현됩니다. Python의 메모리 관리 및CPython최적화 덕분에 표준 목록은 대부분의 작업에서 매우 빠르고 효율적이므로 내장 연결 목록의 실제 필요성이 줄어듭니다.