LINKED LIST-INTRODUCTION
You may choose to look the other way but you can never say again that you did not know.
~William Wilberforce
Hey coder. Welcome to this article where we are going to start with a new data structure "Linked List".
Since you have already studied Arrays, we want to explain Linked Lists by comparing them with Arrays.
So, we will first discuss Arrays and then see how it contrasts with Linked Lists.
Important Links : Introduction Video
Let's suppose we declare the following array:
Since 1 integer is 4 bytes, therefore, for 10 integers 40 bytes are needed.
We have a stack and a heap present in the memory. It can be shown by figure 2.
Suppose the heap is filled at positions where there are green areas and in between those 20 bytes are free at places as shown in the figure 2. If we want to make an arr of 40 bytes then it won't be possible to do so because an array is continuous and continuous memory spaces are not available in this heap.
Had the memory been like shown in figure 3 then we would have been able to construct our desired array since 40 bytes are available continuously in the heap here.
For this situation the array is formed in those 40 bytes as shown in the figure below and the stack would have stored the address of the first element of arr , say 4k.
Now, we'll see how the linked list is different from it.
For a linked list, had the memory in the heap not been contiguous as shown in figure 2, then we would not have had any problem in forming it.
As you can see in the above figure, the list is "linked" despite that the memory is not continuous. Do you see those small squares with 2 compartments? They are called nodes.
There are 2 parts in a node: Data and Address of the next node.
You can see in the figure 6, each element stores the address of the next element. For example, the first node at the address 4k stores the address of the next element at 5k, the node at 5k stores the address of its next element 6k and so on. As there are no more elements after the last node , therefore the address part of it is left "null".
Also the stack stores the address of the first element of the linked list i.e. 4k.
Hence we conclude that a linked list is a non-continuous type of data structure. This means that a Linked List utilizes space when there is a fragmented memory.
Even though it is advantageous to use Linked Lists for space conservation in heap, we notice that since each node stores 2 values: data and address, therefore each node requires 4bytes+ 4 bytes=8 bytes of memory. The memory used in arrays for each element was only 4 bytes. Here, the space of linked lists is noticed to be more.
We suggest you watch the Introduction video for Linked Lists for a better understanding of this topic.
We will discuss more about Linked Lists in the upcoming videos and articles so don't forget to check them out. This is only the starting. For now, Goodbye.
