Связный список (Linked List) представляет собой коллекцию связанных элементов, которые содержат в себе хранимые данные, а также ссылку на связанные с ним элементы (один или несколько). Основным преимуществом данной структуры данных перед обычным массивом является ее динамичность — возможность легко менять количество элементов. Давайте рассмотрим пример реализации на языке C# элементарного односвязного списка.

Архитектура Связного списка (Linked List)

Для начала необходимо упомянуть, что существует несколько видов связных списков. Вот наиболее часто используемые из них:

  • Односвязный список
  • Двусвязный список
  • Кольцевой список

Схематическая структура односвязного списка представлена на рисунке ниже.

Связный список (Linked List)

Связный список (Linked List)

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

Реализация Связного списка (Linked List) на языке C#

В качестве примера рассмотрим тривиальную реализацию односвязного списка.

Элемент списка

Рассмотрим класс элемента связного списка. Для того, чтобы сделать его более универсальным мы используем Универсальный параметр T. Это позволит динамически указывать тип данных при использовании списка.

Список элементов

Теперь рассмотрим сам класс связного списка. Для него мы также используем Универсальный (generic) тип T, а также реализуем интерфейс IEnumerable, чтобы в дальнейшем было удобно перебирать элементы списка с помощью цикла foreach.

Использование

Ну и наконец нам остается проверить работу нашего списка. Для этого создадим несколько элементов и проверим работу списка.

Заключение

Здесь представлена элементарная реализация данной динамической структуры данных. На практике она уже реализована намного лучше внутри платформы .NET в виде списка LinkedList<T>, но для того, чтобы понять внутреннюю структуру лучше рассматривать более простые примеры. Исходный код доступен в репозитории github https://github.com/shwanoff/LinkedList

P.S. Присоединяйся в любой удобной для тебя социальной сети. Для меня очень важно оставаться с тобой на связи, ведь у меня есть еще много полезной информации о программировании для тебя, которой я хочу с тобой поделиться.
[DISPLAY_ULTIMATE_PLUS]

%d такие блоггеры, как: