Listele înlănțuite individual și dublu (cunoscute în mod simplificat și ca Listele Înlănțuite - Linked Lists) conțin colecții de elemente care își păstrează ordinea. Spre deosebire de array-uri, care ocupă spații de memorie continue, listele înlănțuite sunt bazate pe pointeri, permițând alocări de memorie flexibile, non-continue (nu e necesar ca elementele colecției să fie alocate unul după altul, în aceeași zonă de memorie). Această structură facilitează adăugări și ștergeri în orice punct din listă, mai rapide în mod particular la capete - ceea ce face ca listele înlănțuite să fie alegerea perfectă pentru implemenarea structurilor de date precum stive și cozi. Ele sunt secvențe de elemente legate.
Informații Adiționale
Pointerii sunt adrese de memorie, și îi puteți vizualiza ca fiind indicatori care vă spun unde puteți găsi ceva în memorie. În C#, deși puteți folosi pointeri așa cum sunt folosiți în alte limbaje, precum C sau C++, folosim ceva oarecum similar, numit referințe. Când spun ca listele înlănțuite sunt „bazate pe pointeri”, mă refer la faptul că ele folosesc aceste referințe pentru a conecta împreună toate elementele din listă. Fiecare element din listă are o referință care indică spre următorul element, creând un lanț. Acesta este modul în care listele înlănțuite păstrează evidența elementelor în ordine, și acesta este motivul pentru care elementele lor nu trebuie să fie alocate în memorie la adrese consecutive, deoarece orice nod poate indica spre un alt nod, localizat la orice adresă de memorie.
Diferența dintre listele înlănțuite individual și dublu este aceea că în cazul listelor înlănțuite individual, fiecare nod indică doar către următorul nod din lanț, făcând fluxul de curgere „unidirecțional”. În listele înlănțuite dublu, fiecare nod ține o referință (indică) atât catre următorul nod din listă, cât și spre cel anterior, permițând navigarea bi-direcțională.
Principala diferență dintre listele înlănțuite și structuri de date precum array-urile sau listele este aceea că, de vreme ce ele folosesc pointeri pentru a „indica” spre următorul element din secvență, ele nu oferă acces prin index. În limbaj non-academic, acest lucru înseamnă că nu puteți accesa în mod direct „al treilea element”, așa cum ați putea într-un array sau o listă. În schimb, ar trebui să începeți fie la începutul, fie la sfârșitul listei înlănțuite și să „navigați” de la nod ce indică spre următorul nod, ce indică spre următorul nod, până când găsiți nodul pe care îl căutați. Acest fapt implică și că adăugarea și ștergerea elementelor la capetele listelor înlănțuite este eficientă, dar că eficiența descrește pe măsură ce elementul manipulat este localizat mai adânc în structura de date.
Din acest motiv, listele înlănțuite nu sunt atât de des utilizate precum lista, care oferă operațiuni mai rapide pentru majoritatea cazurilor, și sunt mai eficiente cu memoria. Listele oferă de obicei aceleași capabilități, cu mai puțină suprasarcină și mai multă predictibilitate în performanță. Un exemplu unde o listă înlănțuită ar putea fi de preferat unei liste normale ar putea fi atunci când aveți de a face cu o structură de date mare, și ați dori sa adăugați sau să ștergeți elemente în mijlocul ei - toate elementele subsecvente trebuie mutate, deplasate, iar aceasta este o operațiune costisitoare. În cazul unei liste înlănțuite, ar însemna doar „ruperea lanțului” pentru inserarea sau ștergerea elementelor la acea locație, și actualizarea referințelor adiacente care indică spre ele.
Căutarea într-o listă înlănțuită este o operațiune înceată, deoarece trebuie să traversați prin toate elementele ei.
Examplu de utilizare:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
using
System;
namespace
BunaLume
{
class
Program
{
static void Main(string[] args)
{
// creaza o noua lista inlantuita
LinkedList<string> listaInlantuita = new LinkedList<string>();
// foloseste metoda AddLast pentru a adauga elemente la sfarsit
listaInlantuita.AddLast("pisica");
listaInlantuita.AddLast("caine");
listaInlantuita.AddLast("om");
// foloseste metoda AddFirst pentru a adauga elemente la inceput
listaInlantuita.AddFirst("unu");
// insereaza un nod inaintea celui de al doilea (dupa primul nod)
LinkedListNode<string> nod = listaInlantuita.Find("unu");
listaInlantuita.AddAfter(nod, "inserat");
// itereaza prin lista inlantuita
foreach (var valoare in listaInlantuita);
Console.WriteLine(valoare);
Console.ReadLine();
}
}
}
|
Principalele metode ale unei liste înlănțuite sunt următoarele:
AddFirst(), AddLast(), AddBefore(), AddAfter() - adaugă elemente la începutul sau sfârșitul structurii de date interne din lista înlănțuită, respectiv, adaugă înainte sau dupa un anumit element. Exemplu:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
using
System;
namespace
BunaLume
{
class
Program
{
static void Main(string[] args)
{
// creaza o lista inlantuita
LinkedList<string> listaInlantuita = new LinkedList<string>();
// foloseste metoda AddLast pentru a adauga elemente la sfarsit
listaInlantuita.AddLast("pisica");
listaInlantuita.AddLast("caine");
listaInlantuita.AddLast("om");
// foloseste metoda AddFirst pentru a adauga elemente la inceput
listaInlantuita.AddFirst("primul");
// adauga un element nou dupa un anumit alt element
LinkedListNode<string> nod = listaInlantuita.FindLast("caine");
listaInlantuita.AddAfter(nod, "vaca");
// adauga un element nou inainte de un anumit alt element
listaInlantuita.AddBefore(nod, "pasare");
// itereaza prin lista inlantuita
foreach (var valoare in listaInlantuita);
Console.WriteLine(valoare);
Console.ReadLine();
}
}
}
|
Find(), FindLast() - caută un element în colecția internă de elemente. Returnează o referință la o instanță a clasei LinkedListNode, care conține pointeri către alte elemente (rezultatele căutării). Exemplu:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
using
System;
namespace
BunaLume
{
class
Program
{
static void Main(string[] args)
{
// creaza o noua lista inlantuita
LinkedList<string> listaInlantuita = new LinkedList<string>();
// mai intai, adauga trei elemente la lista inlantuita
listaInlantuita.AddLast("unu");
listaInlantuita.AddLast("doi");
listaInlantuita.AddLast("trei");
// insereaza un nod continand rezultatul cautarii, inaiuntea celui de al doilea nod (dupa primul nod)
LinkedListNode<string> nod = listaInlantuita.Find("unu");
listaInlantuita.AddAfter(nod, "inserat");
// itereaza prin lista inlantuita
foreach (var valoare in listaInlantuita);
Console.WriteLine(valoare);
Console.ReadLine();
}
}
}
|
Remove(), RemoveFirst(), RemoveLast() - exact ceea ce sugerează numele lor: prima șterge un anumit nod, celelalte șterg primul sau ultimul element. Exemplu:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
using
System;
namespace
BunaLume
{
class
Program
{
static void Main(string[] args)
{
// creaza o noua lista inlantuita
LinkedList<string> listaInlantuita = new LinkedList<string>();
// mai intai, adauga trei elemente in lista inlantuita
listaInlantuita.AddLast("unu");
listaInlantuita.AddLast("doi");
listaInlantuita.AddLast("trei");
// sterge primul si ultimul element, cat si un nod aleator
listaInlantuita.RemoveFirst();
listaInlantuita.RemoveLast();
LinkedListNode<string> nod = listaInlantuita.Find("doi");
listaInlantuita.Remove(nod);
// itereaza prin lista inlantuita
foreach (var valoare in listaInlantuita);
Console.WriteLine(valoare);
Console.ReadLine();
}
}
}
|
Ca și structurile de date anterioare pe care le-am învățat până acum, listele înlănțuite conțin și niște metode comune, precum Clear(), Contains(), CopyTo(), etc.
Cele mai importante proprietăți ale listelor înlănțuite sunt:
Count - returnează numărul de elemente din listă
First - returnează primul element din listă
Last - returnează ultimul nod din listă.