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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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