Liste legate în Python - Plato AiStream V2.1

Republicat de Platon

Urmaritori: 0

Introducere

O listă legată este o structură de date constând dintr-o secvență de noduri, fiecare conținând o valoare și o referință la următorul nod din secvență. Spre deosebire de matrice, listele legate nu necesită alocarea de memorie contigue, ceea ce le face mai flexibile și mai eficiente pentru anumite operațiuni. În acest articol, vom explora avantajele și dezavantajele listelor conectate și cum să le implementăm în Python.

Cuprins

Avantajele și dezavantajele listelor conectate

Listele legate oferă mai multe avantaje față de alte structuri de date. În primul rând, permit inserarea și ștergerea eficientă a elementelor, deoarece necesită doar actualizarea referințelor nodurilor învecinate. Acest lucru face ca LinkedLists să fie ideal pentru scenariile în care sunt așteptate modificări frecvente. În plus, LinkedLists pot crește sau micșora în mod dinamic dimensiunea, spre deosebire de matricele, care au o dimensiune fixă.

Cu toate acestea, listele conectate au și unele dezavantaje. Spre deosebire de matrice, Listele legate nu acceptă accesul aleatoriu la elemente, ceea ce înseamnă că accesarea unui element la un anumit index necesită parcurgerea listei de la început. Acest lucru poate duce la o performanță mai lentă pentru anumite operațiuni. Mai mult, listele legate necesită memorie suplimentară pentru a stoca referințele la nodurile următoare, ceea ce poate fi ineficient pentru seturile de date mici.

Implementarea listelor legate în Python

Python oferă o modalitate flexibilă și intuitivă de implementare a listelor conectate. Există trei tipuri principale de liste conectate: Listă legată individual, Listă dublu legată și Listă circulară legată. Să le explorăm în detaliu pe fiecare dintre ele.

Lista legată individual

O listă legată individual constă din noduri în care fiecare nod conține o valoare și o referință la următorul nod din secvență. Iată cum puteți crea o listă legată individual în Python:

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

class Linked List:
    def __init__(self):
        self.head = None

Crearea unei liste conectate individual

Pentru a crea o listă legată individual, trebuie să definim o clasă Node care reprezintă fiecare nod din listă. Fiecare nod conține o valoare și o referință la următorul nod. Clasa Linked List servește ca container pentru noduri, cu atributul head indicând primul nod din listă.

Inserarea nodurilor într-o listă legată individual

Inserarea nodurilor într-o listă legată individual implică actualizarea referințelor nodurilor învecinate. Iată un exemplu de inserare a unui nod la începutul listei:

def insert_at_beginning(self, value):
    new_node = Node(value)
    new_node.next = self.head
    self.head = new_node

Ștergerea nodurilor dintr-o listă legată individual

Ștergerea nodurilor dintr-o listă legată individual necesită actualizarea referințelor nodurilor învecinate. Iată un exemplu de ștergere a unui nod cu o anumită valoare:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                break
            current = current.next

Căutarea într-o listă legată individual

Căutarea unei anumite valori într-o listă legată individual implică parcurgerea listei până când valoarea este găsită sau se ajunge la sfârșitul listei. Iată un exemplu de căutare a unei valori:

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Inversarea unei liste conectate individual

Inversarea unei liste conectate individual necesită actualizarea referințelor fiecărui nod pentru a indica nodul anterior. Iată un exemplu de inversare a unei liste conectate individual:

def reverse(self):
    previous = None
    current = self.head
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    self.head = previous

Listă dublu legată

O listă dublu legată este similară cu o listă cu legătură individuală, dar fiecare nod conține o referință atât la nodul următor, cât și la nodul anterior din secvență. Acest lucru permite traversarea eficientă în ambele direcții. Iată cum puteți crea o listă dublu legată în Python:

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

class DoublyLinked List:
    def __init__(self):
        self.head = None

Crearea unei liste dublu legate

Pentru a crea o listă dublu legată, definim o clasă Node care conține o valoare, o referință la următorul nod și o referință la nodul anterior. Clasa DoubleLinked List servește ca container pentru noduri, cu atributul head indicând primul nod din listă.

Inserarea nodurilor într-o listă dublu legată

Inserarea nodurilor într-o listă dublu legată implică actualizarea referințelor nodurilor învecinate. Iată un exemplu de inserare a unui nod la începutul listei:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if self.head:
        self.head.previous = new_node
    new_node.next = self.head
    self.head = new_node

Ștergerea nodurilor dintr-o listă dublu legată

