Introduction to Linked List

Linked List in C: A Beginner’s Guide with Structure and Examples

A linked list in C is an example of a linear data structure that stores data dynamically using structures and pointers. It allows data to be stored at runtime by dynamically creating new memory locations. Unlike arrays, linked lists do not require a contiguous block of memory. Instead, nodes are connected using pointers.

In simpler words, you can think of it as a sequence of nodes, where each node contains some data and a pointer to the next node in the sequence.

Structure of a Node:

Each node in a linked list consists of two parts:

  • Data Field – stores the actual data (e.g., an integer, character, structure, etc.).
  • Pointer Field – stores the address of the next node in the list.

Note: The data field holds the user-defined data, while the pointer field links to the next node, enabling traversal through the list.

 

Linked List Node Structure in C:

In C, a linked list node is typically defined using a struct. The structure includes at least:

  • A data field.
  • A self-referential pointer (i.e., a pointer to the same structure type).

Example:

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

In above struct templates,

  • data: stores the actual value.
  • next: is a self-referential pointer, i.e., it points to another variable of the same structure type.

In linked list each node is dynamically allocated memory from the heap using the malloc() function. As a result, nodes remain in memory until they are explicitly deallocated using the free() function.

📌 Key Characteristics of linked list:

  • Dynamic size – Grows/shrinks at runtime, no fixed size needed.
  • Efficient insertions/deletions: Especially at the beginning or in the middle.
  • Sequential access: Unlike arrays, random access is not possible.
  • Non-contiguous memory – Nodes stored at different memory locations.
  • Extra memory overhead – Stores both data and pointer in each node.
  • No random access – Can’t access by index like arrays.
  • Pointer-based structure – Requires careful pointer management.

 

Representation of linked list:

A linked list is a sequence of nodes, where each node stores data and a pointer to the next node in the list. The first node is accessed through a special pointer known as the head or start pointer.

If the list contains no nodes, it is referred to as an empty linked list, and in that case, the head is set to NULL.

 

 

Let’s consider a above created linked list that is containing four nodes:

  • The head pointer points to the first node.
  • Each node contains:
    • A data field (e.g., 3, 10, 5, 1)
    • A pointer to the next node.
  • The first node stores 3 and the address of the second node.

  • The second node stores 10 and points to the third node, and so on.

  • The last node always contains a NULL pointer, indicating the end of the list.

 

Why use Linked List:

A linked list is a linear data structure, just like an array. But it offers greater flexibility when it comes to managing memory and performing insertions or deletions.

The primary reason to use a linked list is that:

  • Elements can be inserted or removed without reallocating or reorganizing the entire structure.
  • Data doesn’t need to be stored contiguously in memory or on disk.

This makes linked lists highly suitable for applications where:

  • The size of the dataset frequently changes.
  • Insertions and deletions occur often and at random positions.

 

Let’s understand the real-life example to understand the use of linked list. Suppose you have a sorted array storing the salaries of employees:

int aiSalary[10] = { 400, 1200, 2000, 4500, 5000 };

 

Now, a new employee joins with a salary of 1800.

To insert this value while keeping the array sorted:

  • You will have to shift all values greater than 1800 to make space.
  • This is time-consuming, especially as the array grows.

Now let’s see how a linked list helps — using it, this task becomes much simpler and more efficient:

  • You just create a new node with the value 1800.
  • Adjust a couple of pointers to insert it in the correct position.
  • No shifting, no reallocation, and no memory wastage.

 

Feature Array Linked List
Fixed Size ✅ Yes ❌ No
Dynamic Insertion ❌ Costly (shifting) ✅ Efficient
Memory Allocation ✅ Contiguous ✅ Non-contiguous
Deletion ❌ Requires shifting ✅ Just update links

 

✅ Advantages of Linked List:

  • A linked list is a dynamic data structure — nodes can be added or removed at runtime.
  • Insertion and deletion operations are simple and efficient.
    • O(1) insertion/deletion is only possible:

      • At the beginning of the list, or

      • When you already have a pointer/reference to the node.

    • If you need to search for the node, then it becomes O(n).

  • Unlike arrays, there is no need to define the size in advance.
  • We can easily add or remove nodes from the middle of the list.
  • Stacks and queues can be easily implemented using linked lists.

 

❌ Disadvantages of Linked List:

  • Each node stores an extra pointer to the next node, so it uses more memory compared to arrays.
  • Linked lists do not support random access; to access a node, we must traverse from the beginning.
  • Since nodes are not stored contiguously in memory, it takes longer to access individual elements.
  • Reverse traversal is difficult in singly linked lists.
  • In a doubly linked list, reverse traversal is possible, but it requires two additional pointers — one for the next node and another for the previous node.

 

Sample Program to Demonstrate Linked List in C:

