Linked lists vs. arrays

This is a comparison of performance on storage and common operations of linked lists and arrays.

Time complexity analysis[]

The table below uses the Java APIs ArrayList and LinkedList^[1] as reference.

Operation		Time complexity
Operation		`ArrayList`	`LinkedList`
get	`get(int index)` at head/tail	O(1)	O(1)
get	`get(int index)` in middle^[2]	O(1)	O(n)
set	`set(int index)` at head/tail	O(1)	O(1)
set	`set(int index)` in middle^[2]	O(1)	O(n)
add	`add(int index, E e)` at in middle^[2]	O(n)^[3]	O(n)^[4]
	`add(int index, E e)` at head	O(n)^[3]	O(1)
	`add(int index, E e)` at tail	Amortized: O(1)^[5]	O(1)
remove	`remove(int index)` at head	O(n)^[3]	O(1)
	`remove(int index)` at tail	O(1)	O(1)
	`remove(int index)` in the middle^[2]	O(n)^[3]	O(n)^[4]
size check	`size()`	O(1)	O(1)
size check	`isEmpty()`	O(1)	O(1)

Both of them require O(n) space complexity to store the data.
However, linked lists require more space overhead than arrays, because each node also needs to store its adjacent nodes.

If you have a lot of random access operations, use ArrayList.
If you always add / remove at the end, use ArrayList.
- When the time complexity is similar for using ArrayList and LinkedList, use ArrayList (better overhead and locality)
Stack and Vector classes are not recommended.
- Whenever you need a vector, use ArrayList.
- Whenever you need a stack, use Deque.
- Reasons: Stack overflow: LinkedList vs Stack (Archive)
  - Stack extends Vector is synchronized, while LinkedList is not.
  - LinkedList is good for inserting/removing elements at random positions (whenever you have an iterator). But for a stack, we only insert/remove at the end. This makes ArrayList more appealing.
  - Deque allows inserting/removing elements from either end in O(1) time complexity. This covers the functionalities of Stack and Queue.

↑ In Java, the LinkedList class is implemented as a doubly linked list. The wrapper class LinkedList has APIs that allow direct access to both the head and the tail of the linked list, and allows the traversal in both directions.
↑ ^2.0 ^2.1 ^2.2 ^2.3 This is known as random access.
↑ ^3.0 ^3.1 ^3.2 ^3.3 An ArrayList takes O(1) time for locating the position, and O(n) time for shifting elements.
↑ ^4.0 ^4.1 A LinkedList takes O(n) time for locating the position, and O(1) time for inserting / removing the node.
↑
Depends on whether the program need to expand the linked list. Java expands the linked list by one half of its original capacity whenever needed.
- In case of needing expansion, the expansion time complexity is O(n).
- When there is no expansion, the time complexity is O(1).
See amortized time complexity for more details.