Performance differences between ArrayList and LinkedList

by

ArrayList is faster than LinkedList if I randomly access its elements. I think random access means “give me the nth element”. Why ArrayList is faster?

ArrayList has direct references to every element in the list, so it can get the n-th element in constant time. LinkedList has to traverse the list from the beginning to get to the n-th element.

LinkedList is faster than ArrayList for deletion. I understand this one. ArrayList’s slower since the internal backing-up array needs to be reallocated.

ArrayList is slower because it needs to copy part of the array in order to remove the slot that has become free. If the deletion is done using the ListIterator.remove() API, LinkedList just has to manipulate a couple of references; if the deletion is done by value or by index, LinkedList has to potentially scan the entire list first to find the element(s) to be deleted.

If it means move some elements back and then put the element in the middle empty spot, ArrayList should be slower.

Yes, this is what it means. ArrayList is indeed slower than LinkedList because it has to free up a slot in the middle of the array. This involves moving some references around and in the worst case reallocating the entire array. LinkedList just has to manipulate some references.

More Related Contents:

  1. Removing duplicates from arraylist using set
  2. How to check two array list are same content in same position
  3. Logical disjunction of a list of booleans represented by integers [closed]
  4. ArrayList remove methods [closed]
  5. ArrayList, Loop and requisite if can not work that i want – Java 11
  6. How do I remove repeated elements from ArrayList?
  7. Sorting an ArrayList of objects using a custom sorting order
  8. Java: How to read a text file
  9. How to convert an ArrayList containing Integers to primitive int array?
  10. How does a ArrayList’s contains() method evaluate objects?
  11. Common elements in two lists
  12. Concurrent Modification Exception : adding to an ArrayList
  13. How do I make my ArrayList Thread-Safe? Another approach to problem in Java?
  14. Java: how can I split an ArrayList in multiple small ArrayLists?
  15. What is the difference between List and ArrayList? [duplicate]
  16. How to zip two Java Lists
  17. How to convert a String into an ArrayList?
  18. How do I declare a 2D String arraylist?
  19. ArrayList filter [duplicate]
  20. Searching in a ArrayList with custom objects for certain strings
  21. java.util.Vector – alternatives
  22. ArrayList or List declaration in Java
  23. Arrays.asList() of an array
  24. Permutation algorithm for array of integers in Java
  25. How does ArrayList work?
  26. java arraylist ensureCapacity not working
  27. how to fix java.lang.IndexOutOfBoundsException
  28. How to declare an ArrayList with values? [duplicate]
  29. How to remove common values from two array lists
  30. Why does the ArrayList implementation use Object[]?

Leave a Comment