Sunday, August 18, 2019 15:31

Linked List

Listele Conectate individual și dublu (cunoscute și sub numele de Liste ConectateLinked 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.

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:

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:

RemoveFirst(), RemoveLast() – fac exact ceea ce sugerează numele lor: elimină primul sau ultimul element. Exemplu:

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.

Comments

comments

Tags: ,

Leave a Reply