Структуры данных C#.

В C#.NET есть много различных структур данных, например Array - одна из самых часто используемых. Однако C# поставляется с гораздо большим количеством таких структур. Необходимо выбирать правильные структуры данных для написания хорошо структурированных и эффективных программ.

В этой статье я перечислю встроенные в C# структуры данных, включая новые из C#.Net 3.5.

Array.

Возможно самым простой и известной структурой данных является array. В C# array является простым массивом объектов. Для него характерно то, что все его объекты одного типа и их количество фиксировано. Он объявляется и инициализируется следующим образом:

[object type][] myArray = new [object type][number of elements]

Некоторые примеры:

int[] myIntArray = new int[5];
int[] myIntArray2 = { 0, 1, 2, 3, 4 };

Как можно видеть из приведенного выше примера, массив может инициализироваться пустым или с уже заданными элементами.

ArrayList.

ArrayList - это динамический массив. Он может иметь любое количество объектов любого типа.

Ниже приведён пример, где ArrayList - массив произвольных объектов, расширяющийся по мере добавления в него новых элементов.

ArrayList myArrayList = new ArrayList();
myArrayList.Add(56);
myArrayList.Add("String");
myArrayList.Add(new Form());

Недостатком ArrayList является необходимость распаковки его элементов в их оригинальный тип:

int arrayListValue = (int)myArrayList[0];

List<> (список).

Вкратце, структура данных List<> - это строго типизированный ArrayList. Это тоже динамический массив, но его отличие от ArrayList в том, что List<> должен содержать данные только одного типа:

List intList = new List();
intList.Add(45);
intList.Add(34);

Поскольку элементы List<> относятся к одному типу их нет необходимости распаковывать при получении:

int listValue = intList[0];

Для простых типов данных (int, bool, итд.) использование List<> обеспечивает гораздо большую скорость работы, нежели использование ArrayList.

LinkedList<> (двусвязный список).

Теперь совершенно другой тип структуры данных - LinkedList<>. LinkedList<> - это группа объектов, которые вместо того, чтобы индексироваться по ссылке (как, например, Array), расположены в узлах и соединены друг с другом.

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

Какой смысл в такой структуре данных? Её преимущество в том, что добавление элемента в середину списка происходит значительно быстрее, чем в другом типе структуры данных. LinkedList<> также снижает затраты памяти до минимума. С другой стороны, для нахождения элемента, находящегося в середине или в конце списка, требуется довольно много времени.

LinkedList list = newLinkedList();
list.AddLast(6);

Получение значения производится не напрямую, а перебором:

list.First.Value

или

list.Last.Value

Теперь мы можем перейти к более сложным структурам данных.

Dictionary<> (словарь).

Структура данных Dictionary<> очень удобна, она позволяет программисту обращаться к значению по её ключевому индексу. Что это значит? ArrayList, к примеру, автоматически создаёт свои "ключи" - числа, 1, 2 и т.д., так, что для доступа к необходимому объекту используется следующая запись:

myArrayList[2];

Dictionary<> позволяет использовать ключи любого типа, например:

Dictionary myDictionary = new Dictionary();
myDictionary.Add("one", 1);
myDictionary.Add("twenty", 20);

Получение значения производится следующим образом:

int myInt = myDictionary["one"];

При использовании Dictionary<> нет необходимости метаться между типами. Также никто не запрещает создать Dictionary<> таким образом:

Dictionary> nestedDictionary = 
            new Dictionary>();

То есть вложенные структуры данных Dictionary<> возможны и разрешены.

Я понимаю, что может ввести в заблуждение то, как получить все значения из этой структуры данных, поскольку мы можем не знать закономерности в составлении её ключей. К счастью, это не обязательно, вот пример получения всех данных из Dictionary<>:

//List<[same type as index]>
List keyList = new List(myDictionary.Keys);
for (int i = 0; i < keyList.Count; i++)
{
    int myInt = myDictionary[keyList[i]];
}

