Связанный список против динамического массива для реализации стека

Я начал изучать структуры данных и алгоритмы до того, как мой последний год в школе начнет следить за тем, чтобы я был на вершине всего. Одна проблема обзора: "Реализовать стек с помощью связанного списка или динамического массива и объяснить, почему вы сделали лучший выбор".

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

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

В решении книги сказано "для хранения очень больших объектов, список - лучшая реализация", но я не понимаю, почему.

Какой способ лучше? Какие факторы следует использовать для определения того, какая реализация является "лучшей"? Кроме того, какая-то моя логика здесь?

Ответ 1

Здесь есть много компромиссов, и я не думаю, что есть "правильный" ответ на этот вопрос.

Если вы реализуете стек с помощью связанного списка с указателем на хвост, то в худшем случае для выполнения push, pop или peek используется O (1). Однако каждый элемент будет иметь некоторые дополнительные служебные данные, связанные с ним (а именно, указатель), что означает, что для структуры всегда существует O (n) служебная информация. Кроме того, в зависимости от скорости вашего распределителя памяти стоимость выделения новых узлов для стека может быть заметной. Кроме того, если вы постоянно будете выталкивать все элементы из стека, вы можете столкнуться с плохим местоположением, потому что нет гарантии, что связанные ячейки списка будут храниться в памяти в памяти.

Если вы реализуете стек с динамическим массивом, то время ожидания амортизируется для push или pop - это O (1), а наихудшая стоимость просмотра - O (1). Это означает, что если вы заботитесь о стоимости какой-либо одной операции в стеке, это может быть не лучший подход. Тем не менее, распределения нечасты, поэтому общая стоимость добавления или удаления n элементов, вероятно, будет быстрее, чем соответствующие затраты в подходе, основанном на связанных списках. Кроме того, накладные расходы на память этого подхода обычно лучше, чем накладные расходы памяти связанного списка. Если ваш динамический массив просто хранит указатели на элементы, тогда накладные расходы на память в наихудшем случае возникают, когда половина элементов заполняется, и в этом случае есть n дополнительных указателей (то же, что и в случае, когда вы использовали связанный список), и в лучшем случае, когда динамический массив заполнен, пустых ячеек нет, а дополнительные служебные данные - O (1). Если, с другой стороны, ваш динамический массив непосредственно содержит элементы, накладные расходы на память могут быть хуже в худшем случае. Наконец, поскольку элементы хранятся смежно, существует лучшая локальность, если вы хотите непрерывно нажимать или выталкивать элементы из стека, поскольку все элементы находятся рядом друг с другом в памяти.

Короче:

У метода связанных списков есть наихудшие О (1) гарантии на каждую операцию; динамический массив амортизировал O (1) гарантии.
Локальность связанного списка не так хороша, как локальность динамического массива.
Суммарная накладная расходы динамического массива, вероятно, будет меньше, чем общая сумма служебных данных связанного списка, предполагая, что оба указателя хранилища относятся к их элементам.
Суммарные издержки динамического массива, вероятно, будут больше, чем у связанного списка, если элементы хранятся непосредственно.

Ни одна из этих структур явно "лучше", чем другая. Это действительно зависит от вашего варианта использования. Лучший способ выяснить, что быстрее, - это время и посмотреть, что работает лучше.

Надеюсь, это поможет!

Ответ 2

Ну, для вопроса с небольшими объектами и большими объектами рассмотрите, сколько дополнительного пространства для использования связанного списка, если у вас есть маленькие объекты в вашем стеке. Затем рассмотрите, сколько дополнительного пространства вам понадобится, если у вас есть куча объектов больших в вашем стеке.

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

Ответ 3

Важно то, сколько раз malloc() вызывается во время выполнения задачи. Для получения блока памяти может потребоваться от нескольких сотен до тысяч инструкций. (Время в free() или GC должно быть пропорционально этому.) Также сохраняйте смысл перспективы. Это может составлять 99% от общего времени или только 1%, в зависимости от того, что еще происходит.

Ответ 4

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

Ответ 5

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

Например, чтобы увеличить массив, если он заполнен, создайте новый массив в два раза больше размера и скопируйте элементы.

В итоге вы получите амортизированную стоимость ~ 3N для добавления N элементов.