Diferența dintre lista individuală și lista dublă asociată

Listă cu o singură legătură față de o listă dublată

Lista legată este o structură de date liniară care este utilizată pentru a stoca o colecție de date. O listă legată alocă memoria elementelor sale separat în propriul bloc de memorie și structura globală este obținută prin legarea acestor elemente ca legături într-un lanț. O singură listă legată este alcătuită dintr-o secvență de noduri și fiecare nod are o referință la nodul următor din secvență. O listă dublu legată conține o secvență de noduri în care fiecare nod conține o referință la nodul următor, precum și la nodul anterior.

Fiecare element dintr-o singură listă legată are două câmpuri, după cum se arată în figura 1. Câmpul de date păstrează datele reale stocate, iar câmpul următor reține referința la elementul următor în lanț. Primul element al listei legate este stocat ca capul listei legate.

Figura 2 descrie o listă legată individual cu trei elemente. Fiecare element își stochează datele și toate elementele, cu excepția ultimului, stochează o referință la elementul următor. Ultimul element deține o valoare nulă în câmpul următor. Orice element din listă poate fi accesat pornind de la cap și urmând pointerul următor până când veți găsi elementul necesar.

Fiecare element dintr-o listă dublu legată are trei câmpuri, după cum se arată în Figura 3. Similar cu lista cu legături singulare, câmpul de date păstrează datele reale stocate, iar câmpul următor reține referința la elementul următor în lanț. În plus, câmpul anterior conține referința la elementul anterior din lanț. Primul element al listei legate este stocat ca capul listei legate.

Figura 4 prezintă o listă dublă legată cu trei elemente. Toate elementele intermediare stochează referințe la primul și la elementele anterioare. Ultimul element din listă deține o valoare nulă în câmpul următor și primul element din listă deține o valoare nulă în câmpul său anterior. Două listă legată poate fi traversată înainte urmând următoarele referințe în fiecare element și în mod similar poate fi traversată înapoi utilizând referințele anterioare din fiecare element.

Care este diferența dintre lista singulară și lista dublată?

Fiecare element din lista legată singular conține o referință la elementul următor din listă, în timp ce fiecare element din lista dublu legată conține referințe la elementul următor, precum și la elementul anterior din listă. Două liste legate necesită mai mult spațiu pentru fiecare element din listă, iar operațiile elementare, cum ar fi inserarea și ștergerea, sunt mai complexe, deoarece trebuie să se ocupe de două referințe. Dar, listele de linkuri duble permit o manipulare mai ușoară, deoarece permite traversarea listei în direcții înainte și înapoi.