Memory Usage in Linked List
Tags: c, linkedlist, array
Published: 2022-05-11 10:30:15

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.

![image](https://i.ibb.co/F5WHsxG/IMG-20220422-145922.jpg)

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.

![image](https://i.ibb.co/bLVKvGQ/IMG-20220422-152428.jpg)



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.

![image](https://i.ibb.co/jvmpZCW/IMG-20220422-152405.jpg)

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 :**

![image](https://i.ibb.co/58MjSd1/IMG-20220422-152340.jpg)

![image](https://i.ibb.co/Ybz0XSx/IMG-20220422-152318.jpg)

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.