When to use LinkedList instead of ArrayList in Java?

Content from DOC https://q.houxu6.top/?s=When to use LinkedList instead of ArrayList in Java?

I always use it like this:

List<String> names = new ArrayList<>();

I use interfaces as type names for portability so that I can repurpose my code when I ask questions like this.

When should I use LinkedList instead of ArrayList or vice versa?

Summary: There are many use cases where ArrayList and ArrayDeque are preferred over LinkedList. If you’re not sure, start with ArrayList.

TLDR, accessing elements in ArrayList takes constant time [O(1)], and adding elements takes O(n) time [worst case]. Inserting elements into LinkedList takes O(n) time, and accessing them also takes O(n) time, but LinkedList uses more memory than ArrayList .

LinkedList and ArrayList are two different implementations of the List interface. LinkedList is implemented using a doubly linked list. ArrayList is implemented using a dynamically resizable array.

Due to standard linked list and array operations, the various methods will have different algorithm run times.

For LinkedList:

  • get(int index) is O(n) (average n/4 steps), but when index = 0 or O(1) when index = list.size() - 1 (in this case, you can also use getFirst() code> and getLast()). The main advantage of LinkedList is one of them.
  • add(int index, E element) is O(n) (average n/4 steps), but when index = 0 or index = list.size() - 1 is O(1) (in this case, you can also use addFirst( ) and addLast()/add()). The main advantage of LinkedList is one of them.
  • remove(int index) is O(n) (average n/4 steps), but when index = 0 or O(1) when index = list.size() - 1 (in this case, you can also use removeFirst() code> and removeLast()). The main advantage of LinkedList is one of them.
  • Iterator.remove() is O(1). The main advantage of LinkedList is one of them.
  • ListIterator.add(E element) is O(1). The main advantage of LinkedList is one of them.

NOTE: Many operations require n/4 steps in the average case, a constant number of steps in the best case (e.g. index = 0), and a constant number of steps in the worst case ( The middle of the list) is the number of steps n/2.

For ArrayList:

  • get(int index) is O(1). The main advantage of ArrayList is one of them.
  • add(E element) is O(1), but in the worst case it is O(n) because the array must be resized and copy.
  • add(int index, E element) is O(n) (average n/2 steps).
  • remove(int index) is O(n) (average n/2 steps).
  • Iterator.remove() is O(n) (average n/2 steps).
  • ListIterator.add(E element) is O(n) (average n/2 steps).

NOTE: Many operations require n/2 steps in the average case, a constant number of steps in the best case (end of list), and a constant number of steps in the worst case (start of list ) is the number of n steps.

LinkedList allows elements to be inserted or removed in constant time using iterators, but elements can only be accessed sequentially. In other words, you can traverse the list forward or backward, but finding a position in the list takes time proportional to the size of the list. Javadoc says* “The operation on the index list will be performed from the beginning or the end, whichever is closer is chosen”, so these methods are O(n)(n/ 4steps), but is O(1)* when index=0.

On the other hand, ArrayList allows fast random read access, so you can get any element in constant time. However, adding or removing from anywhere but the end requires moving all following elements, either to open up space or to fill gaps. Additionally, if you add more elements than the capacity of the underlying array, a new array (1.5x the size) will be allocated and the old array copied into the new one, thus in the worst case to ArrayListAddition is O(n), but it is constant on average.

So depending on what you intend to do, the implementation should be chosen accordingly. Iterating over either kind of list actually costs about the same. (Technically, iterating over an ArrayList is faster, but unless you’re very concerned about performance, don’t worry about that – they’re all constants.)
The main benefit of using LinkedList is when you reuse existing iterators to insert and delete elements. These operations can be completed inO(1)time by only locally changing the list. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other hand, searching in LinkedList means following the link in O(n) (n/2 steps), whereas in In an ArrayList, the required position can be mathematically calculated and accessed in *O(1)* time.

Another benefit of using LinkedList is when you add or remove elements from the beginning of the list, because these operations are O(1), whereas with ArrayList is O(n). Note that ArrayDeque might be a good alternative to LinkedList for adding and removing elements from the beginning, but it is not a List.

Also, if you have large lists, keep in mind that memory usage will vary. Each element of a LinkedList has more overhead because pointers to the next and previous elements are also stored. ArrayLists does not have this overhead. However, ArrayLists occupy the same memory as the allocated capacity, regardless of whether elements are actually added.

The default initial capacity of ArrayList is quite small (10 units from Java 1.4 to 1.8). But since the underlying implementation is an array, you have to resize the array if you want to add a large number of elements. To avoid the high cost of resizing when you know a large number of elements will be added, construct an ArrayList with a higher initial capacity.

If you understand these two structures from the perspective of data structure, then LinkedList is basically a sequential data structure, which contains a head node. A node is a wrapper around two components: a value of type T accepted via a generic, and another reference to the node to which it is linked. Therefore, we can assert that it is a recursive data structure (one node contains another node, which in turn has another node, and so on…). As mentioned above, adding elements in LinkedList takes linear time.

ArrayList is a growable array. It’s just like a regular array. Under the hood, when elements are added and the ArrayList is full, it creates a new array of a much larger size than the previous one. Then the elements are copied from the previous array into the new array and the element to be added is also placed at the specified index.

syntaxbug.com © 2021 All Rights Reserved.