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

This article will be of some sort of theoretical and story based. It will tell you about the crucial concepts of data structures and algorithms in terms of understanding the linked list with a unique story. This article is the third one in the series of “Data Structure and Algorithm (DSA)”. You’ll learn more about data structures and algorithms in details in my coming articles. So stay tuned for next articles.

About This Article

This article is kind of theoretical and story based. It will tell you about the crucial concepts of data structures and algorithms in terms of understanding the linked list with a unique story. This article is the third one in the series of “Data Structure and Algorithms (DSA)”. You’ll learn more about data structures and algorithms in detail in my coming articles. So, stay tuned for the next articles.

Read this article, then feel free to give your feedback.

The topics to be covered are,

  • Introduction and background
  • Story of array
  • Story of the linked list
  • Measuring the cost

Prerequisites of this article

You should be aware of the concepts of Data Structure and its purpose, ways of implementing it, and its classification. Also, you should have knowledge about time complexity and space complexity, and the ways to analyze the algorithm using different asymptotic notations. All the mentioned topics are clearly described in my previous articles -

Introduction and background

In the previous articles, we have seen that the implementation was not efficient in terms of memory consumption. So we can say that there are some limitations to the arrays. Let’s understand these limitations with the help of a story.

Data Structures And Algorithm 

In this story the computer, let’s say Mr. Computer, assigns the role to memory manager to manage the memory in terms of allocating or cleaning up the memory. Now, there is a web developer who is developing a web application say, John. Now John wants to store the data in the memory so he needs to talk to the memory manager to allocate the memory to the data. First, John wants to store int data into the memory by declaring an int variable,

  1. int x;  

Then memory manager finds/choose 4-bytes of memory for int variable in the memory. And then allocates it.

Data Structures And Algorithm 

Let’s say, memory manager stores int variable x at the address of 217. Then John stores the value at the address in the memory.

  1. x = 8;  
Data Structures And Algorithm

Now let’s say, John wants to make an array of integers of size 4. So he asks the memory manager to allocate memory of size 16-bytes, as array always take memory in a contiguous block.

  1. int A[4];  

So memory manager looks for one contiguous block of memory of size 16-bytes to store the array of size 4.

Data Structures And Algorithm 

Now, whenever John wants to store the element at any index. Let’s say:

  1. A[2] = 2;  

John’s application knows better about the base address of the variable A.

B.A = 204, index = 3, size = width = 4

Mathematical derivation

Here you’ll learn how the element is stored in the memory in the case of an array. Formula and all the mathematical derivation is given below,

Data Structures And Algorithm 


Data Structures And Algorithm

So, it depicts that if you want to store an element then it takes constant time.

Now let’s say, the array A is filled as shown in the figure below, 

 
Data Structures And Algorithm 

Now John wants to extend this array A and wants to store another 5th element in the array. So John asks the memory manager to do it.

Memory manager replies: John you can’t do it because array must store in one contiguous block and where your block A ends, there is not any space present. So, it is not possible for me to extend your array. You should think first about the actual size of the array because there is the highest possibility that you would not get the exact next consecutive block ahead to your previous block. So sorry for this.

Then John asks, what are the options left for me to do it?

Memory manager replies, you have to tell me the size of a new array and then I will create a new array for you according to your given size. Also, the elements in your previous array will be copied in the new array.

John thinks, this time I’ll give a really large size of the block for array so that it does not fill up. So, the memory manager creates a new array of some large size, as shown below,


Data Structures And Algorithm 

Memory manager cleans up the previous memory and creates a new array. Then John stores the new element 89 into it.

You can see the problem of memory is resolved with the help of the newly created array. But John still is not happy because in the first case, the memory was not enough to fulfill his requirements. And then he creates a new array and that array still has the limitation of size. And also the extra copying of previous elements into the new array is also costly in terms of time. One other problem is, in the newly created array, John stores only one element, and all the other memory is wasted. So this solution of creating a new array is not good.

Hence John decided to use new data structure named as Linked List. Now let’s understand what Linked List is. 

Linked List

As you know, John wants the best solution to his problem. So instead of asking memory manager for an array A, which will become one large contiguous block of memory, he asks memory for one element at a time in a separate request. Let’s say John wants to store the following list of four integers.

6, 5, 4, 2

He asks memory manager to allocate 4-bytes of memory integer 6. Memory manager does it as follows,

Data Structures And Algorithm  
Now John makes a separate request for storing integer 5 as follows, 
Data Structures And Algorithm 

Because John makes separate requests then he may or may not get the adjacent memory block to the previous memory block having integer 6. And the highest possibility is that he’ll not get the memory consecutive to 6. Similarly, John makes a separate request for integer 4 and 2. Then the memory will look like as follows,

Data Structures And Algorithm 

As you can see, when John makes a separate request for each integer, he gets disjoint non-contiguous blocks of memory. Because we don't have any addresses here then how can we access element 5, 4, 2?


In the array, we had one contiguous block of memory and identification of the block could be possible with the help of base address. Now the question is how can we access or identify the elements in the linked list. We have to link each block so that we can access them easily.

To link each block we divide each block into two parts, one part contains the data or value and the other part of the block contains the address of another consecutive block. You can see the logical view of memory below,

Data Structures And Algorithm 

So, John asks memory manager to allocate a block in memory that consists of two variables, one variable contains the integer value and the other one variable contains the pointer to the next block or the next node. So we can write:

  1. Struct Node {  
  2.     int data;  
  3.     Node * next;  
  4. }  

We can also show the phenomenon as,

Data Structures And Algorithm  

We need to know only the address of the head node to access the complete list. The first node contains the address of the 2nd node and through the 1st node, we can access the 2nd node. Similarly, in this way, we can access all the nodes. Now it is time to measure the time and space complexity of both solutions used by John.

Measuring the cost

In this section, you’ll see the cost of using both solutions arrays and linked list. We’ll focus on three aspects as shown below:

  • Accessing the element
  • Insertion of element
  • Deletion of element

Accessing the element

Arrays

In arrays, we can access any element using the mathematical derivation as shown above. And the result of this mathematical derivation is constant. So we can say that we can access any element in the array in some specific constant time.

Linked List

In a linked list, we should have knowledge about the address of the head node, so that we can traverse the whole list using addresses. So the time cost to access the element is proportional to the size of the list.

Data Structures And Algorithm  

The worst case of accessing the element in this list is that you want to access the element of the last node. We can say, the time complexity of linked list is “Big oh of n O(n) where n is the size of the complete list”.

Insertion of element

Arrays

If you want to learn the insertion, deletion and accessing the elements in the arrays, please read my consecutive previous article named as Learn About Data Structures And Algorithms (DSA) in which all these concepts are written in very great detail. Let’s move towards measuring the cost of the linked list.

Linked List

In the list, if you want to insert an element then make a separate request to create the node. Then add the data into the data part and add the address of the next node into the pointer part. Let’s say we want to add an element into the middle of the list, we have to follow the following steps:

  • Make a separate request to create a node.
  • Add the data into the data part.
  • Make adjustments of the links to connect each block with other.

In the first step, only the code is created as shown below,

Data Structures And Algorithm 

Then add the data into the data part, as shown below,

Data Structures And Algorithm 

Then adjust all the links to connect each block with each other, as shown below,

Data Structures And Algorithm 

So you have learned the insertion of the element in between the list. As you can see, we don’t need to make shifts between the elements, as in an array. So time complexity of insertion operation is O(n).

Deletion of element

Array

If you want to learn the insertion, deletion and accessing the elements in the arrays. Please read my consecutive previous article named as Learn About Data Structures And Algorithms (DSA) in which all these concepts are written in very great detail. Let’s move towards measuring the cost of the linked list.

Linked List

In the list if you want to delete an element you have to follow the following steps:

  • Delete the node and destruct its pointer references.
  • Adjust the pointer references with each other.

The time complexity for deletion operation in the linked list is O(n) because you have to traverse the whole list to reach the targeted node. So the time taken is directly proportional to the size of the list. So we can say that,

Data Structures And Algorithm  

Hence the time complexity for the deletion operation in case of the linked list is O(n).

Summary

In this article, you have seen the limitations of the array. Then you saw the data structure which can resolve the issues with the arrays. Then you have seen two solutions, arrays and linked list. Then you have seen the cost of operations on both the arrays and linked list. This article is the third one in the series of “Data Structure and Algorithm (DSA)”. In the next article, you’ll learn the difference between the array and the linked list in very great detail. So stay tuned for next articles.

Conclusion

I hope this article has helped you in understanding the basic concepts about limitations with the arrays and its solution as a linked list. Stay tuned for my next articles because this article is the third one in the series of “Learn about Data Structures and Algorithm (DSA)” and you’ll learn more about data structures and algorithms in coming articles. If you have any query, please feel free to contact me in the comments section. Also, give your feedback whether positive or negative. It will help me to make my articles better and increase my enthusiasm to share my knowledge.