Lista legată este o structură de date liniară, în care elementele nu sunt stocate într-o locație adiacentă, ci mai degrabă sunt legate folosind pointeri. Linked List formează o serie de noduri conectate, unde fiecare nod stochează datele și adresa următorului nod.

Structura nodului: Un nod dintr-o listă legată constă de obicei din două componente:
Date: Acesta deține valoarea reală sau datele asociate nodului.
Următorul indicator: Stochează adresa de memorie (referința) următorului nod din secvență.
Cap și coadă: Lista legată este accesată prin nodul principal, care indică primul nod din listă. Ultimul nod din listă indică NULL sau nullptr, indicând sfârșitul listei. Acest nod este cunoscut sub numele de nodul de coadă.

De ce este necesară o structură de date a listelor legate?

Iată câteva avantaje ale unei liste linkate care este enumerată mai jos, vă va ajuta să înțelegeți de ce este necesar să știți.

• Structura dinamică a datelor: Dimensiunea memoriei poate fi alocată sau de-alocată în timpul rulării pe baza operației de inserare sau ștergere.
• Ușurință de inserare/ștergere: Inserarea și ștergerea elementelor sunt mai simple decât matricele, deoarece niciun element nu trebuie să fie mutat după inserare și ștergere, doar adresa trebuia actualizată.
• Utilizare eficientă a memoriei: După cum știm, Linked List este o structură de date dinamică, dimensiunea crește sau scade conform cerințelor, astfel încât aceasta evită risipa de memorie.
• Implementare: Pot fi implementate diferite structuri avansate de date folosind o listă legată, cum ar fi o stivă, o coadă, un grafic, hărți hash etc.

Exemplu:

Într-un sistem, dacă menținem o listă sortată de ID-uri într-o matrice id[] = [1000, 1010, 1050, 2000, 2040].

Dacă vrem să introducem un nou ID 1005, atunci pentru a menține ordinea sortată, trebuie să mutăm toate elementele după 1000 (exclusiv 1000).

Ștergerea este, de asemenea, costisitoare cu matrice până când nu sunt folosite unele tehnici speciale. De exemplu, pentru a șterge 1010 din id[], totul după 1010 trebuie mutat din cauza faptului că se face atât de multă muncă care afectează eficiența codului.

Tipuri de liste legate :

Există în principal trei tipuri de liste legate:

1. Listă cu o singură legătură
2. Listă dublu legată
3. Listă circulară legată

1. Listă cu o singură legătură :

Într-o listă legată individual, fiecare nod conține o referință la următorul nod din secvență. Parcurgerea unei liste conectate individual se face în direcția înainte.

Listă cu o singură legătură

2. Listă dublu legată :

Într-o listă dublu legată, fiecare nod conține referințe atât la nodul următor, cât și la cel anterior. Acest lucru permite traversarea în ambele direcții înainte și înapoi, dar necesită memorie suplimentară pentru referința înapoi.

Listă dublu legată

3. Listă circulară legată :

Într-o listă circulară legată, ultimul nod indică înapoi către nodul principal, creând o structură circulară. Poate fi legată fie individual, fie dublu.

cum functioneaza un calculator

Listă circulară legată

Operațiuni pe liste legate

1. Inserare : Adăugarea unui nou nod la o listă legată implică ajustarea pointerilor nodurilor existente pentru a menține secvența corespunzătoare. Inserarea poate fi efectuată la început, la sfârșit sau în orice poziție din listă
2. Ștergere : Eliminarea unui nod dintr-o listă legată necesită ajustarea pointerilor nodurilor vecine pentru a acoperi golul lăsat de nodul șters. Ștergerea poate fi efectuată la început, la sfârșit sau în orice poziție din listă.
3. In cautarea : Căutarea unei anumite valori într-o listă legată implică parcurgerea listei de la nodul principal până când valoarea este găsită sau se ajunge la sfârșitul listei.

Analiza complexității listei legate :

• Complexitatea timpului: O(n)
• Spațiu auxiliar: O(n)

Avantajele listelor conectate

• Dimensiune dinamică: Listele legate pot crește sau micșora dinamic, deoarece alocarea memoriei se face în timpul execuției.
• Inserare și ștergere: Adăugarea sau eliminarea elementelor dintr-o listă legată este eficientă, mai ales pentru listele mari.
• Flexibilitate: Listele legate pot fi reorganizate și modificate cu ușurință fără a necesita un bloc de memorie contiguu.

Dezavantajele listelor conectate

• Acces aleatoriu: Spre deosebire de matrice, listele legate nu permit accesul direct la elemente prin index. Traversarea este necesară pentru a ajunge la un anumit nod.
• Memorie suplimentară: Listele legate necesită memorie suplimentară pentru stocarea pointerilor, în comparație cu matricele.

Concluzie:

Listele legate sunt structuri de date versatile care asigură alocarea dinamică a memoriei și operațiuni eficiente de inserare și ștergere. Înțelegerea elementelor de bază ale listelor legate este esențială pentru orice programator sau pasionat de informatică. Cu aceste cunoștințe, puteți implementa liste legate pentru a rezolva diverse probleme și pentru a vă extinde înțelegerea structurilor de date și a algoritmilor.