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

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

Существует два основных способа построения односвязного списка. Первый способ – помещать новые элементы в конец списка. Второй – вставлять элементы в определенные позиции списка, например, в порядке возрастания. От способа построения списка зависит алгоритм функции добавления элемента.

Для создания динамического списка необходимо определить структуру, которая помимо информационных полей будет содержать поле указатель на объявленную структуру.

Пример:

struct sp

{

int x;

sp *next;

};

Принцип построения динамического списка по первому способу: во-первых, необходимо объявить указатель, который называется головным указателем. Если значение головного указателя равно null, это означает, что список пуст. Добавление нового элемента происходит в конец списка.

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

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

Следует помнить, что при вставке элемента в начало списка необходимо изменить адрес входа в список где-то в другом месте программы.

Удаление элемента из односвязного списка выполняется просто. Так же как и при вставке, возможны три случая: удаление первого элемента, удаление элемента в середине, удаление последнего элемента.