Time complexity of linked list

by·

Comment

ArrayListandLinkedListare frequently used classes in the Java collection framework. If you know only understand basic performance comparisons ofArrayListandLinkedList, but not the minor details of these two classes, then this article is for you.

" ArrayListshould be used where more search operations are required, and LinkedListshould be used where more insert and delete operation is needed."

ArrayListuses theArraydata structure, and LinkedList uses theDoublyLinkedListdata structure. Here, we are going to discuss how the underlying data structure affects the performance of insert, search, and delete operation onArrayListandLinkedList.

Below is an example of different operations usingArrayListandLinkedList.

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class Example { public static void main(String[] args) { List<Integer> linkedList = new LinkedList<>(); List<Integer> arrayList = new ArrayList<>(); /*Block 1: Insert at last in LinkedList*/ linkedList.add(1); linkedList.add(111); System.out.println(linkedList); /* Output: [1, 111]*/ /*Block 2: Insert at last in Arraylist*/ arrayList.add(1); arrayList.add(111); System.out.println(arrayList); /* Output: [1, 111]*/ /*Block 3: Insert at given index in LinkedList*/ linkedList.add(1, 11); linkedList.add(3, 1111); System.out.println(linkedList); /* Output: [1, 11, 111, 1111]*/ /*Block 4: Insert at given index in Arraylist*/ arrayList.add(1, 11); arrayList.add(3, 1111); System.out.println(arrayList); /* Output: [1, 11, 111, 1111]*/ /*Block 5: Search by value in LinkedList(searching 111 value)*/ for(int i=0; i < linkedList.size(); i++) { if(linkedList.get(i).equals(111)){ System.out.println("Value found at index: "+i); /* Output: Value found at index: 2*/ } } /*Block 6: Search by value in ArrayList(searching 111 value)*/ for(int i=0; i < arrayList.size(); i++) { if(arrayList.get(i).equals(111)){ System.out.println("Value found at index: "+i); /* Output: Value found at index: 2*/ } } /*Block 7: Get value by index in LinkedList*/ Integer value = linkedList.get(2); System.out.println(value); /* Output: 111*/ /*Block 8: Get value by index in ArrayList*/ value = arrayList.get(2); System.out.println(value); /* Output: 111*/ /*Block 9: Remove by value in LinkedList(remove 111)*/ boolean isDeleted = linkedList.remove(new Integer(111)); System.out.println(isDeleted); /* Output: true*/ /*Block 10: Remove by value in ArrayList(remove 111)*/ isDeleted = arrayList.remove(new Integer(111)); System.out.println(isDeleted); /* Output: true*/ /*Block 11: Remove by index in LinkedList*/ value = linkedList.remove(2); System.out.println("Removed value: "+value); /* Output: Removed value: 1111*/ /*Block 12: Remove by index in ArrayList*/ value = arrayList.get(2); System.out.println("Removed value: "+value); /* Output: Removed value: 1111*/ } }

Now, we will compare similar operations onArrayListandLinkedListand see which is more efficient in terms of performance and why.

Insert Value at Last Index(Block 1 and 2)

When we insert a value at last index, ArrayList has to —

• Check whether the underlying array is already full or not.

• If the array is full then it copies the data from the old array to new array(size double than an old array),

• Then add the value at the last index.

On the other hand, LinkedList simply adds that value at the tail of the underlying DoublyLinkedList.

Both have time complexity O(1), but due to the added steps of creating a new array in ArrayList its worst-case complexity reaches to order of N, that is why we prefer using LinkedList where multiple inserts are required.

Insert Value at Given Index(Block 3 and 4)

When we insert a value at a given index, ArrayList has to-

• Check whether the underlying array is already full or not.

• If the array is full then it copies the data from the old array to a new array(size double than an old array).

• After that, starting from the given index, shift values by one index to create space for the new value.

• Then add the value at the given index.

On the other hand, LinkedList simply finds the index and adds that value at a given index by rearranging pointers of underlying DoublyLinkedList.

Both have time complexity O(N), but due to the added steps of creating a new array in ArrayList, and copying the existing values to the new index, we prefer using LinkedList where multiple inserts are required.

Search by Value(Block 5 and 6)

When we search any value in ArrayList or LinkedList, we have to iterate through all elements. This operation has O(N) time complexity. It looks like ArrayList and LinkedList both will have the same performance.

Here we need to notice that array(underlying data structure of ArrayList) stores all values in a continuous memory location, but DoublyLinkedList store each node at a random memory location. Iterating through continuous memory location is more performance efficient than random memory location, that is why we prefer ArrayList over LinkedList when searching by value.

Get Element by Index(Block 7 and 8)

When we get an element by Index then ArrayList is a clear winner.

ArrayList can give you any element in O(1) complexity as the array has random access property. You can access any index directly without iterating through the whole array.

LinkedList has a sequential access property. It needs to iterate through each element to reach a given index, so time complexity to get a value by index from LinkedList is O(N).

Remove by Value(Block 9 and 10)

It is similar to adding value at a given index. To remove an element by value in ArrayList and LinkedList we need to iterate through each element to reach that index and then remove that value. This operation is of O(N) complexity.

The difference is that to remove an element from LinkedList, we just need to modify pointers, which is O(1) complexity, but In ArrayList, we need to shift all elements after the index of the removed value to fill the gap created.

As shifting is costly operation then modifying pointers, so even after the same overall complexity O(N), we prefer LinkedList where more delete by value operation is required.

Remove by Index(Block 11 and 12)

To remove by index, ArrayList find that index using random access in O(1) complexity, but after removing the element, shifting the rest of the elements causes overall O(N) time complexity.

On the other hand, LinkedList takes O(N) time to find the index using sequential access, but to remove the element, we just need to modify pointers.

As shifting is costly operation than iterating, so LinkedList is more efficient if we want to delete element by index.

Singly Linked List vs Doubly Linked List

Before looking at the differences between the singly linked list and doubly linked list, we first understand what is singly linked list and doubly linked list separately.