Линейный однонаправленный список

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

Рисунок 2. Линейный однонаправленный список

Основные операции, осуществляемые с линейным однонаправленным списком:

• вставка элемента;

• просмотр;

• поиск;

• удаление элемента.

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

Для описания алгоритмов этих основных операций используем следующие объявления:

type

PElement = ^TypeElement; {указатель на тип элемента}

TypeElement = record {тип элемента списка}

Data: TypeData; {поле данных элемента}

Next: PElement; {поле указателя на следующий элемент}

end;

var

ptrHead: PElement; {указатель на первый элемент списка}

ptrCurrent: PElement; {указатель на текущий элемент}

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

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

procedure Ins_LineSingleList(DataElem: TypeData;

var ptrHead, ptrCurrent: PElement);

{Вставка непервого элемента в линейный однонаправленный список}

{справа от элемента, на который указывает ptrCurrent}

var

ptrAddition: PElement; {вспомогательный указатель}

begin

New(ptrAddition);

ptrAddition^.Data := DataElem;

if ptrHead = nil then begin {список пуст}

{создаем первый элемент списка}

ptrAddition^.Next := nil;

ptrHead := ptrAddition;

end else begin {список не пуст}

{вставляем элемент списка справа от элемента,}

{на который указывает ptrCurrent}

ptrAddition^.Next := ptrCurrent^.Next;

ptrCurrent^.Next := ptrAddition;

end;

ptrCurrent := ptrAddition;

end;

procedure InsFirst_LineSingleList(DataElem: TypeData;

var ptrHead: PElement);

{Вставка первого элемента в линейный однонаправленный список}

var

ptrAddition: PElement; {вспомогательный указатель}

begin

New(ptrAddition);

ptrAddition^.Data := DataElem;

if ptrHead = nil then begin {список пуст}

{создаем первый элемент списка}

ptrAddition^.Next := nil;

end else begin {список не пуст}

{вставляем новый элемент слева (перед) первым элементом}

ptrAddition^.Next := ptrHead;

end;

ptrHead := ptrAddition;

end;

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

Операция просмотра списка заключается в последовательном просмотре всех элементов списка.

procedure Scan_LineSingleList(ptrHead: PElement);

{Просмотр линейного однонаправленного списка}

var

ptrAddition: PElement; {вспомогательный указатель}

begin

ptrAddition := ptrHead;

while ptrAddition <> nil do begin {пока не конец списка}

writeln(ptrAddition^.Data); {Вывод значения элемента}

ptrAddition := ptrAddition^.Next;

end;

end;

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

function Find_LineSingleList(DataElem: TypeData;

var ptrHead, ptrCurrent: PElement): boolean;

{Поиск элемента в линейном однонаправленном списке}

var

ptrAddition:PElement; {Дополнительный указатель}

begin

if (ptrHead <> nil)then begin {Если существует список}

ptrAddition := ptrHead;

while (ptrAddition <> nil) and

(ptrAddition^.Data <> DataElem) do

{пока не конец списка и не найден элемент}

ptrAddition := ptrAddition^.Next;

{Если элемент найден,

то результатом работы функции является - true}

if ptrAddition <> nil then begin

Find_LineSingleList := true;

ptrCurrent := ptrAddition;

end else begin

Find_LineSingleList := false;

end;

end else begin

Find_LineSingleList:=false;

end;

end;

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

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

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

procedure Del_LineSingleList(var ptrHead,

ptrCurrent: PElement);

{Удаление элемента из линейного однонаправленного списка}

var

ptrAddition: PElement; {вспомогательный указатель}

begin

if ptrCurrent <> nil then begin {вх.параметр корректен}

if ptrCurrent = ptrHead then begin {удаляем первый}

ptrHead := ptrHead^.Next;

dispose(ptrCurrent);

ptrCurrent := ptrHead;

end else begin {удаляем не первый}

{устанавливаем вспомогательный указатель на элемент,

предшествующий удаляемому}

ptrAddition := ptrHead;

while ptrAddition^.Next <> ptrCurrent do

ptrAddition := ptrAddition^.Next;

{непосредственное удаление элемента}

ptrAddition^.Next := ptrCurrent^.Next;

dispose(ptrCurrent);

ptrCurrent := ptrAddition;

end;

end;

end;

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

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