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

Список – это структура данных, представляющая собой логически связанную последовательность элементов списка. В связанном списке (или просто списке; по-английски linked list) элементы линейно упорядочены, но порядок определяется не номерами, как в массиве, а указателями, входящими в состав элементов списка. Списки являются удобным способом хранения динамических множеств, позволяющим реализовать все опе­рации, перечисленные во введении к этой части (хотя и не всегда эффективно).

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

Рисунок 3.1 – Линейный односвязный список

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

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

– просмотр;

– поиск;

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

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

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

type

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

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

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

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

end;

var

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

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

Вставка первого и последующих элементов списка отличаются друг от друга. Поэтому приводится два алгоритма вставки, оформленных в виде процедур языка Pascal: 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;

Листинг 3.1 – Процедуры добавления элемента в односвязный список (в хвост и голову)

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

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

procedure Scan_LineSingleList(ptrHead: PElement);

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

var

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

begin

ptrAddition := ptrHead;

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

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

ptrAddition := ptrAddition^.Next;

end;

end;

Листинг 3.2 – Процедура просмотра односвязного списка

Операция поиска элемента в списке заключается в последовательном просмотре всех элементов списка до тех пор, пока текущий элемент не будет содержать заданное значение или пока не будет достигнут конец списка. В последнем случае фиксируется отсутствие искомого элемента в списке (функция принимает значение 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;

Листинг 3.2 – Процедуры добавления элемента в односвязный список (в хвост и голову)

Ниже представлен псевдокод процедуры List-Search(L, k), которая находит в списке L (с помощью простого ли­нейного поиска) первый элемент, имеющий ключ k. Точнее говоря, она возвра­щает указатель на этот элемент или NIL, если элемента с таким ключом в списке нет.

Листинг 3.3 – Линейный поиск элемента в списке

Поиск в списке из n элементов требует в худшем случае (когда приходится просматривать весь список) Θ(n) операций.

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

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

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

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;

Листинг 3.4 – Линейный поиск элемента в списке

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

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