Python에서 링크 된 목록을 어떻게 구현합니까?-파이썬 튜토리얼-php.cn

Python에서 링크 된 목록을 어떻게 구현합니까?

Johnathan Smith

풀어 주다： 2025-03-10 17:18:43

원래의

619명이 탐색했습니다.

Python에서 링크 된 목록을 구현하는 방법 Python에서 링크 된 목록을 구현하려면 각 요소를 나타내는 클래스를 작성하고 목록을 전체적으로 관리하기위한 클래스를 작성하는 것이 포함됩니다. 각

에는 데이터와 시퀀스의 다음 노드에 대한 포인터가 포함됩니다.

클래스에는 일반적으로 삽입, 삭제, 검색 및 트래버스를위한 메소드가 포함됩니다.

기본 구현은 다음과 같습니다. Node LinkedList이 예제는 단일 링크 된 목록을 보여줍니다 (각 노드 포인트에만 포인트가 있습니다). 이중 연결 목록 (노드는 다음 노드와 이전 노드 모두를 가리 킵니다)도 가능합니다. 특정 작업에 대해 다른 성능 특성을 제공합니다. Node 다른 데이터 구조와 비교하여 Python의 링크 된 목록의 장점 및 단점 LinkedList

advantages : intamic size : intamic size : 런타임 중 쉽게 메모리를 사전 할당 해야하는 배열과 달리

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
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete_node(self, key):
        current = self.head
        if current and current.data == key:
            self.head = current.next
            current = None
            return

        prev = None
        while current and current.data != key:
            prev = current
            current = current.next

        if current is None:
            return

        prev.next = current.next
        current = None

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

#Example Usage
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.prepend(0)
llist.delete_node(2)
llist.print_list() # Output: 0 -> 1 -> 3 -> None

로그인 후 복사

효율적인 보존 및 삭제 : 링크 목록에 어떤 위치에 노드를 삽입하거나 삭제하는 데는 몇 가지 포인터를 업데이트하면 필요합니다. 연속 메모리 할당, 링크 된 목록은 특히 스파 스 데이터를 처리 할 때 배열보다 더 메모리 효율적 일 수 있습니다.

단점 :

임의의 액세스는 효과적입니다.

링크에서 특정 요소에 액세스하려면 목록에서 트래버를 사용해야합니다. O (1) 임의의 액세스.

추가 메모리 오버 헤드 : 각 노드는 다음 노드에 포인터를 저장하기 위해 추가 메모리가 필요합니다. 더 복잡한 구현 : 링크 된 목록은 일반적으로 배열 또는 다른 단순한 데이터 구조와 비교하여 배열 또는 다른 데이터 구조와 비교하여 더 복잡하고 디버그하는 데 더 복잡합니다. 목록 (동적 배열), 스택, 대기열 및 트리, 링크 된 목록은 자주 삽입 및 삭제가 임의의 위치에서 필요할 때 탁월합니다. 그러나 임의의 액세스가 중요하다면 배열 또는 파이썬 목록이 훨씬 더 나은 선택입니다.

이전 코드 예제의 delete_node 메소드는 선형 시간 삭제를 보여줍니다. 검색 효율성을 향상시키기 위해 특정 노드를 자주 검색 해야하는 경우 자체 밸런싱 바이너리 검색 트리 또는 해시 테이블 사용을 고려할 수 있습니다. 그러나 여기에는 데이터 스토리지의 상당한 구조 조정이 필요합니다.