Liste înlănțuite în Python: tutorial cu exemple

O listă înlănțuită este o structură de date care joacă un rol esențial în organizarea și gestionarea datelor. Conține o serie de noduri stocate în locații aleatorii în memorie, ceea ce permite o gestionare eficientă a memoriei. Fiecare nod dintr-o listă înlănțuită conține două componente principale: partea de date și o referință către următorul nod din secvență.

Dacă acest concept ți se pare complex la prima vedere, nu-ți face griji!

Îl vom descompune la elementele de bază pentru a explica ce sunt listele înlănțuite, de ce le folosim și avantajele lor specifice.

De ce liste înlănțuite?

Listele înlănțuite au fost create pentru a depăși diverse neajunsuri asociate cu stocarea datelor în liste obișnuite și tablouri, după cum este prezentat mai jos:

Ușurința inserării și ștergerii

În liste, inserarea sau ștergerea unui element într-o poziție diferită de sfârșit necesită mutarea tuturor elementelor următoare într-o altă poziție. Acest proces are o complexitate de timp O(n) și poate degrada semnificativ performanța, mai ales pe măsură ce lista crește. Dacă nu ești încă familiar cu modul în care funcționează listele sau cu implementarea lor, poți citi tutorialul nostru despre liste în Python.

Listele înlănțuite, însă, funcționează diferit. Ele stochează elemente în diverse locații neadiacente din memorie și le conectează prin pointeri către nodurile următoare. Această structură permite listelor înlănțuite să adauge sau să elimine elemente în orice poziție doar prin modificarea legăturilor pentru a include un element nou sau pentru a sări peste cel șters.

Odată ce ai o referință directă la nodul din punctul de inserare sau ștergere, operația în sine este O(1). Totuși, găsirea acelei poziții necesită în continuare parcurgere O(n), deci beneficiul O(1) se aplică doar când deții deja un pointer către nodul relevant (de exemplu, când lucrezi la începutul listei).

Dimensiune dinamică

Listele Python sunt tablouri dinamice, ceea ce înseamnă că oferă flexibilitate pentru a modifica dimensiunea.

Totuși, acest proces implică o serie de operații complexe, inclusiv realocarea tabloului într-un bloc de memorie nou, mai mare. O astfel de realocare este ineficientă, deoarece elementele sunt copiate într-un bloc nou, alocând posibil mai mult spațiu decât este necesar imediat.

În schimb, listele înlănțuite pot crește și se pot micșora dinamic fără a fi necesară realocarea sau redimensionarea. Acest lucru le face o opțiune preferabilă pentru sarcini care necesită multă flexibilitate.

Eficiență în utilizarea memoriei

Listele alocă memorie pentru toate elementele lor într-un bloc contiguu. Dacă o listă trebuie să crească dincolo de dimensiunea inițială, trebuie să aloce un nou bloc contiguu, mai mare, și apoi să copieze toate elementele existente în acest bloc nou. Acest proces este consumator de timp și ineficient, mai ales pentru liste mari. Pe de altă parte, dacă dimensiunea inițială a listei este supraestimată, memoria nefolosită este irosită.

În contrast, listele înlănțuite alocă memorie pentru fiecare element separat. Această structură duce la o utilizare mai bună a memoriei, deoarece memoria pentru elementele noi poate fi alocată pe măsură ce sunt adăugate.

Când ar trebui să folosești liste înlănțuite?

Deși listele înlănțuite oferă anumite beneficii față de listele și tablourile obișnuite, precum dimensiunea dinamică și eficiența memoriei, ele au și limitări. Deoarece pentru fiecare element trebuie stocați pointeri pentru a referi următorul nod, utilizarea memoriei per element este mai mare la listele înlănțuite. De asemenea, această structură de date nu permite accesul direct la date. Accesarea unui element necesită parcurgere secvențială de la începutul listei, rezultând o complexitate de timp O(n) pentru căutare.

Alegerea între o listă înlănțuită și un tablou depinde de nevoile specifice ale aplicației. Listele înlănțuite sunt cele mai utile când:

