Линейный односвязный список является самым простым видом связных списков. Такой список можно определить с помощью описаний типов (см. пример 1).
Процедуры работы с линейным односвязным списком на языке Паскаль
Type
rel1=^elem; (* Указатель на запись *)
elem=record
next:rel1;
data:<Тип хранимых данных> (* Любой допустимый тип данных *)
end;
var
L1:rel1;
Для того, чтобы такие операции, как добавление или удаление звена, выполнялись одинаково, независимо от места их выполнения в списке, удобно использовать ведущее или заглавное звено - самое первое звено списка, в котором не обязаны храниться полезные данные. Его создание для односвязного списка можно осуществить следующим образом:
var a, L1:list1;
begin
...
new(L1);
L1^.next:=nil;
a:=L1;
...
Указатель на начало списка L1, значением которого является адрес ведущего звена, представляет список как единый программный объект.
Указатель на следующий элемент в последнем звене списка имеет значение nil (NULL или просто 0 в Си/Си++), что является признаком линейного списка.
procedure insert1(link:rel1;info:<Тип>);
var q:rel1;
begin
new(q);
q^.data:=info;
q^.next:=link^.next;
link^.next:=q
end;
procedure delete1(link:rel1);
var q:rel1;
begin
if link^.next<>nil then
begin
q:=link^.next;
link^.next:=link^.next^.next;
dispose(q);
end
end;
function search1(l:rel1;info:<Тип>;var r:rel1):boolean;
var q:rel1;
begin
search1:=false;
r:=nil;
q:=l^.next;
while (q<>nil) and (r<>nil) do
begin
if q^.data=info then
begin
search:=true;
r:=q
end;
q:=q^.next
end
end;
Процедуры добавления и удаления звеньев являются критическими с точки зрения сохранения целостности списка. При неправильном выполнении этих процедур (т.е. при неправильной очерёдности выполнения операций присваивания) возможны 2 ошибочные ситуации:
1. Список "рвётся" по месту вставки или удаления звена, и звено, оказавшее последним, замыкается либо само на себя (чаще всего) (т.е. указатель next или аналогичный ему в этом звене получает значение адреса этого же звена), либо на одно из предшествующих звеньев (в зависимости от неправильной реализации операций вставки или удаления звена). При попытке просмотра списка процедура просмотра зацикливается и бесконечно выводит содержимое одного и того же звена (или нескольких звеньев).
2. Список так же "рвётся" по месту вставки или удаления звена, но указатель в звене, ставшем последним, получает какое-то произвольное значение, которое трактуется как адрес следующего звена (реально не существующего), у которого также есть указатель next, содержащий какой-то адрес, и так далее, до тех пор, пока случайно не попадётся блок данных, для которого указатель next не будет равен нулю. При попытке просмотра списка на дисплей сначала выводятся правильные данные, а затем случайный набор символов.
В обоих случаях к звеньям в "оторвавшейся" части ("хвосте") списка больше нет доступа, и хранящиеся в них данные можно считать потерянными.
Для предотвращения возникновения таких ошибок следует соблюдать правильный порядок проведения связей (т.е. присваивания указателей) при вставке нового звена и удалении существующего (очерёдность операций указана):
Добавление звена в произвольную позицию за ведущим звеном:
struct Link1
{
int data;
Link1* next;
};
void Insert1(Link1* link,int data) // link - звено, за которым вставляется новое
{
Link1* q=new Link1; // 1 Выделение памяти под новое звено
q->data=data; // 2 Ввод данных
q->next=link->next; // 3 Проведение связи от нового звена к следующему
link->next=q; // 4 Проведение связи от "старого" звена у новому
}
Возможность перемещаться по 1-связному списку только в одном направлении приводит к тому, что при удалении звена приходится задавать не реально удаляемое звено, а предшествующее ему. Это делается для того, чтобы можно было скорректировать связь для предшествующего звена, добраться до которого от удаляемого иначе невозможно.
Удаление звена из любого места списка за ведущим звеном:
void Delete1(Link1* link) // link - звено, предшествующее удаляемому
{
Link1* q;
if(link->next) // Проверка на наличие звена, следующего за link
{
q=link->next; // 1 Запоминание удаляемого звена для операции delete
link->next=q->next; // 2 Проведение новой связи в обход удаляемого звена
delete q; // 3 Очистка памяти
}
}
Одной из наиболее простых операций со всеми типами списков является их прохождение, т.е. поочерёдное получение доступа ко всем элементам. Приведём процедуру, реализующую эту операцию для просмотра списка (другие варианты использования прохождения - поиск данных и сохранение списка в файл). В случае перемещения по 2-связному списку в "прямом" направлении эта процедура является одинаковой для 1- и 2-связного линейных списков.
Просмотр 1-связного линейного списка
void Show(Link1* link)
{
Link1 *q=link->next; // Учитывается наличие "пустого" ведущего звена
while(q) // или while(q!=NULL)
{
cout<<q->data<<' '; // или другая операция
q=q->next; // Переход по списку
}
cout<<endl;
}
Поиск в списке является вариантом операции просмотра и отличается тем, что:
1. вместо операции вывода на экран (cout<<q->data) используется операция сравнения искомых данных с хранящимися в звеньях списка;
2. если искомые данные найдены, нет необходимости перемещаться по списку дальше.
Поиск в односвязных списках имеет следующую особенность. Если он выполняется в сочетании с удалением, то результатом поиска может (или должно) быть не то звено, в котором содержатся искомые данные, а предшествующее ему. В итоге для поиска в списке могут потребоваться либо две различные процедуры - "обычная" и находящая предыдущее звено, либо одна универсальная, позволяющая найти оба звена - с искомыми данными и предшествующее ему. Рассмотрим в качестве примера именно этот вариант
Универсальная процедура поиска (находит звено с ключом поиска и предшествующее ему)
int Search(Link1* Start, // Точка начала поиска
Link1*& Find, // Указатель для звена с искомыми данными
Link1*& Pred, // Указатель для предыдущего звена
int Key) // Ключ поиска
{
Link1* Cur=Start->next; // Текущее звено
Pred=Start; // Предыдущее звено ("отстаёт" на 1 шаг от текущего)
int Success=0; // Признак успеха поиска (установлен в 0)
while(Cur && !Success) // Операция логическое "И"
{
if(Cur->data == Key) // нашли
{
Find=Cur; // Запоминание найденного звена
Success=1; // Установка в 1 признака успеха
break; // Выход из цикла при удачном поиске
}
Pred=Cur; // Перемещение предыдущего звена
Cur=Cur->next; // Переход по списку вперёд
}
return Success;
}
Следует отметить, что возможны разные (в том числе более короткие) варианты реализации такого алгоритма, например, без переменной Success (вместо неё используется указатель Find, который до начала поиска должен получить значение NULL и сохранить его при неудачном поиске).
Процедура, которая находит только искомое звено, является более простой, - в ней не нужен указатель Pred и все операторы, в которых он используется.
Похожая процедура применяется для 1-связного кольцевого списка. Отличие её от рассмотренного примера заключается в условии продолжения цикла в операторе while:
while(Cur!=Start && !Success) // Для кольцевого списка
Ведущее (или заглавное) звено. Все приведённые выше примеры на языке Си++ подразумевают наличие в списке ведущего звена. Создаваться это звено может либо отдельной процедурой, либо следующим набором операторов (эти же операторы и будут находиться в процедуре):
Link1 *L1 = new Link1; // Выделение памяти под звено
L1->next = NULL; // Ведущее звено одновременно является последним
Возможна работа со связным списком и без выделенного ведущего звена, т.е. первое звено является обычным, в нём содержатся полезные данные. Именно такой вид списка использовался для организации стека. Ещё один пример использования подобных списков - очередь.
Занесение в очередь и извлечение из очереди, построенной на основе 2-связного списка
void queue_in(Link2*& q, // "Голова" очереди
Link2*& e, // "Хвост" очереди
int k) // Вводимые данные
{
Link2* n=new node; // Новый узел
n->data=k;
n->next=q;
if(q)
q->prev=n;
else
e=n;
n->prev=0;
q=n;
}
int queue_out(Link2*& q, Link2*& e)
{
int k=e->data;
Link2* d=e;
e=d->prev;
if(e)
e->next=0;
else
q=e;
delete d;
return k;
}
Для упрощения обработки "головы" и "хвоста" очереди использован 2-связный список.
В остальных случаях (т.е. для обычных списков) использование ведущего звена является предпочтительным, т.к. позволяет избежать проверок при добавлении и удалении звеньев.
Недостатки односвязного списка заключаются в следующем:
1. По такому списку можно перемещаться только от начального звена к конечному. Начинать можно с любого звена в списке, но если вдруг возникнет необходимость обратиться к предшествующим элементам, придется начинать с начального звена, что неудобно, нерационально и усложняет алгоритмы обработки данных.
2. Наличие только одной связи снижает надёжность хранения данных в 1-связном списке.
3. Следствием первого недостатка является усложнение взаимодействия операций поиска и удаления.
Достоинствами этого списка являются меньший расход памяти по сравнению с другими связными динамическими структурами данных (всего 1 указатель) и простота операций.
