В односвязном списке каждый элемент информации содержит ссылку на следующий элемент списка. Каждый элемент данных обычно представляет собой структуру, которая состоит из информационных полей и указателя связи. Концептуально односвязный список выглядит, как показано на рисунке 1.
Существует два основных способа построения односвязного списка. Первый способ – помещать новые элементы в конец списка. Второй – вставлять элементы в определенные позиции списка, например, в порядке возрастания. От способа построения списка зависит алгоритм функции добавления элемента.
Для создания динамического списка необходимо определить структуру, которая помимо информационных полей будет содержать поле указатель на объявленную структуру.
Пример:
struct sp
{
int x;
sp *next;
};
Принцип построения динамического списка по первому способу: во-первых, необходимо объявить указатель, который называется головным указателем. Если значение головного указателя равно null, это означает, что список пуст. Добавление нового элемента происходит в конец списка.
Полученный список можно отсортировать отдельной операцией уже после его создания, но легче сразу создавать упорядоченный список, вставляя новый элемент в нужное место в последовательности. Кроме того, если список уже отсортирован, имеет смысл поддерживать его упорядоченность, вставляя новые элементы в соответствующие позиции. Для вставки элемента таким способом требуется последовательно просматривать список до тех пор, пока не будет найдено место нового элемента, затем вставить в найденную позицию новую запись и переустановить ссылки.
При вставке элемента в односвязный список может возникнуть одна их трех ситуаций: элемент становится первым, элемент вставляется между двумя другими, элемент становится последним.
Следует помнить, что при вставке элемента в начало списка необходимо изменить адрес входа в список где-то в другом месте программы.
Удаление элемента из односвязного списка выполняется просто. Так же как и при вставке, возможны три случая: удаление первого элемента, удаление элемента в середине, удаление последнего элемента.