• Trebuie să inserezi și să ștergi frecvent multe elemente
• Dimensiunea datelor este imprevizibilă sau probabil să se schimbe frecvent
• Accesul direct la elemente nu este o cerință
• Setul de date conține elemente sau structuri mari

Tipuri de liste înlănțuite

Există trei tipuri de liste înlănțuite, fiecare oferind avantaje specifice pentru scenarii diferite. Aceste tipuri sunt:

Liste simplu înlănțuite

Listă simplu înlănțuită

O listă simplu înlănțuită este cel mai simplu tip de listă înlănțuită, în care fiecare nod conține niște date și o referință către următorul nod din secvență. Poate fi parcursă doar într-o singură direcție – de la cap (primul nod) la coadă (ultimul nod).

Fiecare nod dintr-o listă simplu înlănțuită este alcătuit, de obicei, din două părți:

• Date: Informația efectivă stocată în nod.
• Pointerul Next: O referință către următorul nod. Pointerul next al ultimului nod este, de obicei, setat la null.

Deoarece aceste structuri de date pot fi parcurse doar într-o singură direcție, accesarea unui element specific după valoare sau index necesită pornirea de la cap și deplasarea secvențială prin noduri până când este găsit nodul dorit. Această operație are o complexitate de timp O(n), ceea ce o face mai puțin eficientă pentru liste mari.

Inserarea și ștergerea unui nod la începutul unei liste simplu înlănțuite sunt foarte eficiente, cu o complexitate de timp O(1). Totuși, inserarea și ștergerea la mijloc sau la sfârșit necesită parcurgerea listei până la acel punct, ducând la o complexitate O(n).

Designul listelor simplu înlănțuite le face o structură de date utilă atunci când execuți operații care au loc la începutul listei.

Liste dublu înlănțuite

Listă dublu înlănțuită

Un dezavantaj al listelor simplu înlănțuite este că le putem parcurge doar într-o singură direcție și nu putem itera înapoi la nodul anterior dacă este necesar. Această constrângere limitează posibilitatea de a efectua operații ce necesită navigare bidirecțională.

Listele dublu înlănțuite rezolvă această problemă prin includerea unui pointer suplimentar în fiecare nod, asigurând parcurgerea listei în ambele direcții. Fiecare nod dintr-o listă dublu înlănțuită conține trei elemente: datele, un pointer către următorul nod și un pointer către nodul anterior.

Liste circulare

Listă circulară

Listele circulare sunt o formă specializată de listă înlănțuită în care ultimul nod indică înapoi către primul nod, creând o structură circulară. Asta înseamnă că, spre deosebire de listele simplu și dublu înlănțuite pe care le-am văzut până acum, lista circulară nu se termină; în schimb, se buclează.

Natura ciclică a listelor circulare le face ideale pentru scenarii ce trebuie parcurse continuu, cum ar fi jocurile de societate care revin de la ultimul jucător la primul sau algoritmi de calcul precum planificarea round-robin.

Rezumat al complexităților de timp

Este util să vezi dintr-o privire cum se compară listele înlănțuite cu listele Python:

Ideea principală: listele înlănțuite câștigă la inserări și ștergeri la cap (O(1)), dar pierd la restul. Dacă nu adaugi sau elimini frecvent elemente la începutul structurii tale de date, o listă Python obișnuită este probabil alegerea mai bună.

Cum creezi o listă înlănțuită în Python

Acum că înțelegem ce sunt listele înlănțuite, de ce le folosim și variațiile lor, să trecem la implementarea acestor structuri de date în Python. Notebook-ul pentru acest tutorial este disponibil și în acest workbook DataLab; dacă îți creezi o copie, poți edita și rula codul. Este o opțiune excelentă dacă întâmpini probleme la rularea codului pe cont propriu!

Inițializarea unui nod

După cum am învățat anterior, un nod este un element din lista înlănțuită care stochează date și o referință către următorul nod din secvență. Iată cum poți defini un nod în Python:

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

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

