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

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 “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 know 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.

• Learn About Data Structures And Algorithms (DSA) – Part One
• Learn About Data Structures And Algorithm (DSA) - Part Two

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.

In this story the computer, let’s say Mr. Computer, assigns the role of 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 in the memory by declaring an int variable.

int x; 

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

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

x = 8;  

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 an array always takes memory in a contiguous block.

int A[4];  

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

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

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 isstored in the memory in the case of an array. The formula and all the mathematical derivations are given below,

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.

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 the array must be stored in one contiguous block and where your block A ends, there is not any space present. So, I can't 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 of 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 into the new array.

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

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 costly in terms of time. One other problem is, that 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 a new data structure named 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 the 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 the memory manager to allocate 4 bytes of memory integer 6. Memory manager does it as follows.

Now John makes a separate request for storing integer 5 as follows.

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 integers 4 and 2. Then the memory will look like as follows.

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 elements 5, 4, and 2?

In the array, we had one contiguous block of memory, and identification of the block could be possible with the help of a 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.

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

Struct Node {  
    int data;  
    Node * next;  
}  

We can also show the phenomenon as

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 solution arrays and linked lists. 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. The result of this mathematical derivation is constant. So we can say that we can access any element in the array at some specific constant time.

Linked List

In a linked list, we should know 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.

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 the 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 previous article namedLearn 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 to 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 to the links to connect each block with the other.

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

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

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

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 previous article named 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 destroy 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,

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

Summary

In this article, you have seen the limitations of the array. Then you see the data structure which can resolve the issues with the arrays. Then you have seen two solutions, arrays, and a 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 “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 the next articles.

Conclusion

I hope this article has helped you understand the basic concepts about limitations with the arrays and their 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 queries, 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.