Реализация списков

Класс LinkedList<T> представляет собой двухсвязный список, в котором каждый элемент ссылается на следующий и предыдущий.

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

При этом только ссылки Next (следующий) предыдущего элемента и Previous (предыдущий) следующего элемента должны быть изменены так, чтобы указывать на вставляемый элемент.

В классе List<T> при вставке нового элемента все последующие должны быть сдвинуты.

Недостатки связных списков:

· все элементы связных списков доступны лишь друг за другом.

· Для нахождения элемента, находящегося в середине или конце списка, требуется довольно много времени.

· Связный список не может просто хранить элементы внутри себя. Вместе с каждым из них ему необходимо иметь информацию о следующем и предыдущем элементах.

Вот почему LinkedList<T> содержит элементы типа LinkedListNode<T>.

С помощью класса LinkedListNode<T> появляется возможность обратиться к предыдущему и последующему элементам списка.

класс LinkedList<T> определяет члены для доступа к первому (First) и последнему (Last) элементам в списке, для вставки элементов в определенные позиции и для удаления элементов из заданных позиций, для нахождения элементов, начиная поиск либо с начала, либо с конца списка.

В классе LinkedList<T> определяются два приведенных ниже открытых конструктора:

public LinkedList()

public LinkedList(IEnumerable<T> collection)

В первом конструкторе создается пустой связный список, а во втором конструкторе — список, инициализируемый элементами из коллекции collection.

Наиболее часто используемые методы, определенные в классе LinkedList<T>:

AddAfter() Добавляет в список узел со значением непосредственно после указанного узла. Указываемый узел не должен быть пустым (null). Метод возвращает ссылку на узел, содержащий значение.

AddBefore() Добавляет в список узел со значением value непосредственно перед указанным узлом. Указываемый узел не должен быть пустым (null). Метод возвращает ссылку на узел, содержащий значение.

AddFirst(), AddLast() Добавляют узел со значением в начало или в конец списка.

Find() Возвращает ссылку на первый узел в списке, имеющий передаваемое значение. Если искомое значение отсутствует в списке, то возвращается пустое значение.

Remove() Удаляет из списка первый узел, содержащий передаваемое значение. Возвращает логическое значение true, если узел удален, т.е. если узел со значением обнаружен в списке и удален; в противном случае возвращает логическое значение false.

использования связных списков:

using System;

using System.Collections.Generic;

namespace ConsoleApplication1

{

class Program

{

static void Main()

{

// Создадим связный список

LinkedList<string> link = new LinkedList<string>();

// Добавим несколько элементов

link.AddFirst("Квадрат");

link.AddFirst("Круг");

link.AddFirst("Треугольник");

link.AddFirst("ромб");

// Отобразим элементы в прямом направлении

LinkedListNode<string> node;

Console.WriteLine("Элементы коллекции в прямом направлении: ");

for (node = link.First; node!= null; node = node.Next)

Console.Write(node.Value + "\t");

// Отобразить элементы в обратном направлении

Console.WriteLine("\n\nЭлементы коллекции в обратном направлении: ");

for (node = link.Last; node!= null; node = node.Previous)

Console.Write(node.Value + "\t");

Console.ReadLine();

}

}

}

Сортированный список:

класс SortedList<TKey, TValue>

В классе SortedList<TKey, TValue> предоставляется немало конструкторов. Ниже перечислены наиболее часто используемые конструкторы этого класса:

public SortedList() создается пустой список с выбираемой по умолчанию первоначальной емкостью.

public SortedList(IDictionary<TKey, TValue> dictionary) создается отсортированный список с указанным количеством элементов dictionary

public SortedList(int capacity)создается с помощью параметра capacity задается емкость коллекции, создаваемой в виде отсортированного списка. Если размер списка заранее известен, то, указав емкость создаваемой коллекции, можно исключить изменение размера списка во время выполнения, что, как правило, требует дополнительных затрат вычислительных ресурсов

public SortedList(IComparer<TK> comparer) допускается указывать с помощью параметра comparer способ сравнения объектов, содержащихся в списке.

Емкость коллекции типа SortedList<TKey, TValue> увеличивается автоматически по мере необходимости, когда в список добавляются новые элементы.

Если текущая емкость коллекции превышается, то она увеличивается. Преимущество указания емкости коллекции типа SortedList<TKey, TValue> при ее создании заключается в снижении или полном исключении издержек на изменение размера коллекции. Разумеется, указывать емкость коллекции целесообразно лишь в том случае, если заранее известно, сколько элементов требуется хранить в ней.

В классе SortedList<TKey, TValue > определяется ряд собственных методов, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются.

наиболее часто используемых методов этого класса: