DSA Linked Lists

Linked Lists Full Concept in Data Structures

A linked list organizes data elements so that each element contains a reference directing to the following element in the sequence.Unlike arrays, linked lists don’t need all elements to be side by side in memory. Rather than being stored together, each data item is joined to the next through a pointer.

Definition

A linked list is made up of individual elements called nodes, where each node holds a value and a reference directing to the following element.

Structure of a Node:

Each distinct element within a linked list is referred to as a node.

A node has two parts:

• Data – The actual value
• Pointer – The memory spot that indicates where the next node resides.

How It’s Built:

Instead of storing everything in one block like an array, a linked list spreads the nodes throughout memory. Each node knows where the next one is, so they stay connected even though they are scattered.

Real-Life Analogy:

Think of a treasure hunt. You find the first clue (node), and it tells you where the next clue is (pointer). You follow one by one, even if the clues are in different rooms. That’s how a linked list works.

Example

#include <stdio.h> 
#include <stdlib.h>  

// Define a node 
struct Node {     
       int data;     
       struct Node* next; 
};  

int main() {     
      // Create 3 nodes     
      struct Node* first = malloc(sizeof(struct Node));     
      struct Node* second = malloc(sizeof(struct Node));     
      struct Node* third = malloc(sizeof(struct Node));      

      first->data = 10;     
      first->next = second;      

      second->data = 20;     
      second->next = third;      

      third->data = 30;     
      third->next = NULL; // End of list      

     // Traverse and print     
     struct Node* temp = first;     
     while (temp != NULL) {         
               printf("%d -> ", temp->data);         
               temp = temp->next;     
     }     
     printf("NULL");      

     return 0; 
} 

Output

10 -> 20 -> 30 -> NULL

Types of Linked Lists

• Singly Linked List

Every node contains a link directing solely to the subsequent node.

• Doubly Linked List

Each node links to both its next and previous nodes.

• Circular Linked List

The final node connects to the initial node, creating a circular chain.

Key Operations

Benefits of Linked Lists

• Flexible size — you can grow or shrink easily without wasting memory.
• Great for adding/removing items in the middle or at ends.
• Memory use is dynamic, not pre-allocated.

Downsides

• Slower to access — no direct index like arrays.
• Uses extra memory for pointers.
• More steps needed to find or modify an item.

When to Use Linked Lists:

• When you don’t know in advance how much data you'll store.
• When frequent insertions or deletions are required.
• When dynamic memory usage is important.

Quick Comparison with Arrays