Ștergerea nodurilor dintr-o listă dublu legată necesită actualizarea referințelor nodurilor învecinate. Iată un exemplu de ștergere a unui nod cu o anumită valoare:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
        if self.head:
            self.head.previous = None
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                if current.next:
                    current.next.previous = current
                break
            current = current.next

Căutarea într-o listă dublu legată

Căutarea unei anumite valori într-o listă dublu legată implică parcurgerea listei în oricare direcție până când valoarea este găsită sau se ajunge la sfârșitul listei. Iată un exemplu de căutare a unei valori:

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Inversarea unei liste dublu legate

Inversarea unei liste dublu legate necesită actualizarea referințelor fiecărui nod pentru a schimba pointerii următor și anterior. Iată un exemplu de inversare a unei liste dublu legate:

def reverse(self):
    current = self.head
    while current:
        next_node = current.next
        current.next = current.previous
        current.previous = next_node
        if not next_node:
            self.head = current
        current = next_node

Listă circulară legată

O listă circulară legată este o variație a listei cu legături individuale în care ultimul nod indică înapoi la primul nod, creând o structură circulară. Acest lucru permite traversarea eficientă de la orice nod din listă. Iată cum puteți crea o listă circulară legată în Python:

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

class CircularLinked List:
    def __init__(self):
        self.head = None

Crearea unei liste circulare legate

Pentru a crea o listă circulară legată, definim o clasă Node care conține o valoare și o referință la următorul nod. Clasa CircularLinked List servește ca container pentru noduri, cu atributul head indicând primul nod din listă. În plus, următoarea referință a ultimului nod este setată la cap, creând o structură circulară.

Inserarea nodurilor într-o listă circulară legată

Inserarea nodurilor într-o listă circulară legată implică actualizarea referințelor nodurilor învecinate. Iată un exemplu de inserare a unui nod la începutul listei:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if not self.head:
        self.head = new_node
        new_node.next = self.head
    else:
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head
        self.head = new_node

Ștergerea nodurilor dintr-o listă circulară legată

Ștergerea nodurilor dintr-o listă circulară legată necesită actualizarea referințelor nodurilor învecinate. Iată un exemplu de ștergere a unui nod cu o anumită valoare:

def delete_node(self, value):
    if not self.head:
        return
    current = self.head
    if current.value == value:
        while current.next != self.head:
            current = current.next
        if current == self.head:
            self.head = None
        else:
            current.next = self.head.next
            self.head = self.head.next
    else:
        previous = None
        while current.next != self.head:
            previous = current
            current = current.next
            if current.value == value:
                previous.next = current.next
                break

Căutarea într-o listă circulară legată

Căutarea unei anumite valori într-o listă circulară legată implică parcurgerea listei până când se găsește valoarea sau se parcurge întreaga listă. Iată un exemplu de căutare a unei valori:

def search(self, value):
    if not self.head:
        return False
    current = self.head
    while True:
        if current.value == value:
            return True
        current = current.next
        if current == self.head:
            break
    return False

Inversarea unei liste circulare legate

Inversarea unei liste de legături circulare necesită actualizarea referințelor fiecărui nod pentru a inversa structura circulară. Iată un exemplu de inversare a unei liste circulare legate:

def reverse(self):
    if not self.head:
        return
    previous = None
    current = self.head
    next_node = current.next
    while True:
        current.next = previous
        previous = current
        current = next_node
        next_node = next_node.next
        if current == self.head:
            break
    self.head = previous

Operațiuni comune pe listele conectate

Listele conectate acceptă diverse operații comune care pot fi efectuate asupra elementelor. Să explorăm câteva dintre aceste operațiuni:

Accesarea elementelor dintr-o listă legată

Pentru a accesa elemente dintr-o Listă Linked, putem parcurge lista începând de la nodul principal și trecem la următorul nod până ajungem la poziția dorită. Iată un exemplu de accesare a unui element la un anumit index:

def get_element(self, index):
    current = self.head
    count = 0
    while current:
        if count == index:
            return current.value
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Modificarea elementelor dintr-o listă legată

Modificarea elementelor dintr-o listă legată implică parcurgerea listei pentru a găsi elementul dorit și actualizarea valorii acestuia. Iată un exemplu de modificare a unui element la un anumit index:

def modify_element(self, index, new_value):
    current = self.head
    count = 0
    while current:
        if count == index:
            current.value = new_value
            return
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Găsirea lungimii unei liste legate

Pentru a găsi lungimea unei liste legate, putem parcurge lista și numără numărul de noduri. Iată un exemplu de găsire a lungimii unei liste legate:

