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
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ță.
R: Listele legate oferă operații eficiente de inserare și ștergere, redimensionare dinamică și nu necesită alocarea de memorie contigue.
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.
R: Principalele tipuri de liste conectate sunt Lista legată individual, Lista legată dublu și Lista legată circulară.
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.
Legate de
- Distribuție de conținut bazat pe SEO și PR. Amplifică-te astăzi.
- PlatoData.Network Vertical Generative Ai. Împuterniciți-vă. Accesați Aici.
- PlatoAiStream. Web3 Intelligence. Cunoștințe amplificate. Accesați Aici.
- PlatoESG. carbon, CleanTech, Energie, Mediu inconjurator, Solar, Managementul deșeurilor. Accesați Aici.
- PlatoHealth. Biotehnologie și Inteligență pentru studii clinice. Accesați Aici.
- Sursa: https://www.analyticsvidhya.com/blog/2024/02/linked-lists-in-python/
- :este
- :nu
- :Unde
- 1
- 10
- 16
- 48
- 5
- 9
- a
- Despre Noi
- REZUMAT
- acces
- accesarea
- găzdui
- adăuga
- adăugat
- plus
- În plus,
- adresare
- adiacent
- Avantajele
- algoritmi
- TOATE
- aloca
- alocare
- permite
- permite
- de asemenea
- an
- și
- Orice
- aplicație
- aplicatii
- SUNT
- Mulțime
- articol
- bunuri
- AS
- At
- înapoi
- bazat
- BE
- deoarece
- Început
- Mai bine
- între
- atât
- Pauză
- dar
- by
- CAN
- sigur
- Schimbare
- Caracteristici
- verifica
- control
- alegere
- alegere
- circulară
- clasă
- cod
- coeficienţii
- Comun
- în mod obișnuit
- comparaţie
- concis
- concluzie
- Lua în considerare
- Constând
- constă
- consuma
- Recipient
- conține
- contrast
- conta
- crea
- Crearea
- crucial
- Curent
- de date
- seturi de date
- abuzive
- Deciziile
- Def
- defini
- șterge
- depinde de
- dorit
- detaliu
- diferit
- direcționa
- direcţie
- traseu
- do
- domenii
- de două ori
- dinamic
- dinamic
- fiecare
- cu ușurință
- uşor
- în mod eficient
- eficiență
- eficient
- eficient
- oricare
- element
- element
- altfel
- gol
- întâlni
- capăt
- înscrie
- Întreg
- mai ales
- Eter (ETH)
- Chiar
- exemplu
- Excel
- de aşteptat
- experienţă
- explorare
- explora
- exponent
- expresii
- suplimentar
- fals
- mai repede
- Fișier
- Găsi
- descoperire
- First
- fixată
- flexibil
- urmează
- Pentru
- găsit
- frecvent
- frecvent
- din
- faţă
- În plus
- bine
- grafic
- Crește
- mână
- manipula
- Avea
- cap
- aici
- Înalt
- Cum
- Cum Pentru a
- Totuși
- HTTPS
- ideal
- if
- punerea în aplicare a
- implementat
- Punere în aplicare a
- in
- index
- Indici
- ineficace
- informații
- informat
- interfeţe
- intuitiv
- implică
- IT
- ESTE
- cunoscut
- lipsă
- mare
- Nume
- Lungime
- efectului de pârghie
- LINK
- legate de
- Listă
- liste
- Principal
- face
- FACE
- Efectuarea
- de conducere
- manipulat
- Manipulare
- matematică
- max-width
- Mai..
- sens
- mijloace
- Mass-media
- Memorie
- De mijloc
- milioane
- modificările aduse
- mai mult
- cele mai multe
- muta
- multiplicare
- Muzică
- Navigare
- Nevoie
- nevoilor
- vecin
- următor
- nod
- noduri
- Nici unul
- număr
- of
- oferi
- on
- ONE
- afară
- Operațiuni
- Optimizați
- or
- comandă
- Altele
- al nostru
- afară
- peste
- efectua
- performanță
- efectuată
- Plato
- Informații despre date Platon
- PlatoData
- jucători
- Punct
- puncte
- polinom
- polinomiale
- poziţie
- Practic
- Aplicații practice
- precedent
- principiu
- Problemă
- probleme
- Programe
- furniza
- furnizează
- furnizarea
- Piton
- ridica
- aleator
- gamă
- ajunge
- atins
- Citeste
- înregistrări
- referință
- referințe
- legate de
- scoate
- îndepărtat
- reprezenta
- reprezentare
- reprezentate
- reprezintă
- necesita
- Cerinţe
- Necesită
- rezultat
- rezultând
- reveni
- inversa
- dreapta
- acelaşi
- Spune
- scenarii
- fără sudură
- Caută
- căutare
- Al doilea
- SELF
- Secvenţă
- servește
- set
- câteva
- SCHIMBARE
- asemănător
- simplifica
- pur şi simplu
- Mărimea
- dimensiuni
- mic
- soluţie
- soluţii
- unele
- cântec
- specific
- stivui
- Stive
- Pornire
- stoca
- stocate
- structura
- structurile
- scădere
- astfel de
- potrivit
- a sustine
- SVG
- schimba
- Sarcină
- durată
- termeni
- decât
- acea
- Graficul
- lor
- Lor
- Acolo.
- Acestea
- ei
- acest
- trei
- timp
- la
- instrument
- Toolkit
- top
- traversa
- adevărat
- Două
- tip
- Tipuri
- înţelegere
- spre deosebire de
- până la
- Actualizează
- actualizarea
- utilizat
- util
- Utilizator
- Experiența de utilizare
- ușor de utilizat
- folosind
- Valoros
- valoare
- variabile
- diverse
- variabil
- multilateral
- Video
- Video
- Vizita
- vs
- Cale..
- we
- Ce
- Ce este
- cand
- întrucât
- dacă
- care
- în timp ce
- voi
- cu
- fără
- Apartamente
- tu
- Ta
- zephyrnet