Introduction to Linked Lists

In this introductory guide about linked lists we will familiarize you with this data structure, how to understand it in a relatively simpler manner and some introductory C programs with this data structure.

Linked List is a linear data structure that is formed as a group of nodes which are linked together in an order. A node consists of data as well as the address of the next node. This forms a chain like structure.

Linked List Node Diagram

As you can see from the diagram above the linked list consists of nodes each pointing to the next node in a systemic pattern. The list starts with a head which starts the link. Now each link contains a data element and a pointer to the next node called ‘Next.’ The NULL shows the end of the list.

Understanding Linked List

Lets understand the concept of Linked List with the aid of an example.

Suppose we want to store a list of five integers: 1,2,3,4,5 in the system memory. We request memory for one integer at a time.

To store the first number ‘1’ we will need space to store an integer. For example the block of 4 bytes at starting address 104 gest allotted for it as shown below. Number 1 will be stored here. Now to store the next number 2, another block starting address 118 will be allotted for it. As a separate request was made for this number hence we may or may not get memory adjacent to the first number. It is highly unlikely that the second number will get stored at adjacent memory to the first one. Likewise, separate requests are made for the rest of the numbers 3,4 and 5 and these get allotted at addresses 135, 144 and 172 respectively.

Note that the addresses which we are providing here are just for example purposes and do not depict the actual values.

Linked List Node pic1

Notice that when separate requests are made for each integer, instead of obtaining a contiguous block of memory allocated we are getting disjointed blocks of memory instead.

Adding Address of Next Block

Lets add more information by notifying which element is the first element and which comes after it. This will be achieved by linking these blocks together. When using an array, we got a contiguous block of memory allocated so it was very easy to determine the position of the element. In this case, however we will have to link the disjointed blocks together to achieve the same effect. To do this we will add additional information with each block. Hence the block will now be divided into two parts where one part will contain the data and the second part will contain the address of the next block.

Now for our first block the address of the next block that is storing the number ‘2’ is 118 so 118 gets stored in the address part of the first block. Likewise, the next block will store 135 in its address part. The block containing the number ‘3’ will store the address of the next block which will be 144. The block containing the number ‘4’ will store the address of the next block which will be 172. Now the last block containing the number ‘5’ has no block after it hence it will store 0 as the address which is an invalid address. The 0 address will denote the end of the list.

Linked List Node pic2

Nodes

These blocks which we have been talking about are basically nodes of our linked list. Each consisting of two segments containing the data which is the integer number in our case and the address to the next node that links the list together.

So instead of requesting for a single memory block to store the number now we will have to request for a block of memory that will store two variables. The first will be an integer variable that will store the value of our element. The second will be a pointer variable that will store the address of the next block (node) in the list.

Defining Linked List in C

In C language, we can define a structure type named node. There will be two fields in this node. The first one is integer which will store the data. The second is Node* which is the pointer to the node. It will store the address of the next node in the list.

struct Node
{
   int data;
   struct Node* next;
};

As we have two fields in our Node structure therefore, the node now needs 4 bytes for an integer variable and 4 more bytes for the pointer variable that will store the address of the next node. The pointer variable also takes up 4 bytes in a typical architecture. We will therefore get a block of 8 bytes called a ‘Node.’

For example if the list is stored like this in our system memory as non contiguous nodes connected to each other then this is a linked list data structure.

Linked List Node pic2

A logical view of the linked list will be as shown in the figure below:

Linked List Node picture 3

Here as you can see the data is stored in the nodes followed by the link to the next node. Each node points to the next node. The first node is called the HEAD. The only information of the linked list is the address of the HEAD. It gives us access to the complete list. The address in the last node is 0 or NULL. It denotes that the last node does not point to any other node.

C Program to create Linked List

The following C program creates the linked list we discussed above with 5 nodes. However note that the addresses allocated to the nodes will be different as they were shown for example purposes.


#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};

int main()
{
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;
    struct Node* fourth = NULL;
    struct Node* last = NULL;
 
    // allocate 5 nodes in the heap
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));
    fourth = (struct Node*)malloc(sizeof(struct Node));
    last = (struct Node*)malloc(sizeof(struct Node));
    
    head->data = 1; 
    head->next = second;
   
    second->data = 2;
    second->next = third;
    
    third->data = 3; 
    third->next = fourth;
    
    fourth->data = 4; 
    fourth->next = last;
    
    last->data = 5; 
    last->next = NULL;
    
  return 0;
}

Understanding the Code

What we are doing here is that we are first defining a structure named ‘Node’ which consists of a integer variable called ‘data’ and a pointer to the next node.

struct Node {
    int data;
    struct Node* next;
};

Inside the main() function we will first create five pointers for the five nodes called ‘head’, ‘second’, ‘third’, ‘fourth’ and ‘last’.

    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;
    struct Node* fourth = NULL;
    struct Node* last = NULL;

Then we will allocate memory in the heap for the five nodes using the malloc() operator.

    // allocate 5 nodes in the heap
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));
    fourth = (struct Node*)malloc(sizeof(struct Node));
    last = (struct Node*)malloc(sizeof(struct Node));

The next step will be to assign values to the integer data variable for all the nodes using the arrow operator. Here we have given the values 1,2,3,4 and 5 respectively to the five nodes. Lastly, we have linked the nodes to each other. The head node is linked to the second, the second node to the third, the third node to the fourth, the fourth node to the last and the last node to NULL.

 
    head->data = 1; 
    head->next = second;
   
    second->data = 2;
    second->next = third;
    
    third->data = 3; 
    third->next = fourth;
    
    fourth->data = 4; 
    fourth->next = last;
    
    last->data = 5; 
    last->next = NULL;

Traversing the List

To traverse a linked list we will start from the HEAD and traverse the list till we reach the NULL address. The user defined print() function not only traverses the list but also prints the data of each node as the output.

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};

void print(struct Node* n)
{
    while (n != NULL) {
        printf(" %d ", n->data);
        n = n->next;
    }
}

int main()
{
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;
    struct Node* fourth = NULL;
    struct Node* last = NULL;
 
    // allocate 5 nodes in the heap
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));
    fourth = (struct Node*)malloc(sizeof(struct Node));
    last = (struct Node*)malloc(sizeof(struct Node));
    
    head->data = 1; 
    head->next = second;
   
    second->data = 2;
    second->next = third;
    
    third->data = 3; 
    third->next = fourth;
    
    fourth->data = 4; 
    fourth->next = last;
    
    last->data = 5; 
    last->next = NULL;
    
    print(head);
    
  return 0;
}

Inside the print() function, if n is not NULL then it means that we are not at the end of the list and we keep on moving ahead by n=n->next which moves us to the next node. This will go on till we reach the last node after while the while() loop will be exited. This is the basic logic for traversing the linked list all the way till the end.

Code Output

Now let’s see the code output. After the compilation of the above code, you will get this output.

Linked List Node traversing list

Points to Note

  • Linked List is a linear data structure.
  • A Linked List consists of two parts, the data and the pointer to the next node. The first node is also known as the HEAD. The last node has an address NULL as it does not link to another node.
  • If the value of the HEAD is NULL then it denotes that it is an empty linked list.
  • Linked list elements are stored at non contiguous locations. The elements are however linked using pointers which takes extra amount of system memory.
  • The Linked List is always identified by the address of the first node. Unlike arrays, we can not access any of the elements in constant time.

Leave a Comment