Класс LinkedList<T> представляет двухсвязный список, в котором каждый элемент хранит ссылку одновременно на следующий и на предыдущий элемент.
Создание связанного списка
Для создания связного списка можно принименять один из его конструктора. Например, создадим пустой связный список:
LinkedList<string> people = new LinkedList<string>();
В данном случае связанный список people предназначен для хранения строк.
Также можно в конструктор передать коллекцию элементов, например, список List, по которому будет создан связный список:
var employees = new List<string> { "Tom", "Sam", "Bob" };
LinkedList<string> people = new LinkedList<string>(employees);
foreach (string person in people)
{
Console.WriteLine(person);
}
LinkedListNode
Если в простом списке List<T> каждый элемент представляет объект типа T, то в LinkedList<T> каждый узел представляет объект класса LinkedListNode<T>. А добавляемые в связанный список элементы T фактически обертываются в объект LinkedListNode.
Класс LinkedListNode имеет следующие свойства:
Value: возвращает или устанавливает само значение узла, представленное типом T
Next: возвращает ссылку на следующий элемент типа LinkedListNode<T> в списке. Если следующий элемент отсутствует, то имеет значение null
Previous: возвращает ссылку предыдущий элемент типа LinkedListNode<T> в списке. Если предыдущий элемент отсутствует, то имеет значение null
Свойства LinkedList
Класс LinkedList определяет следующие свойства:
Count: количество элементов в связанном списке
First: первый узел в списке в виде объекта LinkedListNode<T>
Last: последний узел в списке в виде объекта LinkedListNode<T>
Используем эти свойства:
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
Используя свойства LinkedList и LinkedListNode, можно пройтись по всем элементам списка в прямом или обратном порядке:
LinkedList<string> people = new LinkedList<string>(new[] { "Tom", "Sam", "Bob" });
// от начала до конца списка
var currentNode = people.First;
while(currentNode != null)
{
Console.WriteLine(currentNode.Value);
currentNode = currentNode.Next;
}
// с конца до начала списка
currentNode = people.Last;
while (currentNode != null)
{
Console.WriteLine(currentNode.Value);
currentNode = currentNode.Previous;
}
Методы LinkedList
Используя методы класса LinkedList<T>, можно обращаться к различным элементам, как в конце, так и в начале списка:
AddAfter(LinkedListNode<T> node, LinkedListNode<T> newNode): вставляет узел newNode в список после узла node.
AddAfter(LinkedListNode<T> node, T value): вставляет в список новый узел со значением value после узла node.
AddBefore(LinkedListNode<T> node, LinkedListNode<T> newNode): вставляет в список узел newNode перед узлом node.
AddBefore(LinkedListNode<T> node, T value): вставляет в список новый узел со значением value перед узлом node.
AddFirst(LinkedListNode<T> node): вставляет новый узел в начало списка
AddFirst(T value): вставляет новый узел со значением value в начало списка
AddLast(LinkedListNode<T> node): вставляет новый узел в конец списка
AddLast(T value): вставляет новый узел со значением value в конец списка
RemoveFirst(): удаляет первый узел из списка. После этого новым первым узлом становится узел, следующий за удаленным
RemoveLast(): удаляет последний узел из списка
Применим некоторые из этих методов:
var people = new LinkedList<string>();
people.AddLast("Tom"); // вставляем узел со значением Tom на последнее место
//так как в списке нет узлов, то последнее будет также и первым
people.AddFirst("Bob"); // вставляем узел со значением Bob на первое место
// вставляем после первого узла новый узел со значением Mike
if (people.First != null) people.AddAfter(people.First, "Mike");
// теперь у нас список имеет следующую последовательность: Bob Mike Tom
foreach (var person in people) Console.WriteLine(person);
Подобным образом можно создавать связанные списки и других типов:
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;
}