Линейный двусвязный (двунаправленный) список

Линейный односвязный (однонаправленный) список

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

1. Объявление (описание) данных односвязного списка:

type

p_elem = ^element;

element = record

data: string[15];

next: p_elem;

end;

var

head, current, last : p_elem;

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

В описании переменных описаны:

указатели head – указатель на заголовок списка,

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

2. Создание первого элемента списка и заполнение полей:

new(current);

current^.data:= ’данные в первом элементе списка ’;

current^.next:=nil;

Поле current^.next является указателем, доступ к его содержимому осуществляется через указатель current.

3. Создание следующего элемента и связывание его с первым элементом:

head:=current;

new(last);

last^.data:= ’данные во втором элементе списка ’;

last^.next:=nil;

current^.next:=last;

Перед созданием следующего элемента указателю head присваивается значение указателя current для того, чтобы сохранить адрес начала линейного списка (указатель на первый элемент списка является заголовком). Если этого не сделать, то когда значение указателя current будет переопределено, то потеряется возможность доступа к данным, хранящимся в первом элементе списка.

4. Создание списка из n элементов:

head:= nil;

for i:=1 to n do

begin

new(current);

readln(current^.data);

current^.next:=nil;

if head=nil then

head:=current

else

last^.next:= current;

last:= current;

end;

5. Удаление элемента списка:

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

dispose(current);

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

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

1. Объявление данных двусвязного списка:

type

listPtr = ^list;

list = record

number, data: integer;

next, prev: listPtr;

end;

В данном случае number – поле для хранения порядкового номера элемента, data – поле для хранения данных элемента, prev и next – указатели на предыдущий и последующий элемент соответственно.