Если вы знакомы с концепцией указателей, у вас, вероятно, не возникнет проблем с пониманием принципов работы связанных списков.
По сути, связанный список — это массив объектов, который, однако, сильно отличается от простого массива. Обычный массив автоматически выделяет определенную часть памяти. Давайте посмотрим на пример:
string[] dataSet = new string[100];for (int i = 0; i < 99; i++){ dataSet[i] = string.Format("Sample Data {0}", i.ToString());}
Этот код выделяет пространство для 100 строковых элементов и заполняет каждый из них строкой. Однако в обычном массиве есть несколько недостатков. Что если в дальнейшем будет использовано более 100 предметов? Массив необходимо расширить, и если он жестко закодирован до ста значений, могут возникнуть проблемы с переполнением данных. Другая проблема заключается в неэффективном использовании памяти, когда в нем менее ста элементов. В этом случае много памяти остается неиспользованным.
Связанные списки имеют тенденцию решать две из вышеупомянутых проблем. Во-первых, в связанном списке нет одного поля для значения, а два — одно с сохраненными данными, а другое ссылается на следующее значение. Эти два поля вместе составляют узел, то есть — единицу внутри связанного списка.
Значения не хранятся в каком-либо определенном порядке, однако ссылка на следующее значение помогает найти и вставить необходимые значения намного проще.
В C # связанные списки обрабатываются с помощью класса LinkedList <T> , который содержит несколько экземпляров LinkedListNode <T> . После разборки LinkedListNode <T> появляется интересная вещь:
Взгляните на выделенные поля — в .NET узел связанного списка хранит не только ссылку на следующий узел, но и на предыдущий узел. В этом случае схема связанного списка, показанная выше, будет выглядеть следующим образом:
Поскольку значения 1 и 6 являются пределами списка, для первого элемента предыдущий узел равен NULL, а для последнего элемента следующий узел равен NULL.
Чтобы создать экземпляр связанного списка, вы можете использовать следующий код:
LinkedList<string> list = new LinkedList<string>();
Класс LinkedList <T> представляет собой универсальную коллекцию (член пространства имен System.Collections.Generic ), поэтому он безопасно набирается — при использовании разработчик знает о типе элементов внутри него.
Поскольку элементы добавляются без заказа, каждому узлу нужна ссылка. Первоначально вы можете добавлять узлы с помощью методов AddFirst и AddLast . Например:
list.AddFirst("Data Value 1");list.AddLast("Data Value 6");
Даже если уже есть первый и последний элемент, новый узел заменит существующий, и список будет корректироваться соответствующим образом. Чтобы доказать это, попробуйте этот код:
list.AddFirst("Data Value 1");list.AddFirst("Data Value 2");LinkedListNode<string> node = list.Find("Data Value 1");Debug.Print(node.Previous.Value.ToString());
Поскольку узел, содержащий «Значение данных 2», размещается первым, узел, содержащий «Значение данных 1», перемещается на второе место. Поэтому свойство Previous автоматически устанавливается на новый узел, который был вставлен.
То же самое относится и к методу AddLast , хотя свойство Next будет изменено.
Если вы хотите добавить узлы между первым и последним, вы можете использовать методы AddBefore и AddAfter. AddBefore добавит узел перед экземпляром LinkedListNode, который вы собираетесь передать, и AddAfter добавит узел после него.
Для указания начального узла, который будет учитываться при назначении свойства Previous, можно использовать методы Find и FindLast . Find находит первый встречающийся экземпляр узла, а FindLast находит последний экземпляр встречающегося узла, поскольку узлы могут иметь одинаковое значение.
Вот пример того, как использовать методы, упомянутые выше:
list.AddAfter(list.Find("Data Value 1"), "Data Value 2");
Вы должны быть очень осторожны при поиске узла, так как, если вы не укажете правильное искомое значение, будет возвращено нулевое значение, и это вызовет исключение, так как значение не может быть нулевым.
Поскольку список не отсортирован, а значения добавляются динамически, невозможно получить их по индексу, поскольку для узлов не существует фактического значения индекса. Единственный способ найти значение — использовать линейный поиск, который обеспечивается методами Find и FindLast .