Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

ArrayList vs LinkedList from memory allocation perspective

I need to store a large amount of information, say for example 'names' in a java List. The number of items can change (or in short I cannot predefine the size). I am of the opinion that from a memory allocation perspective LinkedList would be a better option than ArrayList, as for an ArrayList once the max size is reached, automatically the memory allocation doubles and hence there would always be a chance of more memory being allocated than what is needed.

I understand from other posts here that individual elements stored in a LinkedList takes more space than an ArrayList as LinkedList also needs to store the node information, but I am still guessing for the scenario I have defined LinkedList might be a better option. Also, I do not want to get into the performance aspect (fetching, deleting etc) , as much has already been discussed on it.

like image 884
IS_EV Avatar asked Jul 19 '12 15:07

IS_EV


People also ask

What kind of memory allocation is used by ArrayList and LinkedList?

Memory for the ArrayList is allocated at compile time only. Thus it is known as Static Memory Allocation. Memory is allocated to the LinkedList during run-time, thus known as dynamic memory allocation. ArrayList can be one dimensional, two-dimensional or multi-dimensional.

Which takes more memory ArrayList or LinkedList?

A LinkedList consumes a bit more memory than an ArrayList since every node stores two references to the previous and next element. The insertion, addition, and removal operations are faster in a LinkedList because there is no resizing of an array done in the background.

Are Linked lists more memory efficient than arrays?

Better use of Memory: From a memory allocation point of view, linked lists are more efficient than arrays. Unlike arrays, the size for a linked list is not pre-defined, allowing the linked list to increase or decrease in size as the program runs.

Is ArrayList memory efficient?

So ArrayList requires more memory consumption than simple Arrays, but you can continue to use then in small programs that wont make much of a difference but when dealing with large ammout of data and performance issues, if you can go with simple arrays dont use ArrayList as Arrays are much faster.


1 Answers

LinkedList might allocate fewer entries, but those entries are astronomically more expensive than they'd be for ArrayList -- enough that even the worst-case ArrayList is cheaper as far as memory is concerned.

(FYI, I think you've got it wrong; ArrayList grows by 1.5x when it's full, not 2x.)

See e.g. https://github.com/DimitrisAndreou/memory-measurer/blob/master/ElementCostInDataStructures.txt : LinkedList consumes 24 bytes per element, while ArrayList consumes in the best case 4 bytes per element, and in the worst case 6 bytes per element. (Results may vary depending on 32-bit versus 64-bit JVMs, and compressed object pointer options, but in those comparisons LinkedList costs at least 36 bytes/element, and ArrayList is at best 8 and at worst 12.)

UPDATE:

I understand from other posts here that individual elements stored in a LinkedList takes more space than an ArrayList as LinkedList also needs to store the node information, but I am still guessing for the scenario I have defined LinkedList might be a better option. Also, I do not want to get into the performance aspect (fetching, deleting etc) , as much has already been discussed on it.

To be clear, even in the worst case, ArrayList is 4x smaller than a LinkedList with the same elements. The only possible way to make LinkedList win is to deliberately fix the comparison by calling ensureCapacity with a deliberately inflated value, or to remove lots of values from the ArrayList after they've been added.

In short, it's basically impossible to make LinkedList win the memory comparison, and if you care about space, then calling trimToSize() on the ArrayList will instantly make ArrayList win again by a huge margin. Seriously. ArrayList wins.

like image 117
Louis Wasserman Avatar answered Oct 20 '22 05:10

Louis Wasserman