ArrayList vs LinkedList с точки зрения распределения памяти

Ответ 1

LinkedList может выделять меньше записей, но эти записи астрономически дороже, чем они были бы для ArrayList - достаточно, чтобы даже худший случай ArrayList был дешевле, чем память.

(FYI, я думаю, что вы ошибаетесь, ArrayList растет на 1,5 раза, когда он заполнен, а не 2x.)

См. http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures: LinkedList потребляет 24 байта на элемент, а ArrayList потребляет в лучшем случае 4 байта на элемент, а в худшем случае - 6 байт на элемент, (Результаты могут варьироваться в зависимости от 32-битных и 64-битных JVM и параметров указателя сжатого объекта, но в тех сравнениях LinkedList стоит не менее 36 байт/элемент, а ArrayList - в лучшем случае 8 и в худшем случае 12.)

UPDATE:

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

Чтобы быть ясным, даже в худшем случае ArrayList на 4x меньше, чем a LinkedList с теми же элементами. Единственный возможный способ сделать выигрыш LinkedList - это намеренно исправить сравнение, вызвав ensureCapacity с заведомо завышенным значением или удалить из значения ArrayList множество значений после их добавления.

Короче говоря, в принципе невозможно сделать LinkedList выигрыш сравнения памяти, а если вам интересно пространство, то вызов trimToSize() на ArrayList мгновенно сделает ArrayList снова заново с огромным отрывом. Шутки в сторону. ArrayList побеждает.

Ответ 2

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

Ваша догадка неверна.

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

Для связанного списка каждый node занимает по меньшей мере 3 раза количество записей, потому что каждый node имеет ссылку next и prev, а также ссылку на запись. (И на самом деле, это более чем в 3 раза из-за пространства, используемого заголовками объектов и дополнениями узлов. В зависимости от размера JVM и указателя оно может достигать 6 раз.)

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

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

Ответ 3

ArrayList.trimToSize() может удовлетворить вас.

Обрезает емкость этого экземпляра ArrayList как текущий список размер. Приложение может использовать эту операцию для минимизации хранения экземпляр ArrayList.

Кстати, в ArrayList Java6 он не удваивает емкость, он достигает максимального размера в 1,5 раза.

Ответ 4

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

LinkedList использует только узлы, которые ему нужны, но они могут быть 24 байта каждый.

Так что даже при этом худший ArrayList будет в 3 раза меньше LinkedList.

Для выборки ARrayList поддерживает произвольный доступ O (1), но LinkedList - O (n). Для удаления из конца оба значения O (1), для удаления из где-то в середине ArrayList - это O (n)

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

Ответ 5

Задняя часть конверта в худшем случае:

500 000 имен в массиве размером от 1 000 000 = 500 000, 500 000 пустых указателей в неиспользуемой части выделенного массива.

500 000 записей в связанном списке = 3 указателя на запись (Node объект имеет текущий, предыдущий и следующий) = 1500000 указателей в памяти. (Затем вам нужно добавить размер самого Node)