Illustration of How Data structure matters with array and set 🔢

Data structure

The data structure can be analyzed the performance with interaction and use case or operations of its.

Most Data structures have four basic operations:

Read, looking somewhere in the data structure to get data on that spot.
Search, looking for a place of specific data within the data structure.
Insert, adding a data or new value into the data structure.
Delete, removing data from the data structure. Measuring the speed of data structure can be determined by the number of steps that each operation takes (Time complexity), not a used time since time can be differed by each computer performance.

Array

The array is just the data structure that contains data lists.

For example:

array = ['a','b','c','d']

The array has two properties:

Index, the position of the array, usually starts the first index at 0 ('a').
Size the number that the array holds data inside. From the example above, this array has a size of 4.

Array Reading Operation Analysis:

The computer takes only one step to look at each position in the array.

We create the above example array (array size of 4) and want to see the last position value; the computer will allocate a row of 4 grids in its memory, each grid has its sorted address. For example, 100, 101, 102, 103.

The computer always remembers the address of the first position/index (index 0 at 100 in memory). If you want to access the last index (3), the computer can sum the index with the first position address, 100 + 3 = 103, and take a peek at the address of 101 in memory and get the last value.

Array Searching Operation Analysis:

If we change the question from what is value in ... index to where is the index of 'd' value in the array.

The computer can jump to a specific index position but can not jump to a particular value. It has to take a look at each one of the data in the array until it sees 'd' value.

It took four steps to search for the last value in the array, the worst case. N cells in an array take a maximum of N steps for searching.

Array Insertion Operation Analysis:

Insertion can be determined in various ways depending on where we want to insert because the computer has to move away from the value next to the insert position.

If we want to add 'e' in the last position, the computer can allocate another cell by remembering the first address and moving at last index in memory, then adding 'e' behind.

This scenario took only one step.

But if we want to add 'e' before 'c' the computer will allocate space in memory behind the end of the array and need to shift 'd' to new space and 'c' to previous 'd' 's position, then add 'e' at previous 'c' position.

This took three steps, 2 for shifting 'd' and 'c' and 1 for adding 'e'

It has a worst-case scenario when we shift the entire array, which is inserted at the first position. This can be concluded as N cells in an array taking a maximum N+1 steps for insertion.

Array Deletion Operation Analysis

Deletion from an array is eliminating a specific position in the array.

If we want to delete the last index, it takes only one step to do it.

But if we want to take the second index out ('b'), we must delete 'b' and move 'c' to the previous 'b' position and move 'd' to the previous 'c' position.

This case took three steps, 1 for deletion and 2 for shifting.

The worst-case happens when we have to delete the first index, which requires a shift to the front of the rest of the array.

If we have 10 data in the array and remove the first one, we have to shift the left of 9 data. We can say that N cells in an array take a maximum N steps for deletion.

Set

Set is data structure that not allow duplicate value in it. For set base array ['a','b','c','d'], we cannot add 'a','b','c' or 'd' in this array.

Not allowing a duplicated value required a search for existing value before insertion, leading to different efficiency in insertion operation.

The searching operation is just looking at the total N size of the set that there is no existing of new value inside. This takes N steps.

And addition with insertion operation step, which is one step for inserting at the end and N+1 for the first place of the set.

To sum up, It takes 2N+1 for inserting into the first set, and the best case takes N+1 for inserting at the end of the set.

Wrapping up

Analysing the steps of each data structure operation is the way to understand time complexity and compare data structure to use.