Lista dublu înlănțuită LinkedList

Clasa LinkedList<T> reprezintă o listă dublu înlănțuită, în care fiecare element stochează simultan o referință către următorul și către elementul anterior.

Crearea unei liste înlănțuite

Pentru a crea o listă înlănțuită, putem folosi unul dintre constructorii săi. De exemplu, să creăm o listă înlănțuită goală:

LinkedList<string> people = new LinkedList<string>();

În acest caz, lista înlănțuită people este destinată stocării șirurilor de caractere.

De asemenea, putem transmite o colecție de elemente constructorului, de exemplu, o listă List, după care va fi creată lista înlănțuită:

var employees = new List<string> { "Tom", "Sam", "Bob" };
LinkedList<string> people = new LinkedList<string>(employees);
foreach (string person in people)
{
   Console.WriteLine(person);
}

LinkedListNode

Dacă într-o listă simplă List<T> fiecare element reprezintă un obiect de tip T, în LinkedList<T> fiecare nod reprezintă un obiect al clasei LinkedListNode<T>. Iar elementele adăugate în lista înlănțuită T sunt de fapt învelite într-un obiect LinkedListNode.

Clasa LinkedListNode are următoarele proprietăți:

• Value: returnează sau setează valoarea nodului, reprezentată de tipul T
• Next: returnează referința către următorul element de tip LinkedListNode<T> din listă. Dacă următorul element nu există, valoarea este null
• Previous: returnează referința către elementul anterior de tip LinkedListNode<T> din listă. Dacă elementul anterior nu există, valoarea este null

Proprietăți LinkedList

Clasa LinkedList definește următoarele proprietăți:

• Count: numărul de elemente din lista înlănțuită
• First: primul nod din listă sub formă de obiect LinkedListNode<T>
• Last: ultimul nod din listă sub formă de obiect LinkedListNode<T>

Utilizăm aceste proprietăți:

var employees = new List<string> { "Tom", "Sam", "Bob" };
LinkedList<string> people = new LinkedList<string>(employees);
Console.WriteLine(people.Count);         // 3
Console.WriteLine(people.First?.Value);  // Tom
Console.WriteLine(people.Last?.Value);   // Bob

Utilizând proprietățile LinkedList și LinkedListNode, putem parcurge toate elementele listei în ordine directă sau inversă:

LinkedList<string> people = new LinkedList<string>(new[] { "Tom", "Sam", "Bob" });

// de la începutul până la sfârșitul listei
var currentNode = people.First;
while(currentNode != null)
{
   Console.WriteLine(currentNode.Value);
   currentNode = currentNode.Next;
}

// de la sfârșitul până la începutul listei
currentNode = people.Last;
while (currentNode != null)
{
   Console.WriteLine(currentNode.Value);
   currentNode = currentNode.Previous;
}

Metode LinkedList

Utilizând metodele clasei LinkedList<T>, putem accesa diferite elemente, atât la sfârșitul, cât și la începutul listei:

• AddAfter(LinkedListNode<T> node, LinkedListNode<T> newNode): inserează nodul newNode în listă după nodul node
• AddAfter(LinkedListNode<T> node, T value): inserează în listă un nou nod cu valoarea value după nodul node
• AddBefore(LinkedListNode<T> node, LinkedListNode<T> newNode): inserează în listă nodul newNode înaintea nodului node
• AddBefore(LinkedListNode<T> node, T value): inserează în listă un nou nod cu valoarea value înaintea nodului node
• AddFirst(LinkedListNode<T> node): inserează un nou nod la începutul listei
• AddFirst(T value): inserează un nou nod cu valoarea value la începutul listei
• AddLast(LinkedListNode<T> node): inserează un nou nod la sfârșitul listei
• AddLast(T value): inserează un nou nod cu valoarea value la sfârșitul listei
• RemoveFirst(): elimină primul nod din listă. După aceasta, nodul de lângă cel șters devine primul nod nou
• RemoveLast(): șterge ultimul nod din listă

Aplicăm unele dintre aceste metode:

var people = new LinkedList<string>();
people.AddLast("Tom"); // inserăm nodul cu valoarea Tom pe ultimul loc
                       // deoarece lista nu are noduri, ultimul va fi și primul
people.AddFirst("Bob"); // inserăm nodul cu valoarea Bob pe primul loc

// inserăm după primul nod un nou nod cu valoarea Mike
if (people.First != null) people.AddAfter(people.First, "Mike");

// acum lista are următoarea secvență: Bob Mike Tom
foreach (var person in people) Console.WriteLine(person);

În mod similar, putem crea liste înlănțuite de alte tipuri:

var company = new LinkedList<Person>();

company.AddLast(new Person("Tom"));
company.AddLast(new Person("Sam"));
company.AddFirst(new Person("Bill"));

foreach (var person in company) Console.WriteLine(person.Name);

class Person
{
   public string Name { get; }
   public Person(string name) => Name = name;
}