Learn About Data Structures And Algorithm (DSA) - Part Two

Now, we want to insert the value 5 at the specific position in the list, let’s say position/index 2, so we have to shift all the values to higher indices so that the block of position/index 2 becomes empty. Then, we store the value 5 into the index 2. You can see it in the following picture logically,

Now, we want to remove the element from the list, first, the value is deleted then all the values are shifted to fill the empty space. You can see it in the following pictures logically.

The pictures are completely made by myself and very self-explanatory. So if you still have any problem understanding then feel free to ask me the question in the comments section.

If you want to count the total number of elements in the list then, you can use the “count” function and calculate the total number of elements using the “end” variable. See the method below.

Hence, you have seen how this array implements the previous ADT. As you know, we have created this list which is of some large size. Now the question comes: what will happen when the list is full while there is still some data to be stored?

So the answer to this question is: “When the implemented array is full, create a new larger array of double the size of the previous array. Then copy the elements of the previous array into the new array.”

So, this is the strategy to be followed when the array is filled up. However, the problem with this strategy is, this strategy is costly in terms of time and space. Let’s go towards the analysis of this list.

Analysis of list

As we know, the data structure is a way to store and organize data. But we also have to maintain the efficiency of the program/algorithm. In the case of this list, we have to analyze the cost of operations performed on this list.

Measuring the Time Complexity

Let’s analyze the cost of time for operations performed on the previously created array. You’ll see the analysis in terms of the following cases.

• Accessing the element
• Inserting the element
• Removing the element

Accessing the element

If we want to access the element of a specific position/index, then it takes some constant time because it is an array. So, its time complexity in terms of Big-Oh notation is O(1).

Inserting the element

If we want to insert an element at the end of the array, then this insertion also takes constant time. So, time complexity in terms of Big-Oh notation will be O(1). This is the case when the array is not full.

But if you want to insert the element at a particular position in the array, then we have to make shifts, as you have seen in the above pictures. The worst case will be if you want to insert an element in the start of the array at the index 0, so we have to shift all the elements toward higher indices. So, cost in terms of time is proportional to the length of the array having n size T n, so time complexity in terms of Big-Oh notation will become O(n), which shows linear time complexity.

The third case is, what happens when you are inserting an element in the array and the array is already full? So we know we have to make a new array of double the size of the previous array and copy the elements from the previous array into the new array. So the procedure of creating a new array and copying all the elements is costly in terms of time. So for this strategy, the cost in terms of time is proportional to the length of the array having n size T n, so time complexity in terms of Big-Oh notation will become O(n), which shows linear time complexity.

Removing the element

If we want to remove an element at the end of the array, then this removal of the element takes constant time. So, time complexity in terms of Big-Oh notation will be O(1).

But if you want to remove an element at a particular position in the array, then we have to make shifts, as you have seen in the above pictures. The worst case will be, if you want to remove an element at the start of the array means at the index 0, so we have to shift all the elements towards lower indices. So, cost in terms of time is proportional to the length of the array having n size T n, so time complexity in terms of Big-Oh notation will become O(n), which shows linear time complexity.

Result of analysis

To understand the result I have created a table to show the costs of time for each operation for the described ADT.

You can deduct the result from the above table like the following.

• We can access any element in constant time. So it is a good thing.
• Insertion and deletion of the element are costly.
• The addition of an element when the array is full is also time costly.

The problem is space complexity

We also have one problem here about this array implementation: it makes our memory useless. When we want to insert the element in the array, and we encounter the filled array, then we create a new array of double the size of the previous array. But we didn’t fill the whole array and all the rest of the memory is wasted. So, it is costly in terms of space complexity.

Best implementation

As we analyze this array implementation, we see that it is costly in terms of both memory and time. So now we need a data structure that implements our previous ADT efficiently. We need to have a data structure that grows its size automatically when the list is full. So, we can say that we want to create a dynamic list. So all these features can be implemented by a data structure named “Linked List”. Linked List is a data structure that implements our ADT and behaves efficiently in terms of memory and time. You’ll learn the introduction and implementation of Linked List in coming articles. So stay tuned!

Summary

In this article, you have learned what the data structure is and its implementation, including ADT. You also learned the implementation of different ADTs. Then you have learned the analysis of different operations run on the array in terms of time and space complexity. Then, you have seen the best implementation of the described ADT. So stay tuned for coming articles.

I hope this article has helped you understand the basic concepts of data structures and the implementation of an array data structure for an ADT. Stay tuned for my next articles because this article is the second one in the series of “Learn about Data Structures and Algorithm (DSA),” and you’ll learn more about data structure in the coming articles. If you have any queries, please feel free to contact me in the comments section. Also, to provide feedback, whether positive or negative. It will help me to make my articles better and increase my enthusiasm to share my knowledge.