ArrayList vs LinkedList from memory allocation perspective

by

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.

More Related Contents:

  1. When to use LinkedList over ArrayList in Java?
  2. How do I remove repeated elements from ArrayList?
  3. How to sort a List/ArrayList?
  4. How to randomize two ArrayLists in the same fashion?
  5. ArrayList Vs LinkedList
  6. How to remove common values from two array lists
  7. How to put HashMap into different elements with same key
  8. I need to create a list that has both colums 1 and 2 equal [closed]
  9. ArrayList, Loop and requisite if can not work that i want – Java 11
  10. Initialization of an ArrayList in one line
  11. Why does my ArrayList contain N copies of the last item added to the list?
  12. How to avoid “ConcurrentModificationException” while removing elements from `ArrayList` while iterating it? [duplicate]
  13. Converting ‘ArrayList to ‘String[]’ in Java
  14. Why do I get an UnsupportedOperationException when trying to remove an element from a List?
  15. How to remove duplicates from a list?
  16. How to make a new List in Java
  17. List versus ArrayList as reference type?
  18. How to copy Java Collections list
  19. Java List Sorting: Is there a way to keep a list permantly sorted automatically like TreeMap?
  20. Add multiple items to an already initialized arraylist in Java
  21. Empty an ArrayList or just create a new one and let the old one be garbage collected? [duplicate]
  22. Simple way to compare 2 ArrayLists
  23. What is a List vs. an ArrayList? [duplicate]
  24. ArrayList: how does the size increase?
  25. Create a List of primitive int?
  26. What is the Simplest Way to Reverse an ArrayList?
  27. How to flatten all items from a nested Java Collection into a single List?
  28. Finding out if a list of Objects contains something with a specified field value?
  29. new ArrayList() failing in Java
  30. Is LinkedList thread-safe when I’m accessing it with offer and poll exclusively?

Leave a Comment