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 din memorie, ceea ce permite o gestionare eficientă a memoriei. Fiecare nod dintr-o listă înlănțuită include două componente principale: partea de date și o referință la următorul nod din secvență.

Dacă acest concept pare complicat la prima vedere, nu te speria!

Îl vom descompune până la elementele de bază pentru a explica ce sunt listele înlănțuite, de ce le folosim și avantajele unice pe care le oferă.

De ce liste înlănțuite?

Listele înlănțuite au fost create pentru a depăși diversele dezavantaje asociate cu stocarea datelor în liste și tablouri obișnuite, după cum urmează:

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

În liste, inserarea sau ștergerea unui element într-o poziție diferită de final 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 deja familiar cu modul în care funcționează listele sau implementarea lor, poți citi tutorialul nostru despre liste în Python.

Listele înlănțuite, însă, funcționează diferit. Ele stochează elementele în locații de memorie variate, neadiacente, ș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 nou element sau a ocoli elementul ș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 o parcurgere O(n), așa că beneficiul O(1) se aplică doar atunci când deții deja un pointer către nodul relevant (de exemplu, când lucrezi la începutul listei).

Dimensiune dinamică

Listele din Python sunt tablouri dinamice, ceea ce înseamnă că oferă flexibilitate în modificarea dimensiunii.

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 nevoie de realocare sau redimensionare. Acest lucru le face o opțiune preferabilă pentru sarcini care cer multă flexibilitate.

Eficiență a 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 contigu de memorie mai mare și apoi să copieze toate elementele existente în acest bloc. 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 neutilizată este irosită.

În schimb, 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 trebuie stocați pointeri pentru fiecare element pentru a referi următorul nod, utilizarea memoriei per element este mai mare în cazul listelor î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 într-o complexitate 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:

• Ai nevoie să inserezi și să ștergi frecvent multe elemente
• Dimensiunea datelor este imprevizibilă sau probabil să se schimbe des
• 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 unice 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ță la 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 propriu-zisă stocată în nod.
• Pointerul Next: O referință la 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 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 O(1). Totuși, inserarea și ștergerea la mijloc sau la final necesită parcurgerea listei până la acel punct, ceea ce duce la o complexitate O(n).

Designul listelor simplu înlănțuite le face o structură de date utilă când efectuezi 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ă capacitatea de a efectua operații care necesită navigare bidirecțională.

Listele dublu înlănțuite rezolvă această problemă prin includerea unui pointer suplimentar în fiecare nod, asigurând că lista poate fi parcursă î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 care trebuie parcurse continuu, cum ar fi jocurile de societate care revin de la ultimul jucător la primul sau în algoritmi de calcul precum planificarea round-robin.

Sumar al complexității de timp

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

Ideea principală: listele înlănțuite câștigă la inserări și ștergeri la început (O(1)), dar pierd la aproape tot restul. Dacă nu adaugi sau elimini des 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. Caietul 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

Așa cum am învățat anterior, un nod este un element din lista înlănțuită care stochează date și o referință la 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 propriu-zisă pe care nodul o conține. Atributul „next” reprezintă adresa următorului nod. Acesta este setat momentan la None, semnificând că nu leagă niciun alt nod din listă. Pe măsură ce adăugăm noduri noi în lista înlănțuită, acest atribut va fi actualizat pentru a indica spre nodul următor.

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

În continuare, trebuie să creăm clasa listei înlănțuite. Aceasta va încorpora toate operațiile pentru gestionarea nodurilor, cum ar fi inserarea și eliminarea. Vom începe prin inițializarea listei înlănțuite:

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

Setând self.head la None, declarăm că lista înlănțuită este inițial goală și că nu există noduri în listă către care să se pointeze. 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, este creat 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 cele din urmă, nodul nou 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 realiza acest lucru, hai să creăm mai întâi o metodă concepută pentru a parcurge și a afișa 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 clasa LinkedList, pentru a crea un nod nou la finalul listei. Dacă lista este goală, noul nod 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ă, iar dacă da, noul nod este atribuit drept cap al listei. În caz contrar, parcurge lista pentru a găsi ultimul nod și setează pointerul acestuia către nodul nou.

Acum trebuie să incluzi această metodă în clasa LinkedList și să o folosești pentru a adăuga un cuvânt la finalul listei. Pentru a face acest lucru, modifică funcția main 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ă pur și simplu am apelat metoda insertAtEnd pentru a afișa cuvântul „jumps” la finalul 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. Astfel, primul nod nu va mai face parte din listă. Pentru a realiza acest lucru, 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ă schimbăm pointerul next al acestuia 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 realiza 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ă, întorcând un mesaj utilizatorului dacă este. În caz contrar, dacă lista conține un singur nod, acel nod este eliminat. Pentru listele cu mai multe noduri, metoda localizează penultimul nod, iar referința către următorul nod este actualizată la None.

Să actualizăm acum funcția main pentru a șterge elemente de la începutul și de la 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, demonstrând cum 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 realiza acest lucru, 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 main 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 găsit cu succes în lista înlănțuită, deoarece există pe prima poziție a listei. Însă 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 a 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 de data science gratuite, ghidate, care te învață cum să rezolvi probleme din lumea reală î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 continuare firească a înțelegerii 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 pildă, extind conceptul listelor înlănțuite într-o formă ierarhică, permițând fiecărui nod să se conecteze la mai multe elemente din structura de date.

Dacă aceste concepte îți sună necunoscut, nu te speria! Datacamp are un curs întreg despre structuri de date și algoritmi în Python, care te va conduce prin aceste concepte în detaliu. Mai întâi vei învăța despre structuri de date precum stive, arbori, tabele de dispersie, cozi și grafuri. Pe măsură ce avansezi în curs, vei dobândi o înțelegere a algoritmilor de căutare și sortare, care te vor ajuta să devii un programator și un rezolvator de probleme mai eficient.

Explorarea conceptelor avansate de 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 această cunoaștere mai departe învățând implementarea listelor dublu și circulare. Skip list-urile sunt o altă extensie a listelor înlănțuite care permit căutări mai rapide prin facilitarea unui acces mai rapid la elemente.

Învățarea acestor structuri de date avansate îți va duce abilitățile tehnice la nivelul următor și îți va îmbunătăți considerabil capabilitățile de programare, pregătindu-te pentru provocări mai complexe în domenii precum data science, dezvoltare software și inginerie de 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 abilități Python Programming. Oferă o serie de cursuri care te vor învăța fundamentele limbajului.