Сравнение различных реализаций списков

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

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

2. Выполнение некоторых операторов в одной реализации требует больших вычислительных затрат, чем в другой. Например, процедуры INSERT и DELETE выполняются за постоянное число шагов в случае связанных списков любого размера, но требуют времени, пропорционального числу элементов, следующих за вставленным (или удаляемым) элементом, при использовании массивов. И наоборот, время выполнения функции для выделения предыдущего или последнего элемента списка постоянно при реализации списков посредством массивов, но в это же время пропорционально длине списка в случае реализации, построенной с помощью указателей.

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

4. Реализация списков с помощью массивов расточительна по отношению к компьютерной памяти, поскольку резервируется объем памяти, достаточный для максимально возможного размера списка независимо от его реального размера в конкретный момент времени. Реализация с помощью указателей использует столько памяти, сколько необходимо для хранения текущего списка, но требует дополнительную память для указателя каждой ячейки. Таким образом, в разных ситуациях по критерию используемой памяти могут быть выгодны разные реализации.

Не нашли, что искали? Воспользуйтесь поиском: