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

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

1. Односвязный список

2. Двусвязный список

3. Кольцевой список

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

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

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

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

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

Теперь реализуем метод добавления данных в коллекцию

Удаление данных из коллекции

Ну и наконец вспомогательные методы для полной очистки связного списка и перебора элементов в цикле

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

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

В итоге получаем следующий вывод на консоль

Заключение

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