O listă liniară (numită şi listă înlănţuită -”Linked List”) este o colecţie de n>=o elemente x[1], … x[n] toate de un tip oarecare, numite noduri între care există o relaţie de ordine determinată de poziţia lor relativă. Ea este deci o mulţime eşalonată de elemente de acelaşi tip având un număr arbitrar de elemente. Numărul n al nodurilor se numeşte lungimea listei. Dacă n=o, lista este vidă. Dacă n>=i, x[1] este primul nod iar x[n] este ultimul nod. Pentru 1

Pentru implementarea dinamică a unei liste liniare (folosind pointeri), nodurile listei vor fi structuri ce conţin două tipuri de informaţie:
• câmpurile ce conţin informaţia structurală a nodului, numite într-un cuvânt INFO
• câmpurile ce conţin informaţia de legătură, numite LINK ce vor conţine pointeri la nodurile listei. înlănţuirea secvenţială a elementelor unei liste se face utilizând variabile de tip pointer, care specifică adresa de memorie a elementelor adiacente. Fiecare nod are un predecesor şi un succesor (mai puţin elementele prim şi ultim dacă lista nu este circulară).

Listele înlănţuite cu un singur câmp de legătură se numesc liste simplu înlănţuite (legătura indică următorul element din listă) iar cele cu 2 câmpuri de legătură liste dublu înlănţuite (o legătură indică nodul precedent iar cealaltă nodul succesor).

Principalele operaţii care se fac asupra unei liste liniare sunt:
• creare (inserare într-o listă iniţial vidă)
• inserare nod
• ştergere nod
• traversare listă
• căutare nod

Crearea unei liste simplu înlănţuite se face în mai mulţi paşi:

1.Iniţializarea listei

prim=NULL;


2.Alocarea de spaţiu pentru nodul ce urmează să fie introdus în listă şi citirea informaţiei aferentă acestui nod:

p=(lista *)malloc(sizeof(lista));
scanf("%d",&p->cheie);


3.Generarea legăturilor corespunzătoare:

p->urm=NULL; //nu există încă un element următor în listă
prim=p; //pointerul prim trebuie să indice în permanenţă capul listei


4.Inserarea unui element într-o listă simplu înlănţuită (care nu este vidă) se poate face astfel:
în capul listei:

//alocarea de spaţiu pentru elementul ce urmează să fie inserat
p=(lista*)malloc(sizeof(lista));
//citim informaţia din nodul ce urmează să fie inserat
scanf("%d",&p->cheie);
//următorul element celui pe care îl inserăm va fi fostul prim element al listei
p->urm=prim;
//prim va indica noul cap al listei
prim=p;


La sfârşitul listei – în cazul în care nu vom lucra cu un pointer care să indice sfârşitul listei (nu este obligatorie decât păstrarea unui pointer spre capul listei) va fi necesară traversarea listei până în final după care se face inserarea noului element:

//pornim cu pointerul p de la capul listei şi ieşim din ciclul for în momentul în care
//pointerul p va indica ultimul element al listei
for (p=prim; p->urm; p=p->urm);
//alocarea de spaţiu pentru elementul ce urmează să fie inserat
q=(lista*)malloc(sizeof(lista));
//citim informaţia din nodul ce urmează să fie inserat
scanf("%d",&q->cheie);
//stabilim legătura dintre ultimul element şi elementul ce urmează să fie inserat
p->urm=q;
//noul ultim element nu are succesor
q->urm=NULL;


După nodul precizat de o cheie dată (conţinută de variabila key);

//pornim cu pointerul p din capul listei şi ieşim din ciclul for dacă am ajuns la
//capătul listei sau dacă valoarea din câmpul cheie este cea căutată
for (p=prim; p&&p->cheie!=key; p=p->urm);
//dacă ieşirea din ciclu s-a făcut prin găsirea valorii dorite
if(p)
{
  //alocarea de spaţiu pentru elementul ce urmează să fie inserat
  q=(lista*)malloc(sizeof(lista));
  //citim informaţia din nodul ce urmează să fie inserat
  scanf("%d",&q->cheie);
  //după nodul indicat de pointerul p va urma noul nod indicat de q
  q->urm=p->urm;
  //noul nod inserat nu are succesor
  p->urm=q;
}
else
  //dacă ieşirea din ciclu s-a datorat ajungerii la capătul listei
  printf("Nu există cheia specificata!\n");


Înaintea unui nod precizat printr-o cheie dată (conţinută de variabila key);

//pornim cu pointerul p din capul listei şi ieşim din ciclul for dacă am ajuns la
//capătul listei sau dacă valoarea din câmpul cheie este cea căutată
for(p=prim;p&&p->cheie!=key;p=p->urm);
//dacă ieşirea din ciclu s-a făcut prin găsirea valorii dorite
if(p)
{
  //alocarea de spaţiu pentru elementul ce urmează să fie inserat
  q= (lista*)malloc(sizeof(lista));
  //folosim un artificiu pentru a permite inserarea unui nod înainte de nodul indicat
  //de pointerul p. Pentru aceasta noul nod creat va prelua informaţia din nodul
  //indicat de pointerul p, iar noul nod va înlocui nodul indicat de pointerul p
  q->cheie=p->cheie;
  //înlănţuirea cu următorul nod după p
  q->urm=p->urm;
  //citim informaţia ce va înlocui vechea valoare din nodul indicat de pointerul p
  scanf("%d",&p->cheie);
  //înlănţuirea elementului având noua valoarea a cheii cu noul element inserat
  p->urm=q;
}
else
  //dacă ieşirea din ciclu s-a datorat ajungerii la capătul listei
  printf("Nu exista cheia specificata !\n");


Traversarea unei liste simplu înlănţuite se face astfel:

for(p=prim;p;p=p->urm) printf("%d ",p->cheie);
putchar("\n");


Căutarea unei anumite valori într-o listă simplu înlănţuită:

printf("Introduceti valoarea cautata:");
//citim în variabila key valoarea ce urmează să o căutăm în listă
scanf("%d", &key);
//traversăm lista până găsim elementul dorit sau ajungem în finalul listei
for(p=prim;p&&p->cheie!=key; p=p->urm);
//dacă nu am ajuns la sfârşitul listei deci ieşirea din ciclul for s-a datorat găsirii
//valorii key în listă
if (p)
  printf("Valoarea a fost găsită !\n");
else
  //dacă ieşirea din ciclu s-a datorat ajungerii la capătul listei
  printf("Nu există cheia specificata!\n");


Ştergerea unui nod din lista simplu înlănţuită
Ştergerea primului nod:

p=prim;
//pointerul prim va indica următorul element care devine astfel capul listei
prim=prim->urm;
//eliberăm memoria ocupată de nodul indicat de pointerul p
free(p);


Ştergerea unui nod având o cheie dată (conţinută de variabila key):

r=NULL;
for(p=prim;p&&p->cheie!=key;r=p,p=p->urm);
if(p)
  if (p<>prim)
  {
    r->urm=p->urm;
    free(p);
  }
  else
  {
    prim=prim->urm;
    free(p);
  }
else
  printf("Nu exista cheia specificata\n");


Ştergerea tuturor elementelor unei liste simplu înlănţuite

while (prim)
{
  p=prim;
  prim=prim->urm;
  free(p);
}