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.

Array storing ‘RONALDO’

Insertion at first which means we missed ‘R’ in ‘RONALDO’

Inserting ‘R’ at the first position

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’

Inserting ‘A’ in the middle

Notice only the elements after ‘A’ are shifted.

Inserting at last position — Missing ‘O’ in RONALDO

Inserting ‘O’ at the last position

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Arjun Vaidy

Arjun Vaidy

Founder of a startup. I explain things through first principles and intuitive mental models