Двунаправленный (двусвязный) список в C# (класс LinkedList)

Двунаправленный (или двусвязный) список – это список, который состоит из последовательности элементов, каждый из которых содержит информационную часть (данные) и два указателя на соседние элементы (на следующий и предыдущий элементы). В пространстве имен .NET C# System.Collections.Generic содержится класс LinkedList<T>, реализующий двунаправленный (двусвязный список).

В обычном универсальном списке List<T> каждый элемент — это объект типа T, в то время, как в LinkedList<T> каждый узел — это объект класса LinkedListNode<T>. Класс LinkedListNode<T> имеет следующие свойства:

• Value — само значение узла, представленное типом T
• Next - ссылка на следующий элемент типа LinkedListNode<T> в списке. Если следующий элемент отсутствует, то имеет значение null
• Previous: ссылка на предыдущий элемент типа LinkedListNode<T> в списке. Если предыдущий элемент отсутствует, то имеет значение null

Для работы со списком элементов у 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() — удаляет последний узел из списка

Двусвязные списки нашли широкое применения при решении каких-либо геометрических задач. Например, двусвязным списком удобно представлять множество вершин многоугольника — каждый узел списка будет описывать очередную вершину многоугольника и, соответственно, можно достаточно легко определить какая вершина является предыдущей, а какая следующий.

Рассмотрим работу с двусвязным списком LinkedList<T> на примере решения задачи о нахождении площади многоугольника.

Практический пример использования двусвязного списка LinkedList<T> в C#

Итак, решам следующую практическую задачу: найдем площадь многоугольника, заданного списком координат (X, Y).

Задачу будем решать при условии, что многоугольник будет без самопересечений. Для решения этой задачи нам потребуется класс, хранящий данные о координатах вершины. Для этого можно воспользоваться уже имеющемся классом PointF из пространства имен System.Drawingили же написать свой собственный класс, например, такой:

 public class Vertex
{ 
   public double X { get; set; }
   public double Y { get; set; }
   public Vertex(double x, double y)
   {
      X = x;
      Y = y;
   }
}

Площадь многоугольника можно рассчитать с использованием следующей формулы:

где X₀,Y₀ = X_n+1,Y_n+1 (координаты последней точки совпадают с первой). Таким образом, алгоритм расчёта площади многоугольника может быть следующим:

1. Вершины N+1 вершин многоугольника — последняя вершина совпадает с первой. То есть, например, для четырехугольника мы зададим пять вершин.
2. В цикле от 0 до N проходим по вершинам многоугольника и считаем сумму по формуле выше
3. Полученную сумму делим на 2 — это и будет площадь многоугольника.

Реализация представленного алгоритма на примере прямоугольника может выглядеть так:

class Program
{
    static void Main(string[] args)
    {
        LinkedList<Vertex> vertices = new LinkedList<Vertex>();
        vertices.AddLast(new Vertex(0.0, 0.0));
        vertices.AddLast(new Vertex(0.0, 2.0));
        vertices.AddLast(new Vertex(2.0, 2.0));
        vertices.AddLast(new Vertex(2.0, 0.0));
        vertices.AddLast(new Vertex(0.0, 0.0));

        double sum = 0;

        LinkedListNode<Vertex> vertex = vertices.First; 
        for (int i = 0; i < vertices.Count-1; i++)
        {
            sum +=  Abs(vertex.Value.X + vertex.Next.Value.X) * (vertex.Value.Y - vertex.Next.Value.Y);
            vertex = vertex.Next;
        }
        double square = 0.5*sum;
        Console.WriteLine($"Площадь многоугольника {square}");
    }
}

Здесь задан четырехугольник (квадрат) со сторонами равными 2. Нетрудно посчитать, что площадь такого многоугольника будет равна четырем. Вывод консоли представленой выше программы будет следующим:

Это всего лишь один из примеров, когда нам может потребоваться двусвязный список LinkedList<T> в C#.

Итого

Сегодня мы на «живом» примере разобрались с тем, что из себя представляет двусвязный список LinkedList<T> в C# и рассчитали с его помощью площадь многоугольника. Двусвязный список отличается от обычного списка List<T> тем, что каждый его элемент — это объект, который помимо полезной информации (данных объекта) содержит также две ссылки — на предыдущий и следующий элементы списка.