Связанное распределение памяти
Связанное представление линейного списка называется связанным списком. При связанном распределении памяти для построения структуры необходимо задать отношения следования и предшествования элементов с помощью указателей. Указателями служат адреса, хранимые в записях данных. В отличие от последовательного распределения памяти, при котором с помощью адресной функции вычисляется адрес следующего элемента, при связанном распределении памяти значение адресной функции можно получить только путем просмотра хранящихся указателей. Такой метод распределения памяти позволяет расширить либо сократить структуру без перемещения самих данных в памяти ЭВМ, однако при этом требуется больше памяти для хранения структуры по сравнению с последовательным распределением [16, 17].
Связанное распределение - более сложный, но и более гибкий способ хранения линейного списка. Каждый узел содержит указатель на следующий узел списка, т.е. адрес следующего узла списка (рис. 3.3). При связанном распределении не требуется, чтобы список хранился в последовательных элементах памяти. Наличие адресов связи в данном способе хранения позволяет размещать узлы списка произвольно в любом свободном участке памяти. При этом линейная структура списка обеспечивается указателями.
Структура линейного списка, представленная с помощью связанного распределения, называется также Цепной структурой или цепью.
Для достижения большей гибкости при работе с линейными списками в каждый узел X[i] вводятся два Указателя. Один из указателей реализует связь рас сматриваемого узла с узлом Х[М], а другой - с узлом X[i+l] (рис. 3.4).
Рис. 3.3. Примеры связанных линейных списков: а) – однонаправленный список; б) – тот же список после удаления узла 4 и включения узлов 2а и 5
Связанные списки - удобная форма представления динамически изменяющихся линейных структур. Любое произвольное изменение порядка записей, сокращение или расширение вектора данных в какой-либо записи не требуют перемещения записей в памяти ЭВМ.
