Liste liniar inlantuite
----- ----- --------- ----- ----
O lista liniar inlantuita este o structura de
date ce are elementele legate secvential. Exista un pointer
catre primul element al listei,
fiecare element al listei pointeaza catre urmatorul element al listei,
av 19519m124t and ultimul element pointand catre NULL. De obicei, o lista
inlantuita se creaza dinamic.
Scriem in fisierul "header" intitulat "list.h" urmatoarele
declaratii:
#include <stdio.h>
typedef char DATA;
struct lista_inlantuita
;
typedef struct lista_inlantuita
ELEMENT;
typedef ELEMENT
*
LISTA;
Relativ la alocarea dinamica, va reamintim ca functia
"malloc()" are un singur argument de tip "size_t" si
intoarce un pointer catre
"void" care pointeaza catre adresa de baza a spatiului de
memorie alocat (evident, cauta spatiu suficient pentru un obiect). Astfel,
daca "head" este o variabila de tip "LISTA", atunci
head = (LISTA) malloc(sizeof(ELEMENT));
va produce o bucata din memorie menita sa memoreze un ELEMENT asignand
adresa de baza pointerului "head".
------------
Exemplu:
------------
Presupunem ca vrem sa creeam dinamic o lista
liniar inlantuita pentru memorarea a trei caractere 'n', 'e' si 'w'.
Considerand
head = (LISTA)
malloc(sizeof(ELEMENT));
head -> d = 'n';
head -> next = NULL;
obtinem un memorie ceva de
genul:
----- ----- ------
head --->| 'n' | NULL |
----- ----- -----
d next
Al doilea element este adaugat de instructiunile:
head -> next = (LISTA)
malloc(sizeof(ELEMENT));
head -> next -> d = 'e';
head -> next -> next =
NULL;
In memorie avem:
------------ ----- ----- -----
head--->| 'n' | ---|--->| 'e' | NULL |
------------ ----- ----- -----
d next
d next
In sfarsit, adaugam si al treilea element:
head -> next -> next =
malloc(sizeof(ELEMENT));
head -> next -> next
-> d = 'w';
head -> next -> next
-> next = NULL;
In memorie avem:
----- ----- ----
----- ----- ---- ----- ----- ------
head--->| 'n' | ---|--->| 'e'
| ---|--->| 'w' | NULL |
----- ----- ----
----- ----- ---- ----- ----- ------
d
next d
next
d next
----- ----- ----------------
Operatii pentru liste
----- ----- ----------------
Operatiile de baza pentru liste liniar inlantuite includ urmatoarele:
1. Crearea unei liste
2. Numararea elementelor unei liste
3. Cautarea unui element
4. Inserarea unui element
5. Stergerea unui element
