Lista legată

O listă legată  este o structură de date dinamică de bază în informatică, constând din noduri care conțin date și legături („linkuri”) către nodul următor și/sau anterior al listei. [1] Avantajul fundamental față de o matrice este flexibilitatea structurală: ordinea elementelor unei liste legate poate să nu coincidă cu ordinea elementelor de date din memoria computerului [2] , iar ordinea de parcurgere a listei este întotdeauna stabilite în mod explicit de legăturile sale interne.

Tipuri de liste legate

Listă liniară legată

Singly linked list (singly linked list)

O listă liniară orientată individual este o structură de date constând din elemente de același tip, legate secvenţial prin pointeri. Fiecare element al listei are un pointer către următorul element. Ultimul element al listei indică NULL . Elementul spre care nu este indicat este primul element (cap) al listei. Aici, legătura de la fiecare nod indică către următorul nod din listă. Într-o listă conectată individual, vă puteți deplasa numai spre sfârșitul listei. Este imposibil să aflați adresa elementului anterior pe baza conținutului nodului curent.

În informatică , o listă liniară este de obicei definită ca un tip de date abstracte (ADT) care formalizează noțiunea de colecție ordonată de date . În practică, listele liniare sunt de obicei implementate folosind matrice și liste legate. Uneori, termenul „listă” este folosit și informal ca sinonim pentru „listă legată”. De exemplu, o listă mutabilă netipificată ADT poate fi definită ca un set de constructor și operații de bază:

  • O operație care verifică dacă o listă este goală.
  • Trei operații de adăugare a unui obiect în listă (la început, la sfârșit sau în interior după orice (n-al-lea) element al listei);
  • O operație care evaluează primul element (cap) al unei liste;
  • O operațiune de accesare a unei liste constând din toate elementele listei originale, cu excepția primei.
Caracteristici
  • Lungimea listei . Numărul de elemente din listă.
  • Listele pot fi tastate sau netipizate . Dacă o listă este introdusă, atunci este dat tipul elementelor sale și toate elementele sale trebuie să fie de tipuri care sunt compatibile cu tipul dat de elemente de listă. Majoritatea listelor sunt tastate.
  • Lista poate fi sortată sau nesortată .
  • În funcție de implementare, poate fi posibil accesul aleatoriu la elementele listei.
Lista legată individual în limbaje de programare

Xi

lista de structuri { câmp int ; // lista de structuri câmp de date * următorul ; // pointer la următorul element };

folosind o listă legată individual:

struct list * l1 = ( struct list * ) malloc ( sizeof ( struct list )); l1 -> câmp = 1 ; l1 -> next = ( struct list * ) malloc ( sizeof ( struct list )); l1 -> următorul -> câmp = 2 ; l1 -> next -> next = ( struct list * ) malloc ( sizeof ( struct list )); /* etc. */ Listă dublu legată (listă dublu legată)

Aici, legăturile din fiecare nod indică către nodul anterior și următorul din listă. La fel ca o listă legată unic, o listă dublu legată permite doar accesul secvenţial la elemente, dar permite şi mişcarea în ambele direcţii. În această listă, este mai ușor să ștergeți și să rearanjați elemente, deoarece adresele acelor elemente ale listei ai căror pointeri sunt direcționați către elementul care este schimbat sunt ușor accesibile.

Lista legată XOR

Folosit rar.

Listă circulară legată

Un fel de listă legată este o listă inelară (ciclică, închisă). Poate fi, de asemenea, cu o singură legătură sau cu două legături. Ultimul element al unei liste circulare conține un indicator către primul, iar primul (în cazul unei liste dublu legate) la ultima.

De regulă, o astfel de structură este implementată pe baza unei liste liniare. Fiecare listă circulară stochează suplimentar un pointer către primul element. Nu există nicio referire la NULL în această listă.

Există, de asemenea, liste circulare cu un element cap dedicat pentru a facilita parcurgerea întregii liste.

Omite lista

Listă cu linkuri extinsă

Beneficii

  • eficient (în timp constant) adăugarea și îndepărtarea elementelor
  • dimensiunea este limitată doar de cantitatea de memorie a computerului și de adâncimea de biți a pointerilor
  • adăugarea și îndepărtarea dinamică a elementelor

Dezavantaje

Dezavantajele listelor legate provin din proprietatea lor principală - accesul secvenţial la date:

  • complexitatea accesului direct la element, și anume, determinarea adresei fizice prin indexul acesteia (numărul de serie) din listă
  • câmpurile de indicatori (indicatorii către elementul următor și anterior) consumă memorie suplimentară (în matrice , de exemplu, pointerii nu sunt necesari)
  • unele operații cu liste sunt mai lente decât cu matrice, deoarece un element arbitrar al listei poate fi accesat doar parcurgând toate elementele care îl preced
  • elementele listei învecinate pot fi alocate non-local în memorie, ceea ce va reduce eficiența stocării în cache a datelor în procesor
  • în comparație cu tablourile, este mult mai dificil (deși posibil) să se efectueze operații vectoriale paralele pe liste legate, cum ar fi calcularea sumei: supraîncărcarea iterației peste elemente reduce eficiența paralelizării

Vezi și

Note

  1. ↑ Cormen, Leiserson, Rivest și Stein. Introducere în algoritmi, ediția a II-a. The MIT Press, 2001. ISBN 0-262-03293-7
  2. ↑ Alinierea datelor
 Structuri de date
Liste
Copaci
Contează
Alte