Listele Conectate individual și dublu (cunoscute și sub numele de Liste Conectate – Linked Lists) conțin colecții de elemente care își păstrează ordinea. Reprezentarea lor în memorie este dinamică, bazată pe pointeri. Ele sunt secvențe legate de elemente. Adăugarea este o operație rapidă, dar este puțin mai lentă decât adăugarea la o listă, pentru că de fiecare dată când adăugăm un element într-o listă conectată, alocăm o nouă zonă de memorie. Alocarea memoriei funcționează la viteze care nu pot fi anticipate cu ușurință. Căutarea într-o listă legată este o operație lentă, deoarece trebuie să trecem prin toate elementele sale. Accesarea unui element prin indexul său este o operație lentă deoarece nu există nicio indexare în liste singure și dublu legate. În schimb, trebuie să trecem prin toate elementele, de la început, unul câte unul. Eliminarea unui element la un indice specificat este o operație lentă deoarece găsirea elementului prin indicele său este o operație lentă. Eliminarea unui element cu o valoare specificată este de asemenea o operație lentă, deoarece implică și ea căutarea. Lista conectată poate adăuga și elimina rapid elemente (cu o complexitate constantă) la cele două capete (cap și coadă). Prin urmare, este foarte util pentru implementarea Stack-urilor, Queue-urilor și a structurilor de date similare. Listele conectate sunt rareori utilizate în practică, deoarece array-urile dinamice (Lista) pot face aproape exact aceleași operații pe care le poate face Linked List, plus faptul că pentru majoritatea acestora funcționează mai repede și sunt mai confortabile. LinkedList utilizează adesea mai multă memorie decât un array sau o listă. Acest lucru se datorează alocării memoriei în .NET Framework și alocării obiectelor. Când aveți nevoie de o listă conectată, utilizați în schimb o listă (despre care vom învăța în lecția următoare), deoarece nu funcționează mai lent și vă oferă o viteză și flexibilitate mai bune. Utilizați LinkedList atunci când trebuie să adăugați și să eliminați elemente la ambele capete ale structurii de date.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// creaza o noua lista conectata LinkedList<string> lista = new LinkedList<string>(); // foloseste metoda AddLast pentru a adauga elemente la sfarsit. lista.AddLast("pisica"); lista.AddLast("caine"); lista.AddLast("om"); // foloseste metoda AddFirst pentru a adauga elemente la inceput. lista.AddFirst("unu"); // insereaza un nod inainte de al doilea element LinkedListNode<string> nod = lista.Find("unu"); lista.AddAfter(nod, "inserat"); // afiseaza elementele listei legate. foreach (var valoare in lista) { Console.WriteLine(valoare); } |
Avantajul principal al listelor conectate față de array-uri este că ele ne oferă posibilitatea de a rearanja elementele în mod eficient.
Principalele metode ale unei liste conectate sunt următoarele:
AddFirst(), AddLast(), AddBefore(), AddAfter() – adaugă elemente la începutul sau sfârșitul structurii de date interne a listei legate, respectiv, adaugă un nou element înainte sau după 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 |
using System; using System.Collections.Generic; class Program { static void Main() { // Creaza o noua instanta linked list. LinkedList<string> lista = new LinkedList<string>(); // Foloseste metoda AddLast pentru a adauga elemente la sfarsit. // Foloseste metoda AddFirst pentru a adauga elemente la inceput. lista.AddLast("caine"); lista.AddLast("pisica"); lista.AddLast("om"); lista.AddFirst("unu"); //adauga un element nou dupa un anumit alt element LinkedListNode<string> curent = lista.FindLast("caine"); lista.AddAfter(curent, "vaca"); //adauga un element nou inainte de un anumit element lista.AddBefore(curent, "pasare"); // Afiseaza elementele listei folosing o bucla foreach foreach (var item in lista) Console.WriteLine(item); } } |
Find() – Caută un element în colecția sa internă de elemente. Aceasta returnează o referință la o instanță a clasei LinkedListNode, care conține pointeri pentru celelalte 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 |
using System; using System.Collections.Generic; class Program { static void Main() { // Creaza o lista conectata noua LinkedList<string> lista = new LinkedList<string>(); // Adauga trei elemente listei. lista.AddLast("unu"); lista.AddLast("doi"); lista.AddLast("trei"); // Insereaza un nod continand rezultatele cautarii, dupa al doilea element LinkedListNode<string> nod = lista.Find("one"); lista.AddAfter(nod, "inserted"); // Cicleaza prin elementele listei conectate. foreach (var valoare in lista) Console.WriteLine(valoare); } } |
RemoveFirst(), RemoveLast() – fac exact ceea ce sugerează numele lor: elimină 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 |
using System; using System.Collections.Generic; class Program { static void Main() { // instantiaza o lista conectata noua LinkedList<string> lista = new LinkedList<string>(); // Adauga trei elemente. lista.AddLast("unu"); lista.AddLast("doi"); lista.AddLast("trei"); // Sterge primul si ultimul element lista.RemoveFirst(); lista.RemoveLast(); // Afiseaza elementele listei foreach (var valoare in lista) Console.WriteLine(valoare); } } |
Ca și structurile de date pe care le-am învățat până acum, Listele conectate conțin de asemenea, câteva metode comune, precum Clear(), Contains(), CopyTo() etc.
Cele mai importante proprietăți ale unei liste conectate sunt:
Count – returnează numărul elementelor din listă.
First – returneaza primul nod al LinkedList.
Last – Obține ultimul nod al LinkedList.
Tags: lista conectata, structuri de date