Структуры данных

Связный список

Двусвязные списки

Стек на основе массива

Стек

Очередь

Дек

Кольцевой односвязный список

Кольцевой двусвязный список


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

Односвязный список в C#

Таким образом, если в массиве положение элементов определяется индексами, то в связном списке — указателями на следующий и (или) на предыдущий элемент.

Связные списки могут различаться. Есть односвязные списки, в которых каждый узел хранит указатель только на следующий узел. Есть двусвязные списки: в них каждый элемент хранит ссылку как на следующий элемент, так и на предыдущий. Есть кольцевые замкнутые списки. В данном случае мы рассмотрим создание односвязного списка.


Двусвязные списки также представляют последовательность связанных узлов, однако теперь каждый узел хранит ссылку на следующий и на предыдущий элементы.

Двусвязный список в C#

Двунаправленность списка приходится учитывать при добавлении или удалении элемента, так как кроме ссылки на следующий элемент надо устанавливать и ссылку на предыдущий. Но в то же время у нас появляется возможность обходить список как от первого к последнему элементу, так и наоборот — от последнего к первому элементу. В остальном двусвязный список ни чем не будет отличаться от односвязного списка.

https://metanit.com/sharp/algoritm/2.2.php


Стек на основе массива представляет собой структуру данных, которая работает по принципу LIFO (Last In First Out — «последний пришел — первый вышел»). Графически стек можно представить в виде столбика или стопки объектов:

Структура стек в C# и .NET

Стек имеет вершину, который образует последний добавленный элемент. При добавлении новый элемент помещается поверх вершины стека и образует новую вершину. При удалении удаляется элемент из вершины стека, а предыдущий элемент образует новую вершину.

Так, на приведенном рисунке вначале вершиной стека является «Tom». После добавления нового элемента «Bob» этот элемент располагается поверх элемента «Tom» и становится новой вершиной.

В библиотеке классов .NET в принципе уже есть свой класс, который выполняет роль стека. Это класс — System.Collections.Generic.Stack. Но рассмотрим, как мы сами можем реализовать структуру в виде стека.

Структура стек вне зависимости от языка программирования обладает неким общим функционалом, который составляют метод добавления элемента (как правило, называется push()) и метод извлечения элемента из вершины стека (обычно называется pop()). Кроме того, нередко реализации стеков содержат метод получения элемента из вершины без его извлечения, метод определения размера стека и ряд других.

https://metanit.com/sharp/algoritm/2.3.php


Стек. В прошлой теме была реализована структура Стек на основе массивов. Однако в подобной структуре мы сталкиваемся с необходимостью динамически изменять размер массива, выделяя для него новую память, или, наоборот, уменьшая ее. Альтернативой является создание стека на основе односвязного списка. Структура «Односвязный список» является простой и понятной и в то же время достаточно эффективной для создания других структур данных.

https://metanit.com/sharp/algoritm/2.4.php


Очередь (queue) — это структура данных, которая работает по принципу FIFO (First In First Out — Первый пришел, первый вышел). При добавлении новый элемент помещается в конец очереди или ее хвост, а удаление идет с начала очереди или головы очереди.

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

https://metanit.com/sharp/algoritm/2.5.php


Дек (deque) представляет двустороннюю очередь, в которой элементы можно добавлять как в начало, так и в конец. Удаление также может идти как с начала, так и с конца.

Поскольку реализовать добавление и удаление нужно с двух сторон, то за основу реализации можно взять организацию двусвязного список.

https://metanit.com/sharp/algoritm/2.6.php


Кольцевые (круговые, циклические) списки являются разновидностью связных списков. Они могут быть односвязными или двусвязными. Их отличительной особенностью является то, что условной последний элемент хранит ссылку на первый элемент, поэтому список получается замкнутым или кольцевым.

Кольцевой список в C#

https://metanit.com/sharp/algoritm/2.7.php


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

Каждый узел такого списка опять же будет представлять элемент, который хранит указатели на следующий и предыдущий узлы

https://metanit.com/sharp/algoritm/2.8.php

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *