Array Vs Linked List

1. Time complexity of Accessing :

Array : Direct or random access of elements is possible with the help of index value. Accessing does not depend on the number of elements in the array and hence takes constant time i.e., order of O(1).

Linked List : Sequential access is performed in the linked list to access any random element in the list.
Ex : In a linked list of 10 nodes to access the 8th node, you need to traverse all the previous seven nodes and then reach the 8th node hence, the access depends upon the number of nodes in the list and takes time complexity of order n i.e., O(n).

2. Memory utilization efficiency :

Array : Because of static memory allocation(fixed size), the memory utilization is not efficient.

Linked List : Because of dynamic memory allocation, memory utilization is efficient.

3. Memory usage :

Array : Less.

Linked List : High.

4. Time complexity of Insertion :

Array :

• At initial - O(n) (worst case)
• At ith position - O(n) (average case)
• At the end - O(1) (best case)

Linked List :

• At initial - O(1) (best case)
• At ith position - O(n) (average case)
• At the end - O(n) (worst case)

5. Time complexity of Deletion :

Array : O(n)

Linked List : O(n)

6. Search Techniques :

Array : Both Linear and Binary search techniques can be used.

Linked List : Only Linear search technique can be used.

I own a website www.coderlogs.com where in I write similar blogs so do visit this website for more such blog posts.