Неупорядоченные списки

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

Неупорядоченный список должен поддерживать следующие операции:

• добавление элемента к списку;

• удаление элемента из списка;

• определение наличия элемента в списке;

• выполнение каких-либо операций (например, печати или вывода не дисплей) для всех элементов списка.

Для управления подобным списком можно немного изменить простую схему, представленную в предыдущем разделе. Когда удаляется элемент из середины списка, оставшиеся элементы сдвигаются на одну позицию, заполняя образовавшийся промежуток. Однако удаление элемента массива подобным способом может занимать много времени, особенно если этот элемент находится в начале списка. Чтобы удалить первый элемент массива, содержащего 1000 записей, необходимо сдвинуть 999 элементов на одну позицию влево. Гораздо быстрее удалять элементы при помощи простой схемы “сборки мусора“. Вместо удаления элементов из списка можно их отметить как неиспользуемые. Если элементы списка – данные простых типов, то их можно маркировать с помощью так называемого "мусорного" значения. Если элементы списка - это структуры, определенные оператором tуре, то можно добавить к ним новое логическое поле IsGarbage. При удалении элемента из списка значение поля IsGarbage устанавливается в True.

Через некоторое время список может переполниться "мусором", в результате чего будет тратиться большое количество машинного времени на пропуск ненужных элементов, чем на обработку реальных данных. Во избежание такой ситуации надо периодически выполнять процедуру сборки мусора. Эта процедура перемещает все непомеченные элементы в начало массива. После этого они добавляются к неиспользуемым элементам в конце массива. Когда вам потребуется включить в список дополнительные элементы, можно повторно использовать помеченные ячейки без изменения размера массива. После добавления дополнительных неиспользуемых записей к другим свободным ячейкам полный объем свободного пространства может стать слишком большим. В этом случае следует уменьшить размер массива, чтобы освободить память.

Связанные списки

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

Рис. 3. Структура односвязного списка

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

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

new_cell^.NextCell:=top_cell;

top_sell:=new_cell;

Рис. 4. Добавление элемента в начало связанного списка

Так же легко осуществляется вставка нового элемента и в середину связанного списка. Предположим, необходимо добавить новый элемент после ячейки, на которую указывает переменная after_me. В этом случае соответствующий код на Pascal имеет вид:

new_cell^.NextCell:=after_me^.NextCell;

after_me^.NextCell:=new_cell

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

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

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

Рис. 5. Представление двусвязного списка