Информатика и технология программирования


Списки как динамические структуры данных - часть 2


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

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




Начало  Назад  Вперед