Представление и обработка данных в виде одно- и двусвязных списков

Структура данных, в которой объекты расположены в линейном порядке, на­зывается связным списком. Однако в отличие от массива, в котором этот порядок определяется индексами, порядок в связном списке определяется указателями на объекты.

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

 

Данные

next

head

 

 

 

							т

Рис. 14.18. Односвязный список

Односвязный список отличается тем, что пройти по нему можно только в одном направлении — от начала в конец списка. Это оказывается достаточно неудобно, по­этому гораздо большее распространение получили двусвязные списки (рис. 14.19), отличающиеся тем, что их узлы содержат по два указателя — на следующий (next) и на предыдущий (prev) элементы списка. Помимо указателя head на первый элемент списка, может существовать также указатель tail на последний элемент списка.

 

prev

Данные

next

head

 

Рис. 14.19. Двусвязный список

, Частный случай двусвязного списка — замкнутый (кольцевой) список, указа­тель next последнего элемента которого указывает на первый элемент, а указатель prev первого элемента — на последний элемент списка.

Глава 14. Основы теории алгоритмов

Главная особенность списка — быстрое выполнение операций вставки и уда­ления в произвольном месте списка. Эти операции требуют модификации ука­зателей максимум у трех узлов: узла, над которым выполняется операция, и двух окружающих узлов. Схематично эти операции и изменения значений указателей показаны на рис. 14.20.

 

 

 

 

 

 

 

 

 

			Вставка

Удаление Рис. 14.20. Вставка и удаление в двусвязных списках

Алгоритм этих операций, приведенный на рис. 14.21 и 14.22, показывает, на­сколько простыми являются алгоритмические операции со списками.

 

 

 

 

 

 

 

 

	Q Начало)
/ Вводах /-
	x.nexf = Lhead	-----
false /^ r-4—<^L.hea	true
	Lhead. prev = x	-----
1----------- ►
	Lhead = x	-----
	x.prev = 0	-----
/ Вывод L /-
(Конец)

Входные данные:

L — список

X — вставляемый элемент (узел)

Поле next элемента х теперь указывает на первый элемент списка, поскольку мы присвоили ему значение указателя head

Список не пустой,

и указатель head указывает

На следующий узел?

Указатель prev бывшего первого элемента списка теперь указывает на вставляемый элемент х

Указатель head списка теперь указывает на вставленный элемент х

Поскольку х в списке первый, его указатель prev не указывает ни на какой элемент

Выходные данные:

L — список со вставленным

элементом х

Рис. 14.21. Вставка элемента в начало списка

14.4. Представление и обработка данных разного типа

Начало

Ввод L, х

Входные данные:

L — список

x — удалямый элемент (узел)

 

Удаляемый элемент не последний в списке? Если да (true), то полю prev следующего за х элемен­та присваивается значение поля prev удаляемого элемента

true Г	^x.prev =
x.prev.next =	x.next	Lhead =	x.nexf

Удаляемый элемент не первый в списке? Если да (true), то полю next предыдущего элемен­та присваивается значение поля next удаляемого элемента. Если удаляемый элемент в списке первый (false), то поле head списка направляется на следующий за удаляемым элемент

x.next.prev = x.prev

Вывод L

Выходные данные:

L — список с удаленным

элементом х

(Конец)

Рис. 14.22. Удаление элемента списка