#notes #fundamental

Массивы против связных списков

Языки программирования с широким набором средств обычно включают встроенные реализации абстрактных типов данных (список, очередь, стек и другие), которые зачастую основаны на некоторой стандартной структуре данных. Более того, отдельные из них могут даже автоматически переключаться с одной структуры данных на другую во время выполнения программ, в зависимости от способа доступа к данным.

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

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

Массивы предпочтительнее связных списков, когда:
– необходим произвольный доступ к данным и очень быстрый доступ к элементам;
– число элементов не изменяется во время выполнения программы, благодаря чему легко выделить непрерывное пространство памяти.