Статья: Линейный односвязный список

Введение

Под связным списком понимается основная структура данных, которая имеет динамический характер и состоит из узлов. Любой узел состоит из информации и ссылок («связок») на следующие и/или расположенные ранее узлы списка. У связного списка имеется одно очень существенное достоинство по сравнению с массивами и это гибкая структура. Расположение компонентов связного списка не обязательно соответствует их порядковой нумерацией, хранящейся в компьютере, а система прохождения списка определяется в явной форме связями внутри списка.

Линейный односвязный список

Линейным односвязным списком называется организация данных, которые состоят из однотипных компонентов, имеющих последовательные связи друг с другом при помощи указателей. У каждого компонента из списка имеется указатель на последующий компонент. У конечного элемента списка указатель указывает на нуль. Начальным в списке расположен компонент, на который не ссылаются никакие указатели. А указатель каждого узла ведёт на соседний узел списка. Если список односвязный, то движение внутри списка возможно лишь в направлении окончания списка. Выяснить адрес компонента, расположенного ранее, по данным текущего узла, не представляется возможным. В дисциплине информатика под линейным списком понимается абстрактный вид информационных данных, который формализует термин упорядоченных данных в коллекции. Обычно, линейный список можно организовать в виде массива или связного списка. Бывают моменты, когда понятие списка в произвольной трактовке применяется в виде синонима связного списка. Например, абстрактный тип данных нетипичного, с возможностью изменения, списка определяется в виде набора из конструктора алгебраического типа данных и базовых процедур:

1. Процедура, которая проверяет, что список не нулевой.
2. Внесение объекта в список при помощи трёх операций (первым, последним или за любым N-м компонентом из списка.
3. Процедура вычисления начального компонента списка.
4. Процедура организации доступа к списку, который включает все компоненты начального списка, исключая первый.

Основные характеристики линейных односвязных списков

К основным характеристикам линейных односвязных списков относятся:

1. Размеры списка, число компонентов в списке.
2. Списки делятся на типизированные и не типизированные. У типизированных списков задаётся тип его компонентов, и у всех, входящих в список компонентов, предполагается тип, который совместим с определённым заранее типом компонентов списка. В большинстве случаев, списки являются типизированными.
3. Есть списки сортированные и не сортированные.
4. В разных реализациях возможна организация прямого доступа к компонентам списка.

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

typedef struct s_list
{
 int field; // область информации
 struct s_list *next; // указатель на очередной компонент
} list;

использование односвязного списка:

1 list* l1 = (list*)malloc(sizeof(list));
2 l1->field = 1;
3 l1->next = (list*)malloc(sizeof(list));
4 l1->next->field = 2;
5 l1->next->next = (list*)malloc(sizeof(list));
6 /* и так далее */

Одной из модификаций связного списка считается список, который замкнут в кольцо. То есть представляет собой замкнутый цикл. По структуре он бывает односвязный или двусвязный. В конечном компоненте замкнутого списка содержится указание на начальный компонент, в котором, в свою очередь, при двусвязном списке может быть указатель на конечный компонент. Обычно, такое построение основывается на линейном списке, в котором не должно быть ссылок на нуль. Есть ещё списки в виде цикла, где выделяется головной элемент. Это значительно облегчает полное прохождение списка.

Преимущества и недостатки линейного односвязного списка

Можно отметить следующие основные преимущества:

1. Удалить или добавить элемент возможно очень быстро и без проблем.
2. Длина списка ограничивается лишь возможностями памяти компьютера и количеством разрядов, отведённых указателям списка.
3. Существует возможность динамического удаления и прибавления компонентов.

Основные проблемные моменты связного списка определяются их основным свойством, а именно последовательным доступом к информационным данным:

1. Достаточно сложно получить прямой доступ к компоненту, то есть определить физический адрес на основании его индекса в списке.
2. На задание указателей на следующие и предыдущие компоненты нужно выделять дополнительные объёмы памяти. А, к примеру, в массиве формирование указателей не требуется.
3. Отдельные процедуры со списком выполняются не так быстро, как при использовании массива, поскольку к выбранному компоненту возможно обращение только после прохождения всех элементов, расположенных до него.
4. Возможно не локальное распределение в памяти компьютера двух соседних элементов в списке, что мешает оптимальному кэшированию информационных данных в компьютере.
5. Затруднено выполнение векторных операций над связным списком, если сравнивать с массивом, таких как определение суммарного результата. Наличие затрат на выполнение перебора компонентов понижает эффект от распараллеливания.

Добавление узла в односвязный линейный список

Операция формирования нового узла в списке имеет два аргумента:

1. Формирование указателя на узел, за которым выполняется добавление.
2. Информационные данные, которые принадлежат узлу.

Блок-схема формирования нового узла представлена в следующем виде:

Рисунок 1. Блок-схема формирования нового узла.

Процесс добавления узла в линейный односвязный список состоит из следующих этапов:

1. Формирование добавляемого узла и внесение в него необходимых данных.
2. Переназначение в узле, стоящем перед добавляемым, указателя на новый узел.
3. Запись в указатель нового узла направления на узел, стоящий далее (который был в указателе предшествующего узла).