The idea of link list can be understood better with the following example:
Suppose Initially there is no data in the memory (RAM):
Considering, our compiler takes 2 Bytes to store an integer value, after allocating memory to this data variable, memory may look like:
Now, suppose we have another instruction in our program as:
In the above statement, we are storing 3 integers in contiguous manner, (whose starting address is accessed by “array”).
The memory will look like:
The address of 2nd element will be b+2 bytes => b = b+1 = 1+b = 1[b]. In programming languages like C/C++, compiler automatically performs b = b+1 = b + 2 bytes (as this array is of type integer and an integer takes 2 bytes of memory).
Similarly, if the array is of type char (char c), the compiler interprets c as, c+1 = address of c + 1 bytes (assuming a char takes 1 bytes of memory).
In case of array, sufficient contiguous memory must be available to accommodate all the variables. If the system has memory as shown in fig. 4, it is not possible to store an array of 3 integers because of unavailability of contiguous memory.
But in the case of above allocation, address of each element must be available to access the data stored at different non-contiguous memory locations (unlike the case of array). Alternatively, if we have the address of 1st element and 1st element store the address of 2nd element and so on, as given in following figure:
There is need of some extra space to store the address value of next element’s location at each element’s location.
Example: to store 3 integer values using non-contiguous memory allocation. It will look like:
If we have the starting element’s address with us (i.e. 200) we can access the data with the data part and the address of next location, where next element is stored by looking at the address part (i.e. 300). The last node contains NULL in the address part which means no next element.
Some important points about Link List
- The name link list comes from this concept: List means a node (data + address to next element) and all the nodes are connected with links (addresses).
- To access any node/element of link list, one has to traverse from the 1st element (start) up to the desired element (because we have the address of the 1st element/start of the link list ==> Link list is a linear data structure (means we can traverse elements in a linear manner only).
To further understand the Link List concept from the implementation point of view please click here.