Liste simplu înlănțuite

O lista L e o secventa de zero sau mai multe elemente, numite noduri, toate fiind de acelasi tip de baza T. L=a1, a2, ... an (n>=0) O proprietate importanta a unei liste este aceea ca nodurile sale pot fi ordonate liniar functie de pozitia lor in cadrul listei.

Se spune ca ai precede pe ai+1 (i=1, 2, ... n-1), iar ai succede pe ai-1 (i=2, 3, ... n), ai aflandu-se pe pozitia i.

Se postuleaza (presupune) existenta pozitiei urmatoare ultimului element al listei si se introduce functia FIN (L) ce va returna pozitia urmatoare pozitiei n din lista L de n elemente.

Folosind notatiile anterioare si notand x (de tip T) un nod al listei, iar p fiind de tip pozitie, se introduce urmatorul set reprezentativ de operatori aplicabili obiectelor de tip lista: p=FIN (L), L=a1, ... an, x p>FIN (L), rezultatul insertiei este imprevizibil.

Implementarea listelor. Structuri recursive de tip lista Cu ajutorul tipului pointer, se defineste structura unui nod al listei liniare care apare ca o structura recursiva, avand o componenta de tip identic cu al structurii complete.

type PointerNod=^Nod; Nod=record cheie: TipCheie; urmator: PointerNod; info: TipInfo end; var inceput: PointerNod; Caracteristica unei astfel de structuri consta in prezenta unei singure inlantuiri. Campul cheie serveste la identificarea nodului (acest camp poate face parte din informatia utila, el este utilizat in cazul cautarilor, sortarii), campul urmator e pointer de inlantuire la nodul urmator, iar cel info contine informatia utila.

Variabila inceput indica spre primul nod al listei; in unele situatii in locul lui inceput se utilizeaza un nod fictiv, adica o variabila de tip nod cu campurile cheie si info neprecizate, dar campul urmator indicand spre primul nod al listei.

De asemenea uneori e util a se pastra pointerul spre ultimul nod al listei.

O varianta este a listelor circulare la care dispare notiunea de prim, ultim nod.

Tehnici de insertie a nodurilor si de creare a listelor inlantuite a) insertia unui nod la inceputul listei Daca inceput e variabila pointer ce indica spre primul nod al listei, iar q o variabila auxiliara de tip pointer, secventa urmatoare realizeaza insertia la inceputul listei si actualizeaza pointerul inceput: new (q); {creeaza spatiu pentru un nou nod} q^. urmator: =inceput; {asignarea campurilor cheie si info} inceput: =q; Secventa e corecta si pentru insertia intr-o lista vida, caz in care inceput=nil (nil fiind pointerul vid, care nu se refera la nici o variabila indicata). b) insertia unui nod la sfarsitul listei Devine mai simpla daca se pastreaza o variabila sfarsit indicand spre ultimul nod al listei: new (q); {creeaza spatiu pentru noul nod ultim al listei} sfirsit^. urmator: =q; q^. urmator: =nil; {asignarea campurilor cheie si info} sfirsit: =q; Pentru insertia la sfarsitul listei e necesara existenta a cel putin un nod, care se creeaza prin procedura de la paragraful ...