 # 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): Fig. 0: Nomenclature used with reference to 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: 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;
```

In the above statement, we are storing 3 integers in contiguous manner, (whose starting address is accessed by “array”).
The memory will look like: 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 = b+0 = 0+b = b.
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. 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: 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: 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: 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.