Implementacja listy pojedynczo połączonej w Pythonie

Dowiedz się, jak zaimplementować pojedynczo połączoną listę w Pythonie. Przeglądaj dynamiczną alokację pamięci, operacje na węzłach, wstawianie, przeglądanie i usuwanie.

Spróbuj w Edytorze

Przegląd

Lista połączona to liniowa struktura danych, w której elementy nie są przechowywane w sąsiadujących lokalizacjach pamięci. Zamiast tego każdy element (zwany węzłem) jest oddzielnym obiektem zawierającym odniesienie do następnego węzła w sekwencji.

Podstawową zaletą listy połączonej w porównaniu z tradycyjną tablicą jest jej dynamiczny rozmiar i możliwość wstawiania lub usuwania elementów na początku w stałym czasie O(1). Jednak dostęp do elementów według indeksu wymaga przechodzenia liniowego, co zajmuje czas O(n).

W Pythonie implementujemy połączoną listę, definiując klasę Node do przechowywania danych i wskaźnika referencyjnego oraz klasę LinkedList do zarządzania węzłem głównym, wstawkami na początku lub końcu oraz usunięciami.

Dane wyjściowe kodu i wykonania

Implementacja listy pojedynczo połączonej w Pythonie, prezentująca tworzenie węzłów, dołączanie i przeglądanie list.

linked_list.py

Spróbuj w Edytorze

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()

Wyjście terminala

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

Wdrażanie krok po kroku

Implementacja funkcji cofania i ponawiania w edytorach tekstu
Tworzenie złożonych struktur danych, takich jak wykresy, stosy i kolejki
Zarządzanie listami, w przypadku których częstotliwość wstawiania i usuwania przewyższa liczbę czynności wyszukiwania

Często zadawane pytania

Jaka jest różnica między listami pojedynczo i podwójnie połączonymi?

Na liście pojedynczo połączonej każdy węzeł wskazuje tylko następny węzeł. Na liście podwójnie połączonej każdy węzeł zawiera odniesienia zarówno do następnego, jak i poprzedniego węzła, umożliwiając dwukierunkowe przechodzenie kosztem dodatkowej pamięci.

Dlaczego Python nie ma wbudowanej klasy LinkedList?

Tablice (listy) Pythona są implementowane jako tablice dynamiczne. Dzięki zarządzaniu pamięcią w języku Python i optymalizacjiCPythonstandardowe listy są niezwykle szybkie i wydajne w przypadku większości zadań, co zmniejsza praktyczną potrzebę stosowania wbudowanej listy połączonej.

Powiązane tematy

Samouczek dotyczący struktury danych stosu w języku Python

Zaimplementuj stos LIFO w Pythonie. Uruchom nasz przykładowy interaktywny kod stosu, aby opanować limity push, pop, peek i pojemności.

Samouczek dotyczący struktury danych kolejki w języku Python

Opanuj operacje kolejkowe FIFO w Pythonie. Wykonaj i uruchom nasz interaktywny przykład kolejki prezentujący metody umieszczania w kolejce i usuwania z kolejki.