Theory and Tasks for Students - Spring 2019
Linked and Double Linked Lists

Список (Linked List) - структура данных, оперирующая понятием "ссылка". Её суть в том, что каждый элемент знает о своём соседе, т.е. имеет ссылку на него. Это позволяет по-настоящему динамически выделять память под новые элементы и очищать её при их удалении. Однако у списка есть две проблемы - первая из них это получение элемента по индексу, такая операция имеет сложность O(n), т.к. требуется перебирать элементы по порядку, начиная с первого. Вторая - это потенциальная возможность зациклить список, если пользователь списка имеет контроль над процессом создания новых элементов. Самый простой цикл - один элемент, которые ссылается на самого себя, как на следующего.

Список описывается двумя классами - сам класс списка List, которым пользуется внешний пользователь, и внутренний класс/структура ListItem, имеющий два поля - хранимое значение и ссылка на следующий элемент. У класс List имеется ссылка на первый элемент и методы для взаимодействия пользователя со списком:

  • void InsertAt(value, index) - создаёт новый элемент списка ListItem и вставляет его после элемента с индекс index, стоимость O(index);
  • void RemoveAt(index) - удаляет из списка элемент с индексом index, стоимость O(index);
  • type GetAt(index) - возвращает значение элемента списка с индексом index, стоимость O(index).

Как видно, преимущество списка в том, что кроме поиска элемента по индексу, стоимость всех операций на самом деле O(1). Существуют реализации, в которых пользователю списка возвращаются ссылки на внутренние элементы списка ListItem, а не только хранимые значения - это позволяет, например, совершать операции добавления элементов void InsertAfter(listItem, value) за O(1). Для удобства можно определить и другие методы, например:

  • List SplitAt(index) - разделяет список на два, отцепляя от исходного все элементы, начиная от элемента с индексом index и возвращая их как новый список, O(index);
  • void ConcatAt(list, index) - прицепляет список-аргумент в исходный после элемента с индексом index, O(index);
  • void PushFront(value) - добавляет элемент в начало, сокращение для InsertAt(item, -1), стоимость O(1);
  • void PopFront(value) - удаляет элемент из начала списка, сокращение для RemoveAt(item, 0), стоимость O(1);

Если хранить ссылку на последний элемент, можно также добавить операции для добавления и удаления последнего элемента. В случае двусвязного списка, каждый элемент должен хранить ссылку как на следующий, так и на предыдущий, что позволяет "проходить" по списку в обоих направлениях, для этого можно реализовать ещё один класс итератора.

Важно понимать, что встроенный в .NET Framework класс System.Collections.Generic.List является не таким списком, а "вектором", т.е. массивом, динамически меняющим размер. Реальный список - System.Collections.Generic.LinkedList