5.3 Кольцевой связный список

В односвязном списке для доступа к желаемому элементу необходимо просматривать список с самого на­чала. Это неудобно и занимает много времени.

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

nach

12 3

3

4

_Г

2

_К

1

Рис. 13

5.4 Линейный двусвязный список

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

1. прямой – на следующий элемент списка;

2. обратный – на предыдущий элемент списка.

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

	пас 1	2 3 4
d	|з U |	4 U 1° 1 Н 1° h 1ГгЧ h I2
	1 ^-~	Г | 1 |_J

Рис. 14

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

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

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

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

В кольцевом двусвязном списке указатель конца не нужен.

Включение в двусвязный список

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

Пусть нужно вставить новый элемент после элемента с индексом I. J := FREE; индекс свободного элемента

SPISOK[J].INF := C; занесение информации

FREE := SPISOK[J].LINK; индекс нового свободного элемента K := SPISOK[I].LINK1; индекс следующего элемента SPISOK[I].LINK1 := J; смена указателя предыдущего элемент

SPISOK[J].LINK1 := K; занесение информации SPISOK[J].LINK2 := I; указатель на следующий элемент

SPISOK[K].LINK2 := J;

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

Контрольные вопросы

1. Линейные динамические структуры. Связный список.

2. Реализация связного списка массивом.

3. Линейный двусвязный список.