def get_length(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.next
    return count

Verificarea dacă o listă legată este goală

Pentru a verifica dacă o listă legată este goală, putem verifica pur și simplu dacă nodul principal este Nici unul. Iată un exemplu de verificare dacă o listă conectată este goală:

def is_empty(self):
    return self.head is None

Concatenarea listelor legate

Pentru a concatena două Liste Linked, putem parcurge prima listă pentru a găsi ultimul nod și a actualiza următoarea sa referință la capul celei de-a doua liste. Iată un exemplu de concatenare a două liste legate:

def concatenate(self, other_list):
    if not self.head:
        self.head = other_list.head
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = other_list.head

Linked List vs. Array

Listele legate și matricele sunt ambele structuri de date utilizate în mod obișnuit, dar au caracteristici diferite care le fac potrivite pentru diferite scenarii. Să comparăm listele și matricele legate în ceea ce privește eficiența memoriei, eficiența inserării și ștergerii și eficiența accesului aleatoriu.

Eficiența memoriei

Listele legate sunt mai eficiente din punct de vedere al memoriei decât matricele, deoarece nu necesită alocare a memoriei contigue. Fiecare nod dintr-o listă legată trebuie doar să stocheze valoarea și o referință la următorul nod, în timp ce tablourile trebuie să aloce memorie pentru toate elementele, chiar dacă nu sunt utilizate.

Eficiența inserării și ștergerii

Listele legate excelează în operațiunile de inserare și ștergere, mai ales când elementele sunt adăugate sau eliminate frecvent din mijlocul listei. Inserarea sau ștergerea unui element într-o listă legată necesită doar actualizarea referințelor nodurilor învecinate, în timp ce matricele pot necesita elemente de deplasare pentru a se adapta la modificare.

Eficiența accesului aleatoriu

Matricele oferă acces aleatoriu eficient la elemente pe baza indicilor acestora, deoarece permit adresarea directă a memoriei. În schimb, listele legate necesită parcurgerea listei de la început pentru a accesa un element la un index specific, ceea ce duce la o performanță mai lentă pentru operațiunile de acces aleatoriu.

Alegerea structurii corecte de date

Alegerea dintre listele legate și matrice depinde de cerințele specifice ale aplicației. Dacă sunt de așteptat modificări frecvente și redimensionare dinamică, Listele legate este o alegere mai bună. Pe de altă parte, dacă accesul aleator și eficiența memoriei sunt cruciale, matricele sunt mai potrivite.

Aplicații cu liste conectate

Acum că avem o bună înțelegere a listelor conectate și a modului în care funcționează acestea, haideți să explorăm câteva dintre aplicațiile practice în care listele legate pot fi utilizate eficient.

De asemenea, vă puteți înscrie în cadrul nostru Cursuri gratuite Astăzi!

Implementarea stivelor și cozilor

Una dintre cele mai comune aplicații ale listelor legate este implementarea stivelor și a cozilor. Atât stivele, cât și cozile sunt tipuri de date abstracte care pot fi implementate cu ușurință folosind liste legate.

O stivă este o structură de date care urmează principiul Last-In-First-Out (LIFO). Elementele sunt adăugate și îndepărtate de la același capăt, cunoscut sub numele de vârful stivei. Listele legate oferă o modalitate eficientă de implementare a stivelor, deoarece putem adăuga sau elimina cu ușurință elemente din capul listei.

Iată un exemplu de implementare a unei stive folosind o listă legată în Python:

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

class Stack:
    def __init__(self):
        self.head = None

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

    def pop(self):
        if self.head is None:
            return None
        popped = self.head.data
        self.head = self.head.next
        return popped

O coadă, pe de altă parte, urmează principiul First-In-First-Out (FIFO). Elementele sunt adăugate la un capăt, cunoscut sub numele de spate, și îndepărtate de la celălalt capăt, cunoscut sub numele de față. Listele legate pot fi, de asemenea, utilizate pentru a implementa cozile în mod eficient.

Iată un exemplu de implementare a unei cozi folosind o listă conectată în Python:

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

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return None
        dequeued = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return dequeued

Manipularea seturi mari de date

Listele legate sunt, de asemenea, utile atunci când aveți de-a face cu seturi mari de date. Spre deosebire de matrice, listele legate nu necesită alocarea de memorie contigue. Aceasta înseamnă că listele conectate pot gestiona eficient seturi de date de dimensiuni diferite, fără a fi nevoie de redimensionare sau realocare.

De exemplu, să presupunem că avem un set de date de milioane de înregistrări și trebuie să efectuăm operațiuni precum inserarea, ștergerea sau traversarea. Utilizarea unei matrice pentru această sarcină poate fi ineficientă, deoarece necesită deplasarea elementelor la inserare sau ștergere. Cu toate acestea, cu o listă legată, putem insera sau șterge cu ușurință elemente prin actualizarea pointerilor, rezultând operații mai rapide.

Algoritmi de traversare a graficelor

Algoritmii de traversare a graficelor, cum ar fi căutarea pe lățime (BFS) și căutarea pe adâncime (DFS), pot fi, de asemenea, implementați folosind liste legate. În traversarea graficului, vizităm fiecare vârf sau nod dintr-un grafic într-o anumită ordine.

Listele legate pot fi folosite pentru a reprezenta lista de adiacență a unui grafic, în care fiecare nod din lista legată reprezintă un vârf și vârfurile adiacente ale acestuia sunt stocate ca noduri de listă conectate. Această reprezentare permite parcurgerea și explorarea eficientă a graficului.

Reprezentarea polinomială

Listele legate pot fi folosite pentru a reprezenta eficient polinoamele. În matematică, polinoamele sunt expresii formate din variabile și coeficienți. Fiecare termen dintr-un polinom poate fi reprezentat ca un nod într-o listă legată, unde coeficientul și exponentul sunt stocate ca date.

Folosind liste legate, putem efectua cu ușurință operații pe polinoame, cum ar fi adunarea, scăderea și înmulțirea. Nodurile pot fi manipulate pentru a efectua aceste operații, rezultând o reprezentare concisă și eficientă a polinoamelor.

Liste de redare cu muzică și video

Listele conectate sunt utilizate în mod obișnuit pentru a implementa liste de redare în playerele muzicale și video. Fiecare melodie sau videoclip poate fi reprezentat ca un nod într-o listă legată, unde datele conțin informații despre fișierul media și indicatorul indică următorul cântec sau videoclip din lista de redare.

Folosirea listelor conectate pentru liste de redare permite navigarea ușoară între melodii sau videoclipuri. Putem adăuga sau elimina cu ușurință melodii din lista de redare prin actualizarea indicatorilor, oferind o experiență de utilizator fără întreruperi.

Concluzie

În concluzie, listele legate sunt structuri de date versatile care găsesc aplicații în diverse domenii. Acestea pot fi folosite pentru a implementa stive și cozi, pentru a gestiona seturi mari de date, pentru a efectua traversarea graficelor, pentru a reprezenta polinoame și pentru a crea liste de redare. Listele legate oferă soluții eficiente la aceste probleme prin valorificarea alocării dinamice a memoriei și manipularea ușoară a nodurilor.

Înțelegând aplicațiile listelor legate, putem lua decizii informate atunci când alegem structuri de date pentru programele noastre. Fie că este vorba despre gestionarea datelor, implementarea algoritmilor sau crearea de interfețe ușor de utilizat, listele conectate oferă un instrument valoros în setul de instrumente al programatorului.

Deci, data viitoare când întâmpinați o problemă care necesită inserare, ștergere sau parcurgere eficientă, luați în considerare utilizarea listelor conectate pentru a simplifica soluția și a optimiza codul.

De asemenea, puteți citi mai multe articole legate de Listele Python aici:

Întrebări Frecvente

Î1: Ce este o listă conectată?

R: O listă legată este o structură de date formată din noduri, în care fiecare nod conține o valoare și o referință (sau o legătură) la următorul nod din secvență.

Î2: Care sunt avantajele utilizării listelor conectate?

R: Listele legate oferă operații eficiente de inserare și ștergere, redimensionare dinamică și nu necesită alocarea de memorie contigue.

Î3: Care sunt dezavantajele listelor conectate?

R: Listele legate nu au acces aleator, necesitând parcurgere pentru accesul la elemente. De asemenea, consumă memorie suplimentară pentru stocarea referințelor, ceea ce poate fi ineficient pentru seturile de date mici.

Î4: Care sunt principalele tipuri de liste legate în Python?

R: Principalele tipuri de liste conectate sunt Lista legată individual, Lista legată dublu și Lista legată circulară.

Î5: În ce scenarii listele legate sunt mai eficiente din punct de vedere al memoriei decât matricele?

R: Listele legate sunt mai eficiente din punct de vedere al memoriei decât matricele atunci când se ocupă de redimensionarea dinamică și de inserări sau ștergeri frecvente, deoarece nu necesită alocarea de memorie contigue.