Структуры данных
Связный список
Связный список (Linked List) представляет набор связанных узлов, каждый из которых хранит собственно данные и ссылку на следующий узел. В реальной жизни связный список можно представить в виде поезда, каждый вагон которого может содержать некоторый груз или пассажиров и при этом может быть связан с другим вагоном.
Таким образом, если в массиве положение элементов определяется индексами, то в связном списке - указателями на следующий и (или) на предыдущий элемент.
Связные списки могут различаться. Есть односвязные списки, в которых каждый узел хранит указатель только на следующий узел. Есть двусвязные списки: в них каждый элемент хранит ссылку как на следующий элемент, так и на предыдущий. Есть кольцевые замкнутые списки. В данном случае мы рассмотрим создание односвязного списка.
Перед созданием списка нам надо определить класс узла, который будет представлять одиночный объект в списке:
public class Node<T>
{
public Node(T data)
{
Data = data;
}
public T Data { get; set; }
public Node<T>? Next { get; set; }
}
Класс Node является обобщенным, поэтому может хранить данные любого типа. Для хранения данных предназначено свойство Data. Для
ссылки на следующий узел определено свойство Next.
Далее определим сам класс списка:
using System.Collections;
using System.Collections.Generic;
public class LinkedList<T> : IEnumerable<T> // односвязный список
{
Node<T>? head; // головной/первый элемент
Node<T>? tail; // последний/хвостовой элемент
int count; // количество элементов в списке
// добавление элемента
public void Add(T data)
{
Node<T> node = new Node<T>(data);
if (head == null)
head = node;
else
tail!.Next = node;
tail = node;
count++;
}
// удаление элемента
public bool Remove(T data)
{
Node<T>? current = head;
Node<T>? previous = null;
while (current != null && current.Data != null)
{
if (current.Data.Equals(data))
{
// Если узел в середине или в конце
if (previous != null)
{
// убираем узел current, теперь previous ссылается не на current, а на current.Next
previous.Next = current.Next;
// Если current.Next не установлен, значит узел последний,
// изменяем переменную tail
if (current.Next == null)
tail = previous;
}
else
{
// если удаляется первый элемент
// переустанавливаем значение head
head = head?.Next;
// если после удаления список пуст, сбрасываем tail
if (head == null)
tail = null;
}
count--;
return true;
}
previous = current;
current = current.Next;
}
return false;
}
public int Count { get { return count; } }
public bool IsEmpty { get { return count == 0; } }
// очистка списка
public void Clear()
{
head = null;
tail = null;
count = 0;
}
// содержит ли список элемент
public bool Contains(T data)
{
Node<T>? current = head;
while (current != null && current.Data !=null)
{
if (current.Data.Equals(data)) return true;
current = current.Next;
}
return false;
}
// добвление в начало
public void AppendFirst(T data)
{
Node<T> node = new Node<T>(data);
node.Next = head;
head = node;
if (count == 0)
tail = head;
count++;
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
Node<T>? current = head;
while (current != null)
{
yield return current.Data;
current = current.Next;
}
}
// реализация интерфейса IEnumerable
IEnumerator IEnumerable.GetEnumerator()
{
return ((IEnumerable<T>)this).GetEnumerator();
}
}
Разберем основные моменты. В зависимости от конкретных задач реализация списков может отличаться, но для всех реализаций характерны прежде всего два метода: добавление и удаление.
Но прежде чем выполнять различные операции с данными, в классе списка определяются три переменные:
Node<T>? head; // головной/первый элемент Node<T>? tail; // последний/хвостовой элемент int count; // количество элементов в списке
Метод добавления:
public void Add(T data)
{
Node<T> node = new Node<T>(data);
if (head == null)
head = node;
else
tail!.Next = node;
tail = node;
count++;
}
Если у нас не установлена переменная head (то есть список пуст), то устанавливаем head и tail. После добавления первого элемента они будут указывать на один и тот же объект.
Если же в списке есть как минимум один элемент, то устанавливаем свойство tail.Next - теперь оно хранит ссылку на новый узел. И переустанавливаем tail - теперь она ссылается на новый узел.
Сложность данного метода составляет O(1). Графически это выглядит так:
Важно отметить наличие переменной tail, которая указывает на последний элемент. Ряд реализаций не используют подобную переменную и добавляют иным образом:
public void AddWithoutTail(T data)
{
Node<T> node = new Node<T>(data);
if (head == null)
{
head = node;
}
else
{
Node<T> current = head;
// ищем последний элемент
while (current.Next!=null)
{
current = current.Next;
}
//устанавливаем последний элемент
current.Next = node;
}
count++;
}
Данный способ вполне рабочий и нередко встречается, однако необходимость перебора элементов для нахождения последнего увеличивает время на поиск и сложность алгоритма. Она равна O(n).
Особняком стоит метод добавления в начало списка, где нам достаточно переустановить ссылку на головной элемент:
public void AppendFirst(T data)
{
Node<T> node = new Node<T>(data);
node.Next = head;
head = node;
if (count == 0)
tail = head;
count++;
}
Удаление элемента
public bool Remove(T data)
{
Node<T>? current = head;
Node<T>? previous = null;
while (current != null && current.Data != null)
{
if (current.Data.Equals(data))
{
// Если узел в середине или в конце
if (previous != null)
{
// убираем узел current, теперь previous ссылается не на current, а на current.Next
previous.Next = current.Next;
// Если current.Next не установлен, значит узел последний,
// изменяем переменную tail
if (current.Next == null)
tail = previous;
}
else
{
// если удаляется первый элемент
// переустанавливаем значение head
head = head?.Next;
// если после удаления список пуст, сбрасываем tail
if (head == null)
tail = null;
}
count--;
return true;
}
previous = current;
current = current.Next;
}
return false;
}
Алгоритм удаления элемента представляет следующую последовательность шагов:
Поиск элемента в списке путем перебора всех элементов
Установка свойства Next у предыдущего узла (по отношению к удаляемому) на следующий узел по отношению к удаляемому.
Для отслеживания предыдущего узла применяется переменная previous. Если элемент найден, и переменная previous равна null, то удаление идет
сначала, и в этом случае происходит переустановка переменной head, то есть головного элемента.
Если же previous не равна null, то реализуются шаги выше описанного алгоритма.
Сложность такого алгоритма составляет O(n). Графически удаление можно представить так:
Чтобы проверить наличие элемента, исползуется метод Contains:
public bool Contains(T data)
{
Node<T>? current = head;
while (current != null && current.Data !=null)
{
if (current.Data.Equals(data))
return true;
current = current.Next;
}
return false;
}
Здесь опять же просто осуществляется перебор. Сложность алгоритма метода составляет O(n).
И для того, чтобы список можно было бы перебрать во внешней прграмме с помощью цикла for-each, класс списка реализует интерфейс IEnumerable:
// реализация интерфейса IEnumerable
IEnumerator IEnumerable.GetEnumerator()
{
return ((IEnumerable<T>)this).GetEnumerator();
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
Node<T>? current = head;
while (current != null)
{
yield return current.Data;
current = current.Next;
}
}
Реализация данного интерфейса не является неотъемлимой частью односвязных списков, однако предоставляет эффективный метод для перебора коллекции в цикле foreach. Иначе нам бы пришлось реализовать какие-то собственные конструкции по перебору списка.
Применение LinkedList:
LinkedList<string> linkedList = new LinkedList<string>
{
// добавление элементов
"Tom",
"Alice",
"Bob",
"Sam"
};
// выводим элементы
foreach (var item in linkedList)
{
Console.WriteLine(item);
}
// удаляем элемент
linkedList.Remove("Alice");
Console.WriteLine("\nПосле удаления Alice");
foreach (var item in linkedList) Console.WriteLine(item);
// проверяем наличие элемента
bool isPresent = linkedList.Contains("Sam");
Console.WriteLine(isPresent ? "Sam присутствует" : "Sam отсутствует");
// добавляем элемент в начало
linkedList.AppendFirst("Bill");
Console.WriteLine("\nПосле добавления Billa");
foreach (var item in linkedList) Console.WriteLine(item);
Консольный вывод:
Tom Alice Bob Sam После удаления Alice Tom Bob Sam Sam присутствует После добавления Billa Bill Tom Bob Sam
- Глава 1. Введение в алгоритмы
- Глава 2. Структуры данных