Связный список C# — Linked List C# представляет собой коллекцию связанных элементов, которые содержат в себе хранимые данные, а также ссылку на связанные с ним элементы (один или несколько). Основным преимуществом данной структуры данных перед обычным массивом является ее динамичность — возможность легко менять количество элементов. Давайте рассмотрим пример реализации на языке C# элементарного односвязного списка.
Архитектура Связного списка (Linked List)
Для начала необходимо упомянуть, что существует несколько видов связных списков. Вот наиболее часто используемые из них:
- Односвязный список
- Двусвязный список
- Кольцевой список
Схематическая структура односвязного списка представлена на рисунке ниже.
Элемент данных добавляется в конец списка путем установки на него ссылки из элемента, который был крайним ранее. Таким образом, получается своеобразная цепочка, в которой каждый элемент данных имеет указатель на следующий.
Реализация Связного списка (Linked List) на языке C#
В качестве примера рассмотрим тривиальную реализацию односвязного списка.
Элемент списка
Рассмотрим класс элемента связного списка. Для того, чтобы сделать его более универсальным мы используем Универсальный параметр T. Это позволит динамически указывать тип данных при использовании списка.
using System;
namespace LinkedList
{
/// <summary>
/// Класс, описывающий элемент связного списка.
/// </summary>
/// <typeparam name="T"> Тип хранимых данных. </typeparam>
public class Item<T>
{
/// <summary>
/// Хранимые данные.
/// </summary>
public T Data { get; set; }
/// <summary>
/// Следующий элемент связного списка.
/// </summary>
public Item<T> Next { get; set; }
/// <summary>
/// Создание нового экземпляра связного списка.
/// </summary>
/// <param name="data"> Сохраняемые данные. </param>
public Item(T data)
{
// Не забываем проверять входные аргументы на null.
if(data == null)
{
throw new ArgumentNullException(nameof(data));
}
Data = data;
}
/// <summary>
/// Приведение объекта к строке.
/// </summary>
/// <returns> Хранимые данные. </returns>
public override string ToString()
{
return Data.ToString();
}
}
}Список элементов
Теперь рассмотрим сам класс связного списка. Для него мы также используем Универсальный (generic) тип T, а также реализуем интерфейс IEnumerable, чтобы в дальнейшем было удобно перебирать элементы списка с помощью цикла foreach.
using System;
using System.Collections;
using System.Collections.Generic;
namespace LinkedList
{
public class LinkedList<T> : IEnumerable<T>
{
/// <summary>
/// Первый (головной) элемент списка.
/// </summary>
private Item<T> _head = null;
/// <summary>
/// Крайний (хвостовой) элемент списка.
/// </summary>
private Item<T> _tail = null;
/// <summary>
/// Количество элементов списка.
/// </summary>
private int _count = 0;
/// <summary>
/// Количество элементов списка.
/// </summary>
public int Count
{
get => _count;
}
/// <summary>
/// Добавить данные в связный список.
/// </summary>
/// <param name="data"></param>
public void Add(T data)
{
// Не забываем проверять входные аргументы на null.
if (data == null)
{
throw new ArgumentNullException(nameof(data));
}
// Создаем новый элемент связного списка.
var item = new Item<T>(data);
// Если связный список пуст, то добавляем созданный элемент в начало,
// иначе добавляем этот элемент как следующий за крайним элементом.
if(_head == null)
{
_head = item;
}
else
{
_tail.Next = item;
}
// Устанавливаем этот элемент последним.
_tail = item;
// Увеличиваем счетчик количества элементов.
_count++;
}
/// <summary>
/// Удалить данные из связного списка.
/// Выполняется удаление первого вхождения данных.
/// </summary>
/// <param name="data"> Данные, которые будут удалены. </param>
public void Delete(T data)
{
// Не забываем проверять входные аргументы на null.
if (data == null)
{
throw new ArgumentNullException(nameof(data));
}
// Текущий обозреваемый элемент списка.
var current = _head;
// Предыдущий элемент списка, перед обозреваемым.
Item<T> previous = null;
// Выполняем переход по всех элементам списка до его завершения,
// или пока не будет найден элемент, который необходимо удалить.
while(current != null)
{
// Если данные обозреваемого элемента совпадают с удаляемыми данными,
// то выполняем удаление текущего элемента учитывая его положение в цепочке.
if(current.Data.Equals(data))
{
// Если элемент находится в середине или в конце списка,
// выкидываем текущий элемент из списка.
// Иначе это первый элемент списка,
// выкидываем первый элемент из списка.
if (previous != null)
{
// Устанавливаем у предыдущего элемента указатель на следующий элемент от текущего.
previous.Next = current.Next;
// Если это был последний элемент списка,
// то изменяем указатель на крайний элемент списка.
if(current.Next == null)
{
_tail = previous;
}
}
else
{
// Устанавливаем головной элемент следующим.
_head = _head.Next;
// Если список оказался пустым,
// то обнуляем и крайний элемент.
if(_head == null)
{
_tail = null;
}
}
// Элемент был удален.
// Уменьшаем количество элементов и выходим из цикла.
// Для того, чтобы удалить все вхождения данных из списка
// необходимо не выходить из цикла, а продолжать до его завершения.
_count--;
break;
}
// Переходим к следующему элементу списка.
previous = current;
current = current.Next;
}
}
/// <summary>
/// Очистить список.
/// </summary>
public void Clear()
{
_head = null;
_tail = null;
_count = 0;
}
/// <summary>
/// Вернуть перечислитель, выполняющий перебор всех элементов в связном списке.
/// </summary>
/// <returns> Перечислитель, который можно использовать для итерации по коллекции. </returns>
public IEnumerator<T> GetEnumerator()
{
// Перебираем все элементы связного списка, для представления в виде коллекции элементов.
var current = _head;
while(current != null)
{
yield return current.Data;
current = current.Next;
}
}
/// <summary>
/// Вернуть перечислитель, который осуществляет итерационный переход по связному списку.
/// </summary>
/// <returns> Объект IEnumerator, который используется для прохода по коллекции. </returns>
IEnumerator IEnumerable.GetEnumerator()
{
// Просто возвращаем перечислитель, определенный выше.
// Это необходимо для реализации интерфейса IEnumerable
// чтобы была возможность перебирать элементы связного списка операцией foreach.
return ((IEnumerable)this).GetEnumerator();
}
}
}Использование
Ну и наконец нам остается проверить работу нашего списка. Для этого создадим несколько элементов и проверим работу списка.
using System;
namespace LinkedList
{
class Program
{
static void Main(string[] args)
{
// Создаем новый связный список.
var list = new LinkedList<int>();
// Добавляем элементы.
list.Add(1);
list.Add(5);
list.Add(17);
list.Add(42);
list.Add(-69);
// Выводим все элементы на консоль.
foreach(var item in list)
{
Console.WriteLine(item);
}
Console.WriteLine();
// Удаляем элемент.
list.Delete(17);
// Выводим все элементы еще раз.
foreach (var item in list)
{
Console.WriteLine(item);
}
Console.ReadLine();
}
}
}Заключение по теме Связный Список C#
Здесь представлена элементарная реализация данной динамической структуры данных. На практике она уже реализована намного лучше внутри платформы .NET в виде списка LinkedList<T>, но для того, чтобы понять внутреннюю структуру лучше рассматривать более простые примеры. Исходный код доступен в репозитории github https://github.com/shwanoff/LinkedList
Также рекомендую изучить статью Список C# | List C# . А еще подписывайтесь на группу ВКонтакте, Telegram и YouTube-канал. Там еще больше полезного и интересного для программистов.