Codul de mai sus inițializează un nod efectuând două acțiuni principale: atributului „data” al nodului i se atribuie o valoare care reprezintă informația efectivă pe care nodul trebuie să o conțină. Atributul „next” reprezintă adresa următorului nod. Acesta este setat momentan la None, semnificând că nu este legat de niciun alt nod din listă. Pe măsură ce continuăm să adăugăm noduri noi în lista înlănțuită, acest atribut va fi actualizat pentru a indica nodul următor.

Crearea unei clase pentru lista înlănțuită

În continuare, trebuie să creăm clasa listei înlănțuite. Aceasta va îngloba toate operațiile pentru gestionarea nodurilor, precum inserarea și eliminarea. Vom începe prin a inițializa lista înlănțuită:

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

Setând self.head la None, afirmăm că lista înlănțuită este inițial goală și că nu există noduri la care să se facă referire. Vom continua acum să populăm lista prin inserarea de noduri noi.

Inserarea unui nod nou la începutul unei liste înlănțuite

În cadrul clasei LinkedList, vom adăuga o metodă pentru a crea un nod nou și a-l plasa la începutul listei:

    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

De fiecare dată când apelezi metoda de mai sus, se creează un nod nou cu datele specificate de tine. Pointerul next al acestui nod nou este setat la capul curent al listei, ceea ce va plasa acest nod în fața celor existente. În final, nodul proaspăt creat devine capul listei.

Acum vom popula această listă înlănțuită cu o serie de cuvinte pentru a înțelege mai bine cum funcționează operația de inserare. Pentru a face asta, hai să creăm mai întâi o metodă concepută să parcurgă și să afișeze conținutul listei:

    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

Metoda de mai sus va afișa conținutul listei noastre înlănțuite. Să folosim acum metodele definite pentru a popula lista cu o serie de cuvinte: „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()

Liniile de cod de mai sus ar trebui să producă următoarea ieșire:

"the quick brown fox"

Inserarea unui nod nou la sfârșitul unei liste înlănțuite

Vom crea acum o metodă numită insertAtEnd în cadrul clasei LinkedList, pentru a crea un nod nou la sfârșitul listei. Dacă lista este goală, nodul nou va deveni capul listei. În caz contrar, va fi adăugat la nodul care este în prezent ultimul din listă. Să vedem cum funcționează în practică:

    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

Metoda de mai sus începe prin a crea un nod nou. Apoi verifică dacă lista este goală și, dacă da, nodul nou este atribuit drept cap al listei. Altfel, parcurge lista pentru a găsi ultimul nod și setează pointerul acestuia către nodul nou.

Acum trebuie să includem această metodă în clasa LinkedList și să o folosim pentru a adăuga un cuvânt la sfârșitul listei. Pentru a face asta, modifică funcția principală astfel:

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

Observă că am apelat pur și simplu metoda insertAtEnd pentru a afișa cuvântul „jumps” la sfârșitul listei. Codul de mai sus ar trebui să producă următoarea ieșire:

"the quick brown fox jumps"

Ștergerea unui nod de la începutul unei liste înlănțuite

Ștergerea primului nod al unei liste înlănțuite este ușoară, deoarece implică doar indicarea capului listei către al doilea nod. În acest fel, primul nod nu va mai face parte din listă. Pentru a face asta, include următoarea metodă în clasa LinkedList:

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

Ștergerea unui nod de la sfârșitul unei liste înlănțuite

Pentru a șterge ultimul nod al unei liste înlănțuite, trebuie să parcurgem lista pentru a găsi penultimul nod și să-i schimbăm pointerul next la None. Astfel, ultimul nod nu va mai face parte din listă. Copiază și lipește următoarea metodă în clasa ta LinkedList pentru a face acest lucru:

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

Metoda de mai sus verifică mai întâi dacă lista înlănțuită este goală, returnând un mesaj utilizatorului dacă este. În caz contrar, dacă lista conține un singur nod, acel nod este eliminat. Pentru liste cu mai multe noduri, metoda identifică penultimul nod, iar referința către următorul nod este actualizată la None.

Să actualizăm acum funcția principală pentru a șterge elemente de la începutul și sfârșitul listei înlănțuite:

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

