Link List

Link List: from memory aspect

Ankur Kulhari

The idea of link list can be understood better with the following example:
Suppose Initially there is no data in the memory (RAM):

nomenclature

Fig. 0: Nomenclature used with reference to memory

empty memory

Fig. 1: Initially empty memory (RAM)

Now in our program we have written following statement:

int a;

Considering, our compiler takes 2 Bytes to store an integer value, after allocating memory to this data variable, memory may look like:

after allocating an integer

Fig. 2: Memory view after allocation of an integer

In fig. 2, 2 bytes means 2 blocks (1 block is of 1 byte) will be reserved (Note that we cannot assign these two blocks in non-contiguous manner as, we cannot divide an integer value into parts (i.e. 2 cannot be split).
Now, suppose we have another instruction in our program as:

int b[3];

In the above statement, we are storing 3 integers in contiguous manner, (whose starting address is accessed by “array”).
The memory will look like:

array allocation

Fig. 3: Memory view, after allocation of an array

“b” is pointing to the 1st element of the array “b” so, we can access the 1st element of this array by using b[0] = b+0 = 0+b = b.
The address of 2nd element will be b+2 bytes => b[1] = b+1 = 1+b = 1[b]. In programming languages like C/C++, compiler automatically performs b[1] = 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[2]), the compiler interprets c[1] 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.

link list

Fig. 4: Memory view at some point of time

This leads to under-utilization of memory which can be avoided if we have some provision to store elements at non-contiguous memory locations as shown in fig. 5:
non-contiguous allocation

Fig. 5: Allocating 5 integers in non-contiguous manner

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:
Linked allocation

Fig. 6: Linked allocation of memory

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:
link list

Fig. 7: Linked List, memory view

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.

What do you think about the article?