Связанный список

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

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

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

Самое правое поле элемента в списковой структуре является полем указателя. Оно указывает местоположение логически следующей ячейки списка: Чтобы определить начало списка, в специальный указатель (не изображенный на рисунке) необходимо занести значение адреса первого элемента списка (в данном случае адрес равен 4).

Основные преимущества связанных списков по сравнению с последовательными списками состоят в следующем:
(a)        при включении в список нового элемента, его можно поместить по любому свободному адресу и при этом не надо физически переставлять следующие элементы;
(b)       после исключения из списка некоего элемента его место можно снова использовать для размещения вновь добавляемого элемента, не прибегая к физическому перемещению каких-либо оставшихся данных;
(c)        если предусмотреть в ячейке не одно, а несколько полей указателя, то можно вести последовательную обработку различных свойств одинаковых элементов или их частей, не просматривая для этого каждый раз весь файл.

Например, рассмотрим список всех сотрудников компании, в котором предусмотрены указатели, устанавливающие отдельные связанные списки для лиц, владеющих немецким, французским или венгерским языком. Если необходимо получить список, имен сотрудников, говорящих по-венгерски, то будет обрабатываться только венгерская цепочка. И это будет выполнено значительно быстрее, чем просмотр всего списка при заданном значении свойства «владеет языком».

Чтобы иметь возможность находить первый и последний элементы этих списков, необходимо сформировать таблицу индексов, указывающих местоположение первого элемента каждой цепочки (первого сотрудника, говорящего по-венгерски, немецки или французски), а также ввести специальный символ, обозначающий конец каждого связанного списка. Такая организация показана на рис. 9.27, где в качестве признака конца списка использован символ #.


Организация данных и структуры данных Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора	Связанный список В связанном списке [27] элементы физически размещены произвольным образом, однако каждый элемент содержит ссылку, указывающую физическое местоположение логически следующего за ним элемента. Отдельные элементы списка часто называют ячейками. Ячейка состоит из двух частей информационной, или части данных, ссылочной, или части указателя, посредством которой ячейка связывается с другими ячейками. В общем случае при использовании списка не делается различия между ячейкой и содержащимися в ней данными, и когда при обработке списковых структур говорят «данные», то под этим понимается как информационная, так и ссылочная части ячейки. Представления строго последовательной структуры и связанного списка изображены на рис. 9.26. Здесь самое левое поле каждого элемента содержит значение свойства, определяющее последовательную структуру. Заштрихованная часть элемента содержит другую информацию. Самое правое поле элемента в списковой структуре является полем указателя. Оно указывает местоположение логически следующей ячейки списка: Чтобы определить начало списка, в специальный указатель (не изображенный на рисунке) необходимо занести значение адреса первого элемента списка (в данном случае адрес равен 4). Основные преимущества связанных списков по сравнению с последовательными списками состоят в следующем: (a) при включении в список нового элемента, его можно поместить по любому свободному адресу и при этом не надо физически переставлять следующие элементы; (b) после исключения из списка некоего элемента его место можно снова использовать для размещения вновь добавляемого элемента, не прибегая к физическому перемещению каких-либо оставшихся данных; (c) если предусмотреть в ячейке не одно, а несколько полей указателя, то можно вести последовательную обработку различных свойств одинаковых элементов или их частей, не просматривая для этого каждый раз весь файл. Например, рассмотрим список всех сотрудников компании, в котором предусмотрены указатели, устанавливающие отдельные связанные списки для лиц, владеющих немецким, французским или венгерским языком. Если необходимо получить список, имен сотрудников, говорящих по-венгерски, то будет обрабатываться только венгерская цепочка. И это будет выполнено значительно быстрее, чем просмотр всего списка при заданном значении свойства «владеет языком». Чтобы иметь возможность находить первый и последний элементы этих списков, необходимо сформировать таблицу индексов, указывающих местоположение первого элемента каждой цепочки (первого сотрудника, говорящего по-венгерски, немецки или французски), а также ввести специальный символ, обозначающий конец каждого связанного списка. Такая организация показана на рис. 9.27, где в качестве признака конца списка использован символ #.