37

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.

IS_EV
  • 988
  • 2
  • 15
  • 29
  • 1
    It would seem you already have your answer. Link-list would be better since it doesn't double in size when the max is reached. lets say you have 251 names and then the array doubles to 500 when you reach 250. you then allocated 249 extra spots in memory for nothing. Basically what I'm trying to say is in the long run Link-List > ArrayList as far as memory goes. – Eric Robinson Jul 19 '12 at 15:43
  • @Eric Robinson: The below comments from other users prove that my understanding was not correct. You might like to note this as well. thanks.. – IS_EV Jul 19 '12 at 21:45
  • 1
    See this answer for a memory footprint visual of the two: http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist/7671021#7671021 – Numeron Jan 23 '13 at 03:39

5 Answers5

69

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.

Jianxin Gao
  • 2,717
  • 2
  • 19
  • 32
Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • FWIW, Joshua Bloch has said publicly that he thinks that ever writing LinkedList was a mistake and that he should have just stuck with ArrayList. (I don't remember where I came across this statement, unfortunately). – Tobias May 22 '14 at 03:42
  • There's one more thing to consider if you have a memory limit - when growing ArrayList, you need to have the original array and the new array in memory while copying, consuming 2.5x more than needed in the worst case. Even so, ArrayList beats LinkedList. – Mifeet May 08 '15 at 12:42
6

ArrayList use one reference per object (or two when its double the size it needs to be) This is typically 4 bytes.

LinkedList uses only the nodes its needs, but these can be 24 bytes each.

So even at it worst ArrayList will be 3x smaller than LinkedList.

For fetching ARrayList support random access O(1) but LinkedList is O(n). For deleting from the end, both are O(1), for deleting from somewhere in the middle ArrayList is O(n)

Unless you have millions of entries, the size of the collection is unlikely to matter. What will matter first is the size of entries which is the same regardless of the collection used.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
6

... but I am still guessing for the scenario I have defined LinkedList might be a better option

Your guess is incorrect.

Once you have got past the initial capacity of the array list, the size of the backing will be between 1 and 2 references times the number of entries. This is due to strategy used to grow the backing array.

For a linked list, each node occupies AT LEAST 3 times the number of entries, because each node has a next and prev reference as well as the entry reference. (And in fact, it is more than 3 times, because of the space used by the nodes' object headers and padding. Depending on the JVM and pointer size, it can be as much as 6 times.)

The only situation where a linked list will use less space than an array list is if you badly over-estimate the array list's initial capacity. (And for very small lists ...)

When you think about it, the only real advantage linked lists have over array lists is when you are inserting and removing elements. Even then, it depends on how you do it.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
3

ArrayList.trimToSize() may satisfy you.

Trims the capacity of this ArrayList instance to be the list's current size. An application can use this operation to minimize the storage of an ArrayList instance.

By the way, in ArrayList Java6, it's not double capacity, it's about 1.5 times max size is reached.

卢声远 Shengyuan Lu
  • 31,208
  • 22
  • 85
  • 130
3

Back of the envelope worst-case:

500,000 names in an array sized to 1,000,000 = 500,000 used, 500,000 empty pointers in the unused portion of the allocated array.

500,000 entries in a linked list = 3 pointers per entry (Node object holds current, prev, and next) = 1,5000,000 pointers in memory. (Then you have to add the size of the Node itself)

Affe
  • 47,174
  • 11
  • 83
  • 83
  • @Affe..yup..in short even in this scenario(kinda worst case) ArrayList will consume lesser memory than Linked List.. – IS_EV Jul 19 '12 at 21:43