Memory Usage in Linked List

Memory is a very crucial thing in the computer system. It is important to manage the memory system efficient all the time. So, let us see how linked list helps in effective usage of computer's memory system.

If you want to store the list of elements then what you will do?
You will declare an array!

Ex : int a[3];
where,

• a = array name
• 3 = array size(number of elements)

so, a total of 3* 4 = 12 bytes of consecutive memory locations will be assigned to store 3 integer values as shown below in the memory representation diagram.

After the creation of array if you want to increase the size of an array, it is not possible because the consecutive locations are already occupied by some other variable.
For example, 29 is already stored as shown in the fig above.

Array has static memory allocation hence, you cannot alter the array size once array is created. If you want to store the elements larger than the array size then you have to create a new array of bigger size and then copy the elements of older array into the new array .

Hence, some extra size of array is created in the beginning thinking that it may be required in the future to extend the array size.

Let us assume that an array of size 50 of type integer is created i.e., int a[50]; resulting into the memory usage of 200(50*4) bytes.

Now, if you need to store only 20 elements then you will use only 20 * 4 = 80 bytes out of 200 bytes. Remaining 120 bytes are free but this free memory cannot be assigned to some other variable as it is fixed to the array. Since you are not using this free memory it leads to wastage of memory which is the main drawback of array.

So, how can we reduce the memory wastage?

Solution is the linked list.

Linked list is a collection of elements but the elements are not stored into the consecutive memory locations.

Ex : If you create a linked list of size 4 then all the four elements will be stored into different blocks of memory as shown in the figure below . Assuming all the elements of linked list of type int each block of memory is of 4-bytes.

In array, since the values are stored in consecutive locations, traversing of data elements becomes easy with the help of the first element's address.

For traversing of elements in the linked list, we need a pointer pointing to the immediate next element in the list as all the elements are not stored into the consecutive locations

Therefore, in the linked list for one integer value 8-bytes of locations will be allocated where 4-bytes will be for integer element and the remaining 4-bytes for storing the address of the next integer element in the list as shown below in the memory representation diagram.

Adding elements is quite easy in linked list. Suppose, if you want to add an element in the linked list then it can be done easily. If anywhere 8-bytes of free space is available in the memory then that free space will be directly allocated for the new element in the list.

In linked list, a block of memory allocated for an element is referred to as a node as shown in the figure.

Each node contains two types of information,

1. Data
2. Pointer to the next node (address of the next node).

The pointer of the last node in the linked list is always equal to NULL.

Syntax of linked list :

struct node
{
 type member 1;
 type member 2;
 ..............
 ..............
 struct node *next; // *pointer to next node in the list
}

Fig. Logical representation of linked list having four nodes :

Here, all the operations(insertion, deletion, etc) starts with the help of a pointer that points to the first node in the linked list. This pointer is generally named start and it is the only source through which you can access the linked list. The list will be considered empty if the pointer start is equal to NULL.

I own a website www.coderlogs.com where in I write similar blogs so do visit this website for more such blog posts.