Двунаправленные связанные списки

Каждый элемент двунаправленного связанного списка имеет два указателя

(рис. 2.3) [8, И]:

• один указатель установлен на предшествующий элемент;

• другой указатель установлен на следующий элемент. Двунаправленный список может быть линейным и циклическим (рис. 2.4). Над линейными двунаправленными списками могут выполняться

следующие операции [8]:

• получение доступа к k-шу узлу для проверки или изменения содержимого его полей;

• вставка нового узла сразу после или до k-то узла;

• удаление k-то узла;

• объединение нескольких списков в один;

• разбиение списка на несколько списков;

• создание копии списка;

• определение количества узлов в списке;

• сортировка узлов в порядке возрастания значений в определенных полях;

• поиск узла с заданным значением в некотором поле.

	ptrnl	info	ptrn2
поле адреса поле поле адреса
предыдущего информации следующего
элемента элемента
списка списка
(левого (правого
элемента) элемента)

Рис. 2.3. Элемент двунаправленного списка

ЛИНЕЙНЫЙ ДВУНАПРАВЛЕННЫЙ СПИСОК

ptrn1=NULL

ptrn2=NULL

Ptrnl

Info

Ptm2

Ptrnl

Info

Ptrn2

ptrnl

info

ptrn2