In the following program, I will create a singly linked list consisting of 4 nodes. Each node holds an integer value and a pointer to the next node in the list.

// A simple C program to introduce a linked list
#include<stdio.h>
#include<stdlib.h>


// Creating Node
 struct Node 
{
  int iData;
  struct Node *pNextNode;
};


// Define the new type Node type and Node pointer
typedef  struct Node  NodeType, * NodePointer;



// This function use to prints the data of the list from the begning
//to the given list.

void PrintTheList(struct Node *pNode)
{
  int iCountOfNode = 0;
  while (pNode != NULL)
  {
     printf("\nValue of %d Node = %d\n", ++iCountOfNode , pNode->iData);
     pNode = pNode->pNextNode;
  }
}
 
 
// Program to create linked-list of 4 node
int main(void)
{

  // Head or Start pointer	
  NodePointer pHead = NULL;
  
  //first Node
  NodePointer pFirstNode = NULL;
  
  //Second Node
  NodePointer pSecondNode = NULL;
  
  //Third Node
  NodePointer pThirdNode = NULL;
  
  //Fourth Node
  NodePointer pFourthNode = NULL;
  
  
  // allocate 4 nodes in the heap  
  pFirstNode =  malloc(sizeof(NodeType)); 
  pSecondNode = malloc(sizeof(NodeType));
  pThirdNode =  malloc(sizeof(NodeType));
  pFourthNode =  malloc(sizeof(NodeType));
 
  /* Four blocks have been allocated  dynamically using the malloc and
     these allocated block are pointed by the node pointters pFirstNode, pSecondNode , pThirdNode
  and pFourthNode. 
        
   pFirstNode           pSecondNode      
          |                    |
          |                    |
    +-----+-------+      +-----+---------+  
    |Data | Address|     | Data | Address| 
    +-----+-------+      +------+--------+  		
    
    
    
    pThirdNode         pFourthNode      
          |                    |
          |                    |
    +-----+-------+      +-----+---------+  
    |Data | Address|     | Data | Address| 
    +-----+-------+      +------+--------+  
           
  */
  
   
  pFirstNode->iData = 3; //assign 3 in iData of first node
  pFirstNode->pNextNode = pSecondNode; // Assign Address of Second Node
  pHead = pFirstNode; // Assign Address of first node to head pointer
  
  /*
  
      		       pFirstNode               pSecondNode      
         	    |                      |
         	    |                      |
          +-----+-------+      +-----+---------+  
  pHead---------->|   3 |       |----->| Data | Address| 
          +-----+-------+      +------+--------+  

  */

   
  pSecondNode->iData = 10; //assign 10 in iData of second node
  pSecondNode->pNextNode = pThirdNode; //Assign Address of third Node
  
  /*
  
  				 
           pFirstNode         pSecondNode                pThirdNode      
         	  |                    |                         |
         	  |                    |                         |
          +-----+-------+      +------+------+       +-----+---------+  
  pHead---------->|3    |       |----->|  10  |      |------>| Data | Address| 
          +-----+-------+      +------+------+       +------+--------+  
  
  */
  
  pThirdNode->iData = 2; //assign 2 in iData of third node
  pThirdNode->pNextNode = pFourthNode; //Assign Address of fourth Node
  
  /*
  
  			 
           pFirstNode         pSecondNode                pThirdNode             pSecondNode      
         	  |                    |                         |                      |            
         	  |                    |                         |                      |
          +-----+-------+      +------+--------+       +-----+------+      +-----+---------+      
  pHead---------->|3    |       |----->|  10  |        |------>| 2   |      |----->| Data | Address| 
          +-----+-------+      +------+--------+       +------+-----+      +------+--------+   
  
  */
  
  pFourthNode->iData = 1; //assign 1 in iData of fourth node
  pFourthNode->pNextNode = NULL; //Assign NULL to indicate that linked list is terminated here.
  
   
  /* 
  
  			   pFirstNode         pSecondNode                pThirdNode           pSecondNode          
         	  |                    |                         |                   |            
         	  |                    |                         |                   |
          +-----+-------+      +------+--------+       +-----+------+      +-----+--------+      
  pHead---------->|3    |       |----->|  10  |        |------>| 2   |      |----->| 1   |    NULL|    
          +-----+-------+      +------+--------+       +------+-----+      +------+-------+   
  
  */
  
//Print The Linked list
  
  PrintTheList(pHead);   
  
 // After the use of linked-list explicitly delete the all nodes
 free(pFirstNode);
 pFirstNode = NULL;
 
 free(pSecondNode);
 pSecondNode = NULL;
 
 free(pThirdNode);
 pThirdNode = NULL;
 
 free(pFourthNode);
 pFourthNode = NULL;
 
 pHead = NULL;
 
   
  return 0;
}

OutPut:

 

 

 

Recommended Articles for you: