Data structures from scratch- Bot-up series #13[Illustrations of Insertion/Deletion operations in Arrays and Linked Lists]
Understanding basic operations through illustrations.
Before moving on to the next data structures. Let us pause for a moment and understand insertion/deletion operations in arrays and linked lists.
Both arrays and linked lists have different approaches to these operations. Lets’s start from Array.
Say we stored ‘RONALDO’ in an Array.
Insertion at first which means we missed ‘R’ in ‘RONALDO’
Notice rest of the elements is shifted to the one place right. This will ensure contiguous memory allocations and indexing.
Insertion at the middle which means we missed ‘A’ in ‘RONALDO’
Notice only the elements after ‘A’ are shifted.
Inserting at last position — Missing ‘O’ in RONALDO
Notice there is no shifting of elements in the array.
The same is the case with deletion but opposite i.e element shifts to the left.
Insertion/Deletion in the array requires shifting of elements and this shifting takes time.
If the number of elements is more and shifting takes time proportionally
The time cost of shifting is directly proportional to the number of elements in the array.
Worst case — Inserting at first
Average case — Inserting in the middle
Best case — Inserting at last
However we always choose data structures based on worst-case scenarios. This means arrays are not suitable for Insertion/Deletion operations.
We will see the same operations in linked lists in the next post.
