Definire
O listă liniară este o segvenţă finită de n elemente (componente) de acelaşi tip de nod 1,nod 2,...nod n numite şi noduri aflate într-o relaţie de ordine.
Adresa unei variabile poate puncta la rândul său către o altă adresă care să puncteze către o altă adresă. Aşa cum se observă şi din desen, dacă noi "introducem" de fiecare dată o informaţie utilă obţinem o structură de date numită listă liniară. Pentru că fiecare element din listă conţine adresa unui singur element(cel următor), lista o vom numi simplu înlănţuită.
În cadrul unei liste sunt puse în evidenţă :
- un element numit primul element;
- un element numit ultimul element;
- câte un singur element succesor pentru fiecare element al listei (cu excepţia ultimului element, care nu are succesor);
- câte un singur element predecesor pentru fiecare element al listei (cu excepţia primului element, care nu are predecesor);
Pentru a pune în evidenţă succesiunea nodurilor, lista o putem reprezenta astfel:
Componentele listei pot fi date elementare sau date structurate.
Operaţiile cele mai importante definite pe liste sunt :
- Crearea unei liste;
- Adăugarea (inserarea) unui nou nod in listă;
- Ştergerea (eliminarea) unui nod din listă;
- Modificarea valorii pentru un nod al listei;
- Parcurgerea unei liste;
- Determinarea numărului de noduri dintr-o lista;
- Căutarea în listă a nodului (nodurilor) cu o valoare particulară a unui anumit câmp;
- Sortarea nodurilor unei liste în ordine crescatoare (descrescatoare) conţinuturilor anumitor câmpuri ale nodurilor;
- Suprimarea (ştergerea) unei liste;
- Salvarea unei liste;
- Restaurarea unei liste.
Decraraţia
Declaraţia de mai sus este una generică şi pe marginea ei putem face urmatoarele observaţii:
- Pentru a nu complica inutil lucrul, consideram informaţia utilă de tip intreg. Evident că în funcţie de datele problemei putem avea câmpuri de mai multe tipuri, însă pentru exemplificări, pe noi ne vor interesa mecanismele şi operaţiile ce se pot face într-o listă care sunt aceleaşi, indiferent de natura informaţiei utile.
- Întreaga listă este alocată în HEAP, segmentul de date va conţine valoarea primului element;
- Aşa cum arată şi sensul săgeţilor ordinea de parcurgere este de la stânga la dreapta (de la primul element, la ultimul);
- Lista se termină cu "NIL" pe care îl vom numi "pointer în vânt" sau "împământare";
- Pierderea sau ruperea accidentală a unei legături în interiorul listei duce la alterarea definitivă şi irevocabilă a întregului conţinut;
- Listele sunt structuri de date cu acces secvenţial.