Listă dublu legată, algoritmi și programare

Listă dublu legată, algoritmi și programare

Figura 1 O listă dublu legată în formă grafică.

Să luăm în considerare câteva funcții standard pentru o listă dublu conectată. Funcția push adaugă un nou element poziției i a listei. Funcția efectuează următoarele acțiuni:
1) creează un element nou;
2) copiați valoarea câmpului de informații;
3) dacă acest element este singurul;
3.1), ambii indicatori (următorii și înainte) se referă la acest element (figura 2),
3.2), pointerul indică mai întâi un singur element din listă.
4) altfel mutăm indicatorul la elementul i și adăugăm un element nou înaintea elementului i.
Adăugați o nouă valoare în lista dublu legată (apăsați 4), elementul nou va fi adăugat după primul. După operația de împingere, lista conține un element (Figura 2).


Figura 2 Adăugarea unei noi valori.

Adăugați încă câteva valori (împingeți 6 și împingeți 7), fiecare element nou va fi adăugat după primul. Lista conține trei elemente (Figura 3) în următoarea secvență.

Listă dublu legată, algoritmi și programare

Figura 3. Adăugarea de valori noi

Funcția pop afișează elementul i din listă. Funcția efectuează următoarele acțiuni:
1) dacă lista este goală, ieșim din funcție;
2) dacă lista conține un singur element;
2.1) copiați valoarea câmpului de informații
2.2) eliminați elementul din listă
2.3) atribuiți antetul necompletat
3) altfel mutăm indicatorul la elementul i;
3.1) dacă antetul indică elementul i (primul == t), apoi mutați antetul la următorul element (First = t-> next)
3.2) copiați valoarea câmpului de informații
3.3) ștergeți elementul i din listă
4) returnați valoarea câmpului de informații.
Executați funcția pop peste lista liniară (împingeți al treilea element). Obținem următoarea stare a listei conectate (figura 4).

Listă dublu legată, algoritmi și programare

Figura 4. Extragerea elementului.