Если вы заинтересованы, вы можете прочитать более подробно о C# Dictionary<>.

Hashtable (хеш-таблица).

Структура данных Hashtable очень похожа на структуру Dictionary<>. Hashtable также принимает пару ключ/значение, но они должны быть объектными ссылками - ссылкой на ключ и ссылкой на сам объект. С приходом .NET 2.0 обобщённые словари вроде Dictionary<> стали более предпочтительнее, по сравнению со словарями, основанными на типе Object.
Значения в хеш-таблице хранится в порядке, зависящем от хэш-кода их ключа.

Hashtable myTable = new Hashtable();

HashSet<>.

Структура данных HashSet<> была введена в C# Net 3.5. Эта специфическая структура данных очень сильно напоминает List<>. В чём же различие? У HashSet<> есть очень важная особенность - она не допускает повторяющихся значений. Например:

HashSet mySet = new HashSet();
mySet.Add(3);
mySet.Add(5);
mySet.Add(3);
mySet.Add(10);

List myListFromSet = mySet.ToList();
int myInt = myListFromSet[2];

Если mySet был бы обычной структурой данных List<>, то индекс 2 должен был вернуть значение 3 (проверьте сами). Но если вы запустите пример, вы увидите, что myInt возвращает значение 10. Это происходит потому, что HashSet<> игнорирует дубликат со значением 3.
Для более подробного изучения вы можете посетить страницу C# HashSet<>.

Stack и Stack<>(стек).

Класс Stack является одним из многих структур данных в C#, которые напоминают ArrayList. Как и ArrayList, стек имеет методы для добавления и получения данных, но с небольшой разницей в их поведении.
Чтобы добавить в стек данные, необходимо использовать метод Push, который является эквивалентом Add в ArrayList. Получение значения немного отличается. Стек имеет метод Pop, который возвращает и одновременно удаляет последний добавленный объект. Если вы хотите получить последнее значение в стеке без его удаления, используйте метод Peek.
Стек работает по алгоритму LIFO, что расшифровывается как Last-In-First-Out (последним пришёл - первым обслужен). Эта специфическая структура данных будет полезна, если вам необходимо вернуться той же дорогой, так сказать.
Есть два вида объявления стека в C#:

Stack stack = new Stack();
Stack stack = new Stack();

Различия в них в том, что первая структура данных будет работать с производными от класса Object, тогда как вторая принимает только определённый тип данных.
Вот код C#, для добавления и извлечения данных из стека:

Stack stack = new Stack();
stack.Push("1");
stack.Push("2");
stack.Push("3");

while (stack.Count > 0)
{
    MessageBox.Show(stack.Pop());
}

Если запустить этот код, то увидите, что список возвращён в следующем порядке: 3, 2, 1.

Queue и Queue<>(очередь).

Очередь - ещё одна из многих структур данных в C#. Очередь очень похожа на стек, но есть одно важное отличие. Вместо того, чтобы следовать алгоритму LIFO, очередь следует алгоритму FIFO, что расшифровывается как First-In-First-Out (первый пришёл - первый обслужен). К примеру, когда вы отправляете статью для утверждения на сайт, то там она добавляется в очередь на утверждение. Таким образом, объекты, добавленные первыми, первыми будут и обработаны.
Добавление элемента в очередь (аналогичено Push для стека) осуществляется методом Enqueue:

queue.Enqueue("1");

Извлечение элемента - методом Dequeue:

queue.Dequeue();

Аналогично, метод Peek позволяет просмотреть верхнее значение в очереди, не удаляя его. Эта специфическая структура данных очень часто используется в связке со стеком.
Вот простой код для добавления и извлечения данных из очереди:

Queue queue = new Queue();
queue.Enqueue("1");
queue.Enqueue("2");
queue.Enqueue("3");

while (queue.Count > 0)
{
   MessageBox.Show(queue.Dequeue());
}

Также имейте ввиду, что очередь, как и стек, может быть определена как любого типа данных (Queue), так и только для одного типа (Queue<>).