Listy połączone w Pythonie: poradnik z przykładami

Lista połączona to struktura danych, która odgrywa kluczową rolę w organizacji i zarządzaniu danymi. Zawiera szereg węzłów przechowywanych w losowych miejscach w pamięci, co pozwala na efektywne zarządzanie pamięcią. Każdy węzeł listy połączonej zawiera dwa główne elementy: część z danymi oraz odniesienie do następnego węzła w sekwencji.

Jeśli na pierwszy rzut oka brzmi to skomplikowanie, nie martw się!

Rozłożymy temat na czynniki pierwsze, aby wyjaśnić, czym są listy połączone, dlaczego ich używamy i jakie dają unikalne korzyści.

Dlaczego listy połączone?

Listy połączone powstały, by przezwyciężyć różne wady związane z przechowywaniem danych w zwykłych listach i tablicach, jak opisano poniżej:

Łatwość wstawiania i usuwania

W listach wstawienie lub usunięcie elementu w dowolnym miejscu poza końcem wymaga przesunięcia wszystkich kolejnych elementów na inne pozycje. Ten proces ma złożoność czasową O(n) i może znacząco pogorszyć wydajność, zwłaszcza gdy lista rośnie. Jeśli nie znasz jeszcze działania list lub ich implementacji, możesz przeczytać nasz poradnik o listach w Pythonie.

Listy połączone działają jednak inaczej. Przechowują elementy w różnych, nieciągłych obszarach pamięci i łączą je wskaźnikami do kolejnych węzłów. Taka struktura pozwala dodawać lub usuwać elementy w dowolnym miejscu, po prostu modyfikując łącza, aby włączyć nowy element lub pominąć usunięty.

Gdy masz bezpośrednie odniesienie do węzła w punkcie wstawienia lub usunięcia, sama operacja ma złożoność O(1). Nadal jednak znalezienie tej pozycji wymaga przejścia O(n), więc korzyść O(1) dotyczy tylko sytuacji, gdy już trzymasz wskaźnik do odpowiedniego węzła (np. gdy pracujesz na początku listy).

Dynamiczny rozmiar

Listy w Pythonie to dynamiczne tablice, co oznacza, że dają możliwość modyfikowania rozmiaru.

Jednak proces ten obejmuje serię złożonych operacji, w tym realokację tablicy do nowego, większego bloku pamięci. Taka realokacja jest nieefektywna, ponieważ elementy są kopiowane do nowego bloku, potencjalnie rezerwując więcej miejsca, niż jest od razu potrzebne.

Z kolei listy połączone mogą rosnąć i kurczyć się dynamicznie, bez potrzeby realokacji czy zmiany rozmiaru. Dlatego są preferowane w zadaniach wymagających dużej elastyczności.

Wydajność pamięciowa

Listy alokują pamięć dla wszystkich elementów w jednym ciągłym bloku. Jeśli lista musi urosnąć poza początkowy rozmiar, musi przydzielić nowy, większy ciągły blok pamięci, a następnie skopiować do niego wszystkie istniejące elementy. Ten proces jest czasochłonny i nieefektywny, zwłaszcza przy dużych listach. Z drugiej strony, jeśli początkowy rozmiar listy zostanie przeszacowany, niewykorzystana pamięć się marnuje.

Dla porównania, listy połączone alokują pamięć dla każdego elementu osobno. Taka struktura prowadzi do lepszego wykorzystania pamięci, ponieważ pamięć dla nowych elementów można przydzielać w miarę ich dodawania.

Kiedy używać list połączonych?

Choć listy połączone zapewniają pewne korzyści względem zwykłych list i tablic, takie jak dynamiczny rozmiar i wydajność pamięciowa, mają też ograniczenia. Ponieważ dla każdego elementu trzeba przechowywać wskaźnik do kolejnego węzła, zużycie pamięci na element jest większe. Ta struktura nie pozwala też na bezpośredni dostęp do danych. Dostęp do elementu wymaga sekwencyjnego przejścia od początku listy, co daje złożoność wyszukiwania O(n).

Wybór między listą połączoną a tablicą zależy od konkretnych potrzeb aplikacji. Listy połączone są najbardziej przydatne, gdy:

• Musisz często wstawiać i usuwać wiele elementów
• Rozmiar danych jest nieprzewidywalny lub często się zmienia
• Bezpośredni dostęp do elementów nie jest wymagany
• Zbiór danych zawiera duże elementy lub struktury

Typy list połączonych

Istnieją trzy typy list połączonych, z których każdy oferuje unikalne zalety w różnych scenariuszach. Są to:

Listy jednokierunkowe

Lista jednokierunkowa

Lista jednokierunkowa to najprostszy typ listy połączonej, w której każdy węzeł zawiera dane oraz odniesienie do następnego węzła w sekwencji. Można ją przechodzić tylko w jednym kierunku — od głowy (pierwszego węzła) do ogona (ostatniego węzła).

Każdy węzeł listy jednokierunkowej zazwyczaj składa się z dwóch części:

• Dane: Rzeczywista informacja przechowywana w węźle.
• Wskaźnik next: Odniesienie do następnego węzła. Wskaźnik next ostatniego węzła jest zwykle ustawiony na null.

Ponieważ te struktury można przechodzić tylko w jednym kierunku, dostęp do konkretnego elementu po wartości lub indeksie wymaga rozpoczęcia od głowy i sekwencyjnego przechodzenia przez węzły, aż znajdziesz poszukiwany węzeł. Operacja ta ma złożoność O(n), co czyni ją mniej wydajną dla dużych list.

Wstawianie i usuwanie węzła na początku listy jednokierunkowej jest bardzo wydajne — ma złożoność O(1). Jednak wstawianie i usuwanie w środku lub na końcu wymaga przejścia listy do danego miejsca, co skutkuje złożonością O(n).

Projekt list jednokierunkowych sprawia, że są użyteczną strukturą danych przy operacjach wykonywanych na początku listy.

Listy dwukierunkowe

Lista dwukierunkowa

Jedną z wad list jednokierunkowych jest to, że można je przechodzić tylko w jednym kierunku i w razie potrzeby nie da się wrócić do poprzedniego węzła. To ograniczenie utrudnia operacje wymagające dwukierunkowej nawigacji.

Listy dwukierunkowe rozwiązują ten problem, dodając w każdym węźle dodatkowy wskaźnik, dzięki czemu listę można przechodzić w obu kierunkach. Każdy węzeł listy dwukierunkowej zawiera trzy elementy: dane, wskaźnik do następnego węzła oraz wskaźnik do poprzedniego węzła.

Listy cykliczne

Lista cykliczna

Listy cykliczne to wyspecjalizowana forma list połączonych, w której ostatni węzeł wskazuje z powrotem na pierwszy, tworząc strukturę kołową. Oznacza to, że w przeciwieństwie do list jednokierunkowych i dwukierunkowych, które widzieliśmy do tej pory, lista cykliczna się nie kończy — zamiast tego zapętla się.

Cykliczny charakter list cyklicznych sprawia, że idealnie nadają się do scenariuszy wymagających ciągłego przechodzenia, takich jak gry planszowe, w których po ostatnim graczu wraca się do pierwszego, albo algorytmy obliczeniowe, jak planowanie z użyciem algorytmu round-robin.

Podsumowanie złożoności czasowej

Warto na szybko porównać listy połączone z listami Pythona:

Najważniejszy wniosek: listy połączone wygrywają we wstawieniach i usunięciach na początku (O(1)), ale przegrywają w pozostałych przypadkach. Jeśli nie dodajesz ani nie usuwasz często elementów na początku swojej struktury danych, zwykła lista Pythona będzie prawdopodobnie lepszym wyborem.

Jak stworzyć listę połączoną w Pythonie

Skoro już wiemy, czym są listy połączone, dlaczego ich używamy i jakie mają odmiany, przejdźmy do implementacji tych struktur w Pythonie. Notes do tego poradnika znajdziesz także w tym workbooku DataLab; jeśli utworzysz kopię, możesz edytować i uruchamiać kod. To świetna opcja, jeśli napotkasz problemy z uruchomieniem kodu u siebie!

Inicjalizacja węzła

Jak już wiemy, węzeł to element listy połączonej, który przechowuje dane i odniesienie do następnego węzła w sekwencji. Oto jak możesz zdefiniować węzeł w Pythonie:

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

    def __repr__(self):
        return f"Node({self.data})"

Powyższy kod inicjalizuje węzeł, wykonując dwie główne czynności: atrybut „data” węzła otrzymuje wartość reprezentującą informację, którą węzeł ma przechowywać. Atrybut „next” reprezentuje adres następnego węzła. Obecnie jest ustawiony na None, co oznacza, że nie łączy się z żadnym innym węzłem na liście. Gdy będziemy dodawać nowe węzły do listy połączonej, ten atrybut zostanie zaktualizowany, aby wskazywać kolejny węzeł.

Tworzenie klasy listy połączonej

Następnie musimy utworzyć klasę listy połączonej. Będzie ona kapsułkować wszystkie operacje zarządzania węzłami, takie jak wstawianie i usuwanie. Zaczniemy od zainicjowania listy połączonej:

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

Ustawiając self.head na None, mówimy, że lista połączona jest początkowo pusta i nie ma w niej węzłów, do których można by się odwołać. Teraz przejdziemy do zapełniania listy poprzez wstawianie nowych węzłów.

Wstawianie nowego węzła na początku listy połączonej

W klasie LinkedList dodamy metodę tworzącą nowy węzeł i umieszczającą go na początku listy:

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node

Za każdym razem, gdy wywołasz powyższą metodę, tworzony jest nowy węzeł z podanymi danymi. Wskaźnik next tego węzła jest ustawiony na obecną głowę listy, co umieszcza nowy węzeł przed istniejącymi. Na końcu nowo utworzony węzeł staje się głową listy.

Teraz zapełnimy tę listę połączoną serią słów, aby lepiej zrozumieć, jak działa operacja wstawiania. W tym celu najpierw utwórzmy metodę służącą do przechodzenia i wypisywania zawartości listy:

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line

Powyższa metoda wypisze zawartość naszej listy połączonej. Przejdźmy teraz do użycia zdefiniowanych metod, aby zapełnić listę serią słów: „the quick brown fox”.

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()

Powyższe linie kodu powinny dać następujący wynik:

"the quick brown fox"

Wstawianie nowego węzła na końcu listy połączonej

Teraz utworzymy metodę insertAtEnd w klasie LinkedList, aby dodać nowy węzeł na końcu listy. Jeśli lista jest pusta, nowy węzeł stanie się jej głową. W przeciwnym razie zostanie dołączony do obecnego ostatniego węzła. Zobaczmy, jak to działa w praktyce:

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

Powyższa metoda zaczyna od utworzenia nowego węzła. Następnie sprawdza, czy lista jest pusta — jeśli tak, nowy węzeł zostaje przypisany jako głowa listy. W przeciwnym przypadku przechodzi listę, aby znaleźć ostatni węzeł, i ustawia jego wskaźnik na nowy węzeł.

Musimy teraz dodać tę metodę do naszej klasy LinkedList i użyć jej do dodania słowa na końcu listy. Aby to zrobić, zmodyfikuj funkcję main tak, aby wyglądała następująco:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()

Zauważ, że po prostu wywołaliśmy metodę insertAtEnd, aby wydrukować słowo „jumps” na końcu listy. Powyższy kod powinien dać następujący wynik:

"the quick brown fox jumps"

Usuwanie węzła z początku listy połączonej

Usunięcie pierwszego węzła listy połączonej jest proste, ponieważ polega jedynie na ustawieniu głowy listy tak, by wskazywała drugi węzeł. W ten sposób pierwszy węzeł przestaje być częścią listy. Aby to zrobić, dodaj do klasy LinkedList następującą metodę:

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head

Usuwanie węzła z końca listy połączonej

Aby usunąć ostatni węzeł listy połączonej, musimy przejść listę, znaleźć przedostatni węzeł i zmienić jego wskaźnik next na None. Dzięki temu ostatni węzeł przestanie być częścią listy. Skopiuj i wklej poniższą metodę do swojej klasy LinkedList, aby to zrobić:

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None

Powyższa metoda najpierw sprawdza, czy lista połączona jest pusta, i jeśli tak — zwraca komunikat do użytkownika. W przeciwnym razie, jeśli lista zawiera pojedynczy węzeł, ten węzeł zostaje usunięty. W listach z wieloma węzłami metoda lokalizuje przedostatni węzeł i aktualizuje jego odniesienie do następnego węzła na None.

