Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Main differences:

  1. First, their underlying data structures are different. ArrayList is based on arrays, while LinkedList is based on linked lists.
  2. ArrayList is more suitable for random search, while LinkedList is more suitable for deletion and addition. Meanwhile, the time complexity of query, addition and deletion is also different.
  3. ArrayList and LinkedList both implement the List interface, but LinkedList also implements the Deque interface, so LinkedList can also be used as a queue.

Query:

An ArrayList is an array, so when you get one of its elements, you get it directly. The underlying LinkedList is implemented by linked lists, so it is slower to get the non-first and last elements of the LinkedList, which is also implemented in the source code of LinkedList.

Get method concrete implementation: Get method concrete implementation:But also becauseLinkedListThe bottom ofThe listThe reason throughgetFirstThe () method gets the first element andgetLastThe () method is fast enough to get the last element.

  • Add:

ArrayList finally add a element in the array operation directly add elements to the position of the last expansion at the same time, in the middle a subscript add elements, because the subscript already by the elements you need to add elements to vacate a place, so the elements behind the whole move back, then add the element is inserted into the subscript. LinkedList adds an element directly to the end of the list when the last element is added, no expansion is involved. When adding an element in the middle, you need to traverse the list to find the subscript, and then the insertion process does not involve element movement, where the speed depends on the size of the subscript.

The added performance of the two can not be compared depending on the specific application scenario.

  • delete

ArrayList deletion is just the opposite of insertion. If you delete an element with a subscript, all elements after that subscript move forward. LinkedList deletion iterates through the subscript before deleting it.