Codul de mai sus va afișa lista înainte și după ștergere, evidențiind modul în care funcționează operațiile de inserare și ștergere în listele înlănțuite. Ar trebui să vezi următoarea ieșire după rularea acestui cod:

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

Căutarea unei valori specifice în lista înlănțuită

Ultima operație pe care o vom învăța în acest capitol este regăsirea unei valori specifice în lista înlănțuită. Pentru a face asta, metoda ar trebui să pornească de la capul listei și să itereze prin fiecare nod, verificând dacă datele nodului se potrivesc cu valoarea căutată. Iată o implementare practică a acestei operații:

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" 

Pentru a găsi valori specifice în lista înlănțuită pe care am creat-o, actualizează funcția principală pentru a include metoda de căutare pe care tocmai am creat-o:

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

Codul de mai sus va produce următoarea ieșire:

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

Cuvântul „quick” a fost localizat cu succes în lista înlănțuită, deoarece există pe prima poziție a listei. Totuși, cuvântul „lazy” nu face parte din listă, motiv pentru care nu a fost găsit.

Gânduri finale

Dacă ai ajuns până aici, felicitări! Acum ai o înțelegere solidă a principiilor de bază ale listelor înlănțuite, inclusiv structura lor, tipurile, cum să adaugi și să elimini elemente și cum să le parcurgi.

Dar călătoria nu se oprește aici. Listele înlănțuite sunt doar începutul lumii structurilor de date și algoritmilor. Iată câțiva pași următori posibili pentru a-ți aprofunda înțelegerea subiectului:

Creează-ți propriul proiect

Intră în aplicațiile practice ale listelor înlănțuite integrându-le într-un proiect de programare sau de știința datelor. Listele înlănțuite sunt folosite pentru a dezvolta sisteme de fișiere, a construi tabele de dispersie și chiar pentru a crea sisteme de navigație GPS și jocuri de societate. Pentru a începe propriile proiecte, consultă proiectele noastre gratuite, ghidate de știința datelor care te învață cum să rezolvi probleme reale în Python, R și SQL.

Învață despre structuri de date și algoritmi

Învățarea altor structuri de date, precum arbori, stive și cozi, este o progresie firească după înțelegerea listelor înlănțuite. Aceste structuri se bazează pe principiile listelor înlănțuite, ajutându-te să rezolvi eficient o gamă mai largă de probleme computaționale. Arborii și arborii binari de căutare, de exemplu, extind conceptul listelor înlănțuite într-o formă ierarhică, permițând fiecărui nod să se conecteze la mai multe elemente din structură.

Dacă aceste concepte ți se par nefamiliare, nu-ți face griji! Datacamp are un curs întreg despre structuri de date și algoritmi în Python care te va ghida prin aceste concepte în detaliu. Vei învăța mai întâi despre structuri de date precum stive, arbori, tabele de dispersie, cozi și grafuri. Pe măsură ce avansezi în curs, vei înțelege algoritmi de căutare și sortare, care te vor ajuta să devii un programator și un rezolvator de probleme mai eficient.

Explorarea conceptelor avansate despre liste înlănțuite

Am implementat liste simplu înlănțuite în acest tutorial, acoperind operații precum inserarea, ștergerea și parcurgerea.

Poți duce aceste cunoștințe mai departe învățând implementarea listelor dublu și a celor circulare. Skip list-urile sunt o altă extensie a listelor înlănțuite care permit operații de căutare mai rapide, facilitând accesul mai rapid la elemente.

Învățarea acestor structuri de date avansate îți va duce abilitățile tehnice la următorul nivel și îți va îmbunătăți considerabil capacitățile de programare, pregătindu-te pentru provocări mai complexe în domenii precum știința datelor, dezvoltarea software și machine learning.

Dacă îți dorești o introducere mai prietenoasă pentru începători în programare înainte de a aborda aceste subiecte avansate, explorează traseul nostru de carieră Python Programmer. Oferă o serie de cursuri care te vor învăța elementele de bază ale limbajului.