Zaktualizujmy teraz funkcję main, aby usuwać elementy z początku i końca listy połączonej:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()

Powyższy kod wydrukuje listę przed i po usunięciach, pokazując, jak działają operacje wstawiania i usuwania w listach połączonych. Po uruchomieniu kodu powinieneś zobaczyć następujący wynik:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox

Wyszukiwanie konkretnej wartości w liście połączonej

Ostatnia operacja, której się tutaj nauczymy, to odszukiwanie konkretnej wartości w liście połączonej. Aby to zrobić, metoda powinna zacząć od głowy listy i iterować przez każdy węzeł, sprawdzając, czy dane w węźle odpowiadają szukanej wartości. Oto praktyczna implementacja tej operacji:

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 

Aby znaleźć konkretne wartości w utworzonej przez nas liście połączonej, zaktualizuj funkcję main, aby uwzględniała właśnie stworzoną metodę wyszukiwania:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find

Powyższy kod da następujący wynik:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list

Słowo „quick” zostało pomyślnie odnalezione w liście połączonej, ponieważ występuje na pierwszej pozycji listy. Natomiast słowa „lazy” nie ma na liście, dlatego nie zostało znalezione.

Na koniec

Jeśli dotarłeś aż tutaj — gratulacje! Masz już solidne podstawy dotyczące list połączonych: ich struktury, typów, sposobów dodawania i usuwania elementów oraz przechodzenia po liście.

Ale na tym podróż się nie kończy. Listy połączone to dopiero początek świata struktur danych i algorytmów. Oto kilka możliwych kolejnych kroków, które pogłębią twoje zrozumienie tematu:

Stwórz własny projekt

Wejdź w praktyczne zastosowania list połączonych, integrując je z projektem programistycznym lub data science. Listy połączone są używane do budowy systemów plików, konstruowania tablic mieszających (hash tables), a nawet tworzenia systemów nawigacji GPS i gier planszowych. Aby zacząć własne projekty, sprawdź nasze darmowe prowadzone projekty data science, które uczą rozwiązywania realnych problemów w Pythonie, R i SQL.

Poznaj struktury danych i algorytmy

Nauka innych struktur danych, takich jak drzewa, stosy i kolejki, to naturalny krok po zrozumieniu list połączonych. Te struktury rozwijają zasady list połączonych, pomagając efektywnie rozwiązywać szerszy zakres problemów obliczeniowych. Drzewa i drzewa binarne wyszukiwania, na przykład, rozszerzają koncepcję list połączonych do formy hierarchicznej, pozwalając każdemu węzłowi łączyć się z wieloma elementami w strukturze danych.

Jeśli te pojęcia brzmią dla ciebie obco, nie martw się! Datacamp ma cały kurs o strukturach danych i algorytmach w Pythonie, który przeprowadzi cię przez nie bardziej szczegółowo. Najpierw poznasz struktury danych takie jak stosy, drzewa, tablice mieszające, kolejki i grafy. W miarę postępów zrozumiesz algorytmy wyszukiwania i sortowania, co pomoże ci stać się bardziej efektywnym programistą i rozwiązywać problemy sprawniej.

Poznawanie zaawansowanych zagadnień list połączonych

W tym poradniku zaimplementowaliśmy listy jednokierunkowe, obejmując operacje takie jak wstawianie, usuwanie i przechodzenie.

Możesz pójść o krok dalej, poznając implementację list dwukierunkowych i cyklicznych. Skip lists to kolejne rozszerzenie list połączonych, które umożliwia szybsze wyszukiwanie, zapewniając szybszy dostęp do elementów.

Poznanie tych zaawansowanych struktur danych wyniesie twoje umiejętności techniczne na wyższy poziom i znacząco usprawni twoje programowanie, przygotowując cię na bardziej złożone wyzwania w data science, inżynierii oprogramowania i uczeniu maszynowym.

Jeśli wolisz bardziej początkujące wprowadzenie do programowania, zanim zmierzysz się z tymi zaawansowanymi tematami, sprawdź nasz ścieżkę umiejętności Python Programming. Oferuje serię kursów, które nauczą cię podstaw języka.