Thread by @swapnakpanda

Difference between an Array and a Linked List

↓

These differences will make you grasp the fundamentals of both Array and Linked List really quick.

And if you are preparing for any interviews, it would definitely help you.

Let's explore 👇

1️⃣ Storage
2️⃣ Size
3️⃣ Access of Elements
4️⃣ Insertion/Deletion of Elements
5️⃣ Search for Elements
6️⃣ Memory Allocation
7️⃣ Memory Usage
8️⃣ Memory Utilisation
9️⃣ Use case

↓

1️⃣ Storage

Array: Elements are stored consecutively in contiguous memory locations.

Linked List: Elements are stored in random memory locations. Each element stores the address of the next element.

2️⃣ Size

Array: Size of an Array depends upon the implementation. But by default it's static and declared during memory allocation.

Linked List: Size of a Linked List is not fixed. Linked Lists can grow and shrink after each element insertion/deletion.

3️⃣ Accessing of Elements

Array: Access is direct. Elements are accessed using index. Time Complexity is O(1).

Linked List: Access is sequential. Traversal always happens from the beginning. Time Complexity is O(n).

4️⃣ Insertion/Deletion of Elements

Array: It is slower as space has to be made by shifting existing elements. Time Complexity is O(n).

Linked List: It is faster, easier and more efficient. No need to shift elements, only pointer values are changed. Time Complexity is O(1).

5️⃣ Searching for Elements

Array: Both linear [O(n)] and binary search [O(log n)] can be performed. If elements are sorted, binary search is too efficient.

Linked List: Only linear search is efficient [O(n)]. Binary search takes even more time [O(n log n)].

6️⃣ Memory Allocation

Array: For static sized arrays, memory is allocated ahead of time whereas dynamic sized arrays, new memory is allocated at runtime only.

Linked List: Memory for an element of a Linked List is allocated as and when it is inserted.

7️⃣ Memory Usage

Array: It requires less usage of memory as only values are stored.

Linked List: It requires high usage of memory as every element stores both value and pointer to next element.

8️⃣ Memory Utilisation

Array: High and ineffective. Because array is allocated entire "size" of memory even if zero or only 1 element is to be stored.

Linked List: Very efficient. Memory is allocated only for existing elements.

9️⃣ Use Case

Array: Use an array when elements need to be accessed randomly and in a fast manner.

Linked List: Use a linked list when memory utilisation is of high importance and, sequential access of elements are fine.