Data Structures & Algorithms
DSA - Home
DSA - Introduction
DSA - Environment Setup
DSA - Algorithms Basics
DSA - Characteristics of Algorithms
DSA - Asymptotic Analysis
Data Structures
DSA - Data Structure Basics
DSA - Data Structures and Types
DSA - Array Data Structure
Linked Lists
DSA - Linked List Data Structure
DSA - Single Linked List Data Structure
DSA - Doubly Linked List Data Structure
DSA - Circular Linked List Data Structure
Stack & Queue
DSA - Stack Data Structure
DSA - Expression Parsing
DSA - Queue Data Structure
Searching Algorithms
DSA - Searching Algorithms
DSA - Linear Search Algorithm
DSA - Binary Search Algorithm
DSA - Interpolation Search
DSA - Jump Search Algorithm
DSA - Exponential Search
DSA - Fibonacci Search
DSA - Sublist Search
DSA - Hash Table
Sorting Algorithms
DSA - Sorting Algorithms
DSA - Bubble Sort Algorithm
DSA - Insertion Sort Algorithm
DSA - Selection Sort Algorithm
DSA - Merge Sort Algorithm
DSA - Shell Sort Algorithm
DSA - Heap Sort
DSA - Bucket Sort Algorithm
DSA - Counting Sort Algorithm
DSA - Radix Sort Algorithm
DSA - Quick Sort Algorithm
Graph Data Structure
DSA - Graph Data Structure
DSA - Depth First Traversal
DSA - Breadth First Traversal
DSA - Spanning Tree
Tree Data Structure
DSA - Tree Data Structure
DSA - Tree Traversal
DSA - Binary Search Tree
DSA - AVL Tree
DSA - Red Black Trees
DSA - B Trees
DSA - B+ Trees
DSA - Splay Trees
DSA - Tries
DSA - Heap Data Structure
Recursion
DSA - Recursion Algorithms
DSA - Tower of Hanoi Using Recursion
DSA - Fibonacci Series Using Recursion
Divide and Conquer
DSA - Divide and Conquer
DSA - Max-Min Problem
DSA - Strassen's Matrix Multiplication
DSA - Karatsuba Algorithm
Greedy Algorithms
DSA - Greedy Algorithms
DSA - Travelling Salesman Problem (Greedy Approach)
DSA - Prim's Minimal Spanning Tree
DSA - Kruskal's Minimal Spanning Tree
DSA - Dijkstra's Shortest Path Algorithm
DSA - Map Colouring Algorithm
DSA - Fractional Knapsack Problem
DSA - Job Sequencing with Deadline
DSA - Optimal Merge Pattern Algorithm
Dynamic Programming
DSA - Dynamic Programming
DSA - Matrix Chain Multiplication
DSA - Floyd Warshall Algorithm
DSA - 0-1 Knapsack Problem
DSA - Longest Common Subsequence Algorithm
DSA - Travelling Salesman Problem (Dynamic Approach)
Approximation Algorithms
DSA - Approximation Algorithms
DSA - Vertex Cover Algorithm
DSA - Set Cover Problem
DSA - Travelling Salesman Problem (Approximation Approach)
Randomized Algorithms
DSA - Randomized Algorithms
DSA - Randomized Quick Sort Algorithm
DSA - Karger’s Minimum Cut Algorithm
DSA - Fisher-Yates Shuffle Algorithm

Data Structures & Algorithms - Single Linked List Algorithm

Share with a Friend

HOME

Single Linked List

A Single Linked List is a linear data structure in which each node contains:

Data
Pointer (or reference) to the next node

Example Representation:

IMAGE - single_linked_list_1.jpg

Each node points to the next, and the last node points to NULL.

1️⃣ Single Linked List Implementation

C C++ Java Python

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

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

// Insert at the end
void insertAtEnd(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    while (temp->next) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// Print list
void printList(struct Node* head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);

    printf("Linked List:\n");
    printList(head);

    return 0;
}

Output

Linked List:
10 -> 20 -> 30 -> NULL

#include <iostream>
using namespace std;

// Node structure
class Node {
public:
    int data;
    Node* next;

    Node(int val) {
        data = val;
        next = NULL;
    }
};

// Insert at end
void insertAtEnd(Node*& head, int newData) {
    Node* newNode = new Node(newData);
    if (!head) {
        head = newNode;
        return;
    }

    Node* temp = head;
    while (temp->next) temp = temp->next;
    temp->next = newNode;
}

// Print list
void printList(Node* head) {
    while (head) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "NULL\n";
}

int main() {
    Node* head = NULL;

    insertAtEnd(head, 10);
    insertAtEnd(head, 20);
    insertAtEnd(head, 30);

    cout << "Linked List:\n";
    printList(head);

    return 0;
}

Output

Linked List:
10 -> 20 -> 30 -> NULL

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class LinkedList {
    Node head;

    // Insert at end
    void insertAtEnd(int newData) {
        Node newNode = new Node(newData);
        if (head == null) {
            head = newNode;
            return;
        }

        Node temp = head;
        while (temp.next != null) temp = temp.next;
        temp.next = newNode;
    }

    // Print list
    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        LinkedList ll = new LinkedList();

        ll.insertAtEnd(10);
        ll.insertAtEnd(20);
        ll.insertAtEnd(30);

        System.out.println("Linked List:");
        ll.printList();
    }
}

Output

Linked List:
10 -> 20 -> 30 -> NULL

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    # Insert at end
    def insertAtEnd(self, newData):
        newNode = Node(newData)
        if not self.head:
            self.head = newNode
            return
        temp = self.head
        while temp.next:
            temp = temp.next
        temp.next = newNode

    # Print list
    def printList(self):
        temp = self.head
        while temp:
            print(temp.data, end=" -> ")
            temp = temp.next
        print("NULL")

ll = LinkedList()
ll.insertAtEnd(10)
ll.insertAtEnd(20)
ll.insertAtEnd(30)

print("Linked List:")
ll.printList()

Output

Linked List:
10 -> 20 -> 30 -> NULL

Following is a type declaration for a linked list of integers:

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

2️⃣ Basic Operations in Linked List

The basic operations in the linked lists are insertion, deletion, searching, display, and deleting an element at a specified key. These operations are performed on Single Linked Lists as given below −

A Linked List supports several operations that allows insertion, deletion, traversing, searching and reversing the list. The most common operations are:
1️⃣ Insertion − Adds an element at the beginning of the list.

2️⃣ Deletion − Deletes an element at the beginning of the list.

3️⃣ Traversal − Displays the complete list.

4️⃣ Search − Searches an element using the given key.

5️⃣ Reverse − Reverses the complete list.

6️⃣ Delete − Deletes an element using the given key.

1️⃣ Insertion in Linked List

Insertion allows adding a new node at different positions:

At the beginning
At the end
At a specific position

Insert at the Beginning - C / C++ / Java / Python

🔹 C Program to insert node at the beginning

🔹 C++ Program to insert node at the beginning

🔹 Java Program to insert node at the beginning

🔹 Python Program to insert node at the beginning

C C++ Java Python

C Program: Insert Node at Beginning
#include <stdio.h>
#include <stdlib.h>
 
// Define the structure for a node
struct Node {
    int data;
    struct Node* next;
};
 
// Function to insert a node at the beginning
void insertAtBeginning(struct Node** head_ref, int new_data) {
    // Allocate memory for new node
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
 
    // Put in the data
    new_node->data = new_data;
 
    // Make next of new node as head
    new_node->next = *head_ref;
 
    // Move the head to point to the new node
    *head_ref = new_node;
}
 
// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}
 
// Main function
int main() {
    struct Node* head = NULL;
 
    // Insert elements at the beginning
    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 10);
 
    // Print the linked list
    printf("Linked List: ");
    printList(head);
 
    return 0;
}

Output

Linked List: 10 -> 20 -> 30 -> NULL

C++ Program: Insert Node at Beginning
#include <iostream>
using namespace std;
 
// Define the structure for a node
class Node {
public:
    int data;
    Node* next;
 
    Node(int value) {
        data = value;
        next = nullptr;
    }
};
 
// Function to insert a node at the beginning
void insertAtBeginning(Node*& head, int new_data) {
    Node* new_node = new Node(new_data);
    new_node->next = head;
    head = new_node;
}
 
// Function to print the linked list
void printList(Node* node) {
    while (node != nullptr) {
        cout << node->data << " -> ";
        node = node->next;
    }
    cout << "NULL" << endl;
}
 
// Main function
int main() {
    Node* head = nullptr;
 
    // Insert elements at the beginning
    insertAtBeginning(head, 30);
    insertAtBeginning(head, 20);
    insertAtBeginning(head, 10);
 
    // Print the linked list
    cout << "Linked List: ";
    printList(head);
 
    return 0;
}

Output

Linked List: 10 -> 20 -> 30 -> NULL

Java Program: Insert Node at Beginning
class Node {
    int data;
    Node next;
 
    // Constructor
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
 
public class LinkedList {
    Node head;
 
    // Function to insert a node at the beginning
    public void insertAtBeginning(int newData) {
        Node newNode = new Node(newData);
        newNode.next = head;
        head = newNode;
    }
 
    // Function to print the linked list
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }
 
    // Main method
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
 
        // Inserting elements at the beginning
        list.insertAtBeginning(30);
        list.insertAtBeginning(20);
        list.insertAtBeginning(10);
 
        // Printing the linked list
        System.out.print("Linked List: ");
        list.printList();
    }
}

Output

Linked List: 10 -> 20 -> 30 -> NULL

Python Program: Insert Node at Beginning
 
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    # Function to insert at the beginning
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
 
    # Function to print the linked list
    def print_list(self):
        temp = self.head
        while temp:
            print(temp.data, end=" -> ")
            temp = temp.next
        print("NULL")
 
# Main code
ll = LinkedList()
ll.insert_at_beginning(30)
ll.insert_at_beginning(20)
ll.insert_at_beginning(10)
 
print("Linked List:", end=" ")
ll.print_list()

Output

Linked List: 10 -> 20 -> 30 -> NULL

Insert at the End - C / C++ / Java / Python

🔹 C Program to insert node at the end

🔹 C++ Program to insert node at the end

🔹 Java Program to insert node at the end

🔹 Python Program to insert node at the end

C C++ Java Python

C Program: Insert Node at the End
 
#include <stdio.h>
#include <stdlib.h>
 
// Define the structure for a node
struct Node {
    int data;
    struct Node* next;
};
 
// Function to insert a node at the end
void insertAtEnd(struct Node** head_ref, int new_data) {
    // Create a new node
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    struct Node* last = *head_ref;
 
    new_node->data = new_data;
    new_node->next = NULL;
 
    // If the list is empty, make the new node the head
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
 
    // Otherwise, traverse to the last node
    while (last->next != NULL)
        last = last->next;
 
    // Link the last node to the new node
    last->next = new_node;
}
 
// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}
 
// Main function
int main() {
    struct Node* head = NULL;
 
    // Insert elements at the end
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
 
    // Print the linked list
    printf("Linked List: ");
    printList(head);
 
    return 0;
}

Output

Linked List: 10 -> 20 -> 30 -> NULL

C++ Program: Insert Node at the End
#include <iostream>
using namespace std;
 
// Define the structure for a node
class Node {
public:
    int data;
    Node* next;
 
    Node(int value) {
        data = value;
        next = nullptr;
    }
};
 
// Function to insert a node at the end
void insertAtEnd(Node*& head, int value) {
    Node* newNode = new Node(value);
 
    if (head == nullptr) {
        head = newNode;
        return;
    }
 
    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
 
    temp->next = newNode;
}
 
// Function to print the linked list
void printList(Node* head) {
    while (head != nullptr) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}
 
// Main function
int main() {
    Node* head = nullptr;
 
    // Insert elements at the end
    insertAtEnd(head, 10);
    insertAtEnd(head, 20);
    insertAtEnd(head, 30);
 
    // Print the linked list
    cout << "Linked List: ";
    printList(head);
 
    return 0;
}

Output

Linked List: 10 -> 20 -> 30 -> NULL

Java Program: Insert Node at the End
class Node {
    int data;
    Node next;
 
    // Constructor
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
 
public class LinkedList {
    Node head;
 
    // Function to insert a node at the end
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
 
        if (head == null) {
            head = newNode;
            return;
        }
 
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
 
        temp.next = newNode;
    }
 
    // Function to print the linked list
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }
 
    // Main method
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
 
        // Inserting elements at the end
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
 
        // Printing the linked list
        System.out.print("Linked List: ");
        list.printList();
    }
}

Output

Linked List: 10 -> 20 -> 30 -> NULL

Python Program: Insert Node at the End
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    # Function to insert at the end
    def insert_at_end(self, data):
        new_node = Node(data)
 
        if not self.head:
            self.head = new_node
            return
 
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
 
        last_node.next = new_node
 
    # Function to print the linked list
    def print_list(self):
        temp = self.head
        while temp:
            print(temp.data, end=" -> ")
            temp = temp.next
        print("NULL")
 
# Main code
ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
 
print("Linked List:", end=" ")
ll.print_list()

Output

Linked List: 10 -> 20 -> 30 -> NULL

Insert at a specific position - C / C++ / Java / Python

🔹 C Program to insert node at a specific position

🔹 C++ Program to insert node at the end

🔹 Java Program to insert node at the end

🔹 Python Program to insert node at the end

C C++ Java Python

C Program: Insert Node at Specific Position
#include <stdio.h>
#include <stdlib.h>
 
// Define the structure for a node
struct Node {
    int data;
    struct Node* next;
};
 
// Function to insert a node at a specific position
void insertAtPosition(struct Node** head_ref, int position, int new_data) {
    // Allocate memory for new node
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    struct Node* temp = *head_ref;
 
    new_node->data = new_data;
 
    // If the position is 0, insert at the beginning
    if (position == 0) {
        new_node->next = *head_ref;
        *head_ref = new_node;
        return;
    }
 
    // Traverse the list to find the node just before the position
    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }
 
    // If the position is more than the number of nodes, do nothing
    if (temp == NULL) {
        printf("Position is greater than the length of the list\n");
        return;
    }
 
    // Make the next of new node point to the next of current node
    new_node->next = temp->next;
 
    // Now make the current node point to the new node
    temp->next = new_node;
}
 
// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}
 
// Main function
int main() {
    struct Node* head = NULL;
 
    // Insert elements at the beginning
    insertAtPosition(&head, 0, 10);  // Insert 10 at position 0
    insertAtPosition(&head, 1, 20);  // Insert 20 at position 1
    insertAtPosition(&head, 1, 15);  // Insert 15 at position 1
 
    // Print the linked list
    printf("Linked List: ");
    printList(head);
 
    return 0;
}

Output

Linked List: 10 -> 15 -> 20 -> NULL

C++ Program: Insert Node at Specific Position
 
#include <iostream>
using namespace std;
 
// Define the structure for a node
class Node {
public:
    int data;
    Node* next;
 
    Node(int value) {
        data = value;
        next = nullptr;
    }
};
 
class LinkedList {
public:
    Node* head;
 
    LinkedList() {
        head = nullptr;
    }
 
    // Function to insert a node at a specific position
    void insertAtPosition(int position, int value) {
        Node* newNode = new Node(value);
 
        // If inserting at the head (position 0)
        if (position == 0) {
            newNode->next = head;
            head = newNode;
            return;
        }
 
        Node* temp = head;
        for (int i = 0; temp != nullptr && i < position - 1; i++) {
            temp = temp->next;
        }
 
        // If the position is greater than the number of nodes, print an error
        if (temp == nullptr) {
            cout << "Position out of bounds" << endl;
            return;
        }
 
        newNode->next = temp->next;
        temp->next = newNode;
    }
 
    // Function to print the linked list
    void printList() {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }
};
 
// Main function
int main() {
    LinkedList list;
 
    // Insert elements at specific positions
    list.insertAtPosition(0, 10); // Insert 10 at position 0
    list.insertAtPosition(1, 20); // Insert 20 at position 1
    list.insertAtPosition(1, 15); // Insert 15 at position 1 (between 10 and 20)
 
    // Print the linked list
    cout << "Linked List: ";
    list.printList();
 
    return 0;
}

Output

Linked List: 10 -> 15 -> 20 -> NULL

Java Program: Insert Node at Specific Position
 
class Node {
    int data;
    Node next;
 
    // Constructor to create a new node
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
 
public class LinkedList {
    Node head;
 
    // Function to insert a node at a specific position
    public void insertAtPosition(int position, int data) {
        Node newNode = new Node(data);
 
        // If inserting at the head (position 0)
        if (position == 0) {
            newNode.next = head;
            head = newNode;
            return;
        }
 
        Node temp = head;
        // Traverse to the node before the specified position
        for (int i = 0; temp != null && i < position - 1; i++) {
            temp = temp.next;
        }
 
        // If position is greater than the number of nodes, print an error
        if (temp == null) {
            System.out.println("Position out of bounds");
            return;
        }
 
        // Insert the new node at the specific position
        newNode.next = temp.next;
        temp.next = newNode;
    }
 
    // Function to print the linked list
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }
 
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
 
        // Insert elements at specific positions
        list.insertAtPosition(0, 10);  // Insert 10 at position 0
        list.insertAtPosition(1, 20);  // Insert 20 at position 1
        list.insertAtPosition(1, 15);  // Insert 15 at position 1 (between 10 and 20)
 
        // Print the linked list
        System.out.print("Linked List: ");
        list.printList();
    }
}

Output

Linked List: 10 -> 15 -> 20 -> NULL

Python Program: Insert Node at Specific Position
 
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    # Function to insert at a specific position
    def insert_at_position(self, position, data):
        new_node = Node(data)
 
        # If inserting at the head (position 0)
        if position == 0:
            new_node.next = self.head
            self.head = new_node
            return
 
        temp = self.head
        # Traverse to the node before the specified position
        for _ in range(position - 1):
            if temp is None:
                print("Position out of bounds")
                return
            temp = temp.next
 
        # Insert the new node at the specific position
        new_node.next = temp.next
        temp.next = new_node
 
    # Function to print the linked list
    def print_list(self):
        temp = self.head
        while temp:
            print(temp.data, end=" -> ")
            temp = temp.next
        print("NULL")
 
# Main code
ll = LinkedList()
ll.insert_at_position(0, 10)  # Insert 10 at position 0
ll.insert_at_position(1, 20)  # Insert 20 at position 1
ll.insert_at_position(1, 15)  # Insert 15 at position 1 (between 10 and 20)
 
print("Linked List: ", end="")
ll.print_list()

Output

Linked List: 10 -> 15 -> 20 -> NULL

Explanation:

10 is inserted at position 0 (head).
20 is inserted at position 1.
Then 15 is inserted at position 1, between 10 and 20.

1️⃣ Deletion in Linked List

We can delete a node from a singly linked list in three major cases:

Deleting the head node (the first node).
Deleting a node from the middle (i.e., after the head node).
Deleting the last node.

Deletion in Singly Linked List - C / C++ / Java / Python

🔹 C Program to Delete in Singly Linked List

🔹 C++ Program to Delete in Singly Linked List

🔹 Java Program to Delete in Singly Linked List

🔹 Python Program to Delete in Singly Linked List

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
 
// Define the structure for a node
struct Node {
    int data;
    struct Node* next;
};
 
 
// Function to insert a node at the end
void insertAtEnd(struct Node** head_ref, int new_data) {
    // Create a new node
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    struct Node* last = *head_ref;
 
    new_node->data = new_data;
    new_node->next = NULL;
 
    // If the list is empty, make the new node the head
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
 
    // Otherwise, traverse to the last node
    while (last->next != NULL)
        last = last->next;
 
    // Link the last node to the new node
    last->next = new_node;
}
 
 
// Function to delete the first node
void deleteFirst(struct Node** head_ref) {
    if (*head_ref == NULL) {
        printf("List is empty.\n");
        return;
    }
    struct Node* temp = *head_ref;
    *head_ref = (*head_ref)->next;
    free(temp);
}
 
// Function to delete a node at a specific position
void deleteAtPosition(struct Node** head_ref, int position) {
    if (*head_ref == NULL) {
        printf("List is empty.\n");
        return;
    }
 
    struct Node* temp = *head_ref;
 
    // If the position is 0, delete the head node
    if (position == 0) {
        *head_ref = temp->next;
        free(temp);
        return;
    }
 
    // Traverse to the node just before the position
    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }
 
    // If position is greater than the number of nodes
    if (temp == NULL || temp->next == NULL) {
        printf("Position out of bounds.\n");
        return;
    }
 
    struct Node* next_node = temp->next->next;
    free(temp->next); // Free memory of the node to be deleted
    temp->next = next_node;
}
 
// Function to delete the last node
void deleteLast(struct Node** head_ref) {
    if (*head_ref == NULL) {
        printf("List is empty.\n");
        return;
    }
 
    struct Node* temp = *head_ref;
 
    // If there is only one node
    if (temp->next == NULL) {
        free(temp);
        *head_ref = NULL;
        return;
    }
 
    // Traverse to the second last node
    while (temp->next != NULL && temp->next->next != NULL) {
        temp = temp->next;
    }
 
    free(temp->next);
    temp->next = NULL;
}
 
// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}
 
// Main function
int main() {
    struct Node* head = NULL;
 
    // Adding elements to the list
    // (For simplicity, assuming insertAtEnd and insertAtPosition are already defined)
 
    // Inserting nodes (example)
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
 
    printf("Original List: ");
    printList(head);
 
    // Deleting first node
    deleteFirst(&head);
    printf("After Deleting First Node: ");
    printList(head);
 
    // Deleting node at position 1
    deleteAtPosition(&head, 1);
    printf("After Deleting Node at Position 1: ");
    printList(head);
 
    // Deleting last node
    deleteLast(&head);
    printf("After Deleting Last Node: ");
    printList(head);
 
    return 0;
}

Output

Original List: 10 -> 20 -> 30 -> 40 -> NULL

After Deleting First Node: 20 -> 30 -> 40 -> NULL

After Deleting Node at Position 1: 20 -> 40 -> NULL

After Deleting Last Node: 20 -> NULL

#include <iostream>
using namespace std;
 
// Define the structure for a node
class Node {
public:
    int data;
    Node* next;
 
    Node(int value) {
        data = value;
        next = nullptr;
    }
};
 
class LinkedList {
public:
    Node* head;
 
    LinkedList() {
        head = nullptr;
    }
 
    // Function to delete the first node
    void deleteFirst() {
        if (head == nullptr) {
            cout << "List is empty." << endl;
            return;
        }
 
        Node* temp = head;
        head = head->next;
        delete temp;
    }
 
    // Function to delete a node at a specific position
    void deleteAtPosition(int position) {
        if (head == nullptr) {
            cout << "List is empty." << endl;
            return;
        }
 
        Node* temp = head;
 
        // If position is 0, delete the head node
        if (position == 0) {
            head = temp->next;
            delete temp;
            return;
        }
 
        // Traverse to the node just before the position
        for (int i = 0; temp != nullptr && i < position - 1; i++) {
            temp = temp->next;
        }
 
        // If position is greater than the number of nodes
        if (temp == nullptr || temp->next == nullptr) {
            cout << "Position out of bounds." << endl;
            return;
        }
 
        Node* nodeToDelete = temp->next;
        temp->next = temp->next->next;
        delete nodeToDelete;
    }
 
    // Function to delete the last node
    void deleteLast() {
        if (head == nullptr) {
            cout << "List is empty." << endl;
            return;
        }
 
        Node* temp = head;
 
        // If there is only one node
        if (temp->next == nullptr) {
            delete temp;
            head = nullptr;
            return;
        }
 
        // Traverse to the second last node
        while (temp->next != nullptr && temp->next->next != nullptr) {
            temp = temp->next;
        }
 
        delete temp->next;
        temp->next = nullptr;
    }
 
    // Function to print the linked list
    void printList() {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }
};
 
int main() {
    LinkedList list;
 
    // Insert nodes at the end (you can implement a similar insertAtEnd function)
    list.head = new Node(10);
    list.head->next = new Node(20);
    list.head->next->next = new Node(30);
    list.head->next->next->next = new Node(40);
 
    cout << "Original List: ";
    list.printList();
 
    // Deleting the first node
    list.deleteFirst();
    cout << "After Deleting First Node: ";
    list.printList();
 
    // Deleting node at position 1
    list.deleteAtPosition(1);
    cout << "After Deleting Node at Position 1: ";
    list.printList();
 
    // Deleting the last node
    list.deleteLast();
    cout << "After Deleting Last Node: ";
    list.printList();
 
    return 0;
}

Output

Original List: 10 -> 20 -> 30 -> 40 -> NULL

After Deleting First Node: 20 -> 30 -> 40 -> NULL

After Deleting Node at Position 1: 20 -> 40 -> NULL

After Deleting Last Node: 20 -> NULL

class Node {
    int data;
    Node next;
 
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
 
class LinkedList {
    Node head;
 
    // Insert node at the end (for demonstration purpose)
    void insertAtEnd(int data) {
        Node newNode = new Node(data);
 
        if (head == null) {
            head = newNode;
            return;
        }
 
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
 
        temp.next = newNode;
    }
 
    // Delete the first node
    void deleteFirst() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        head = head.next;
    }
 
    // Delete node at specific position
    void deleteAtPosition(int position) {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
 
        if (position == 0) {
            deleteFirst();
            return;
        }
 
        Node temp = head;
        for (int i = 0; i < position - 1 && temp != null; i++) {
            temp = temp.next;
        }
 
        if (temp == null || temp.next == null) {
            System.out.println("Position out of bounds.");
            return;
        }
 
        temp.next = temp.next.next;
    }
 
    // Delete the last node
    void deleteLast() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
 
        if (head.next == null) {
            head = null;
            return;
        }
 
        Node temp = head;
        while (temp.next.next != null) {
            temp = temp.next;
        }
 
        temp.next = null;
    }
 
    // Print the linked list
    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }
}
 
public class LinkedListDeletion {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
 
        // Inserting nodes
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        list.insertAtEnd(40);
 
        System.out.println("Original List:");
        list.printList();
 
        // Deleting first node
        list.deleteFirst();
        System.out.println("After Deleting First Node:");
        list.printList();
 
        // Deleting node at position 1 (second node in list)
        list.deleteAtPosition(1);
        System.out.println("After Deleting Node at Position 1:");
        list.printList();
 
        // Deleting last node
        list.deleteLast();
        System.out.println("After Deleting Last Node:");
        list.printList();
    }
}

Output

Original List:
10 -> 20 -> 30 -> 40 -> NULL
After Deleting First Node:
20 -> 30 -> 40 -> NULL
After Deleting Node at Position 1:
20 -> 40 -> NULL
After Deleting Last Node:
20 -> NULL

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    # Function to delete the first node
    def delete_first(self):
        if self.head is None:
            print("List is empty.")
            return
        self.head = self.head.next
 
    # Function to delete a node at a specific position
    def delete_at_position(self, position):
        if self.head is None:
            print("List is empty.")
            return
 
        temp = self.head
 
        # If position is 0, delete the head node
        if position == 0:
            self.head = temp.next
            return
 
        # Traverse to the node before the specified position
        for _ in range(position - 1):
            if temp is None:
                print("Position out of bounds")
                return
            temp = temp.next
 
        # If position is more than the number of nodes
        if temp is None or temp.next is None:
            print("Position out of bounds")
            return
 
        # Skip the node to be deleted
        temp.next = temp.next.next
 
    # Function to delete the last node
    def delete_last(self):
        if self.head is None:
            print("List is empty.")
            return
 
        temp = self.head
 
        # If there is only one node
        if temp.next is None:
            self.head = None
            return
 
        # Traverse to the second last node
        while temp.next is not None and temp.next.next is not None:
            temp = temp.next
 
        temp.next = None
 
    # Function to print the linked list
    def print_list(self):
        temp = self.head
        while temp:
            print(temp.data, end=" -> ")
            temp = temp.next
        print("NULL")
 
# Main code
ll = LinkedList()
ll.head = Node(10)
ll.head.next = Node(20)
ll.head.next.next = Node(30)
ll.head.next.next.next = Node(40)
 
print("Original List: ", end="")
ll.print_list()
 
# Deleting the first node
ll.delete_first()
print("After Deleting First Node: ", end="")
ll.print_list()
 
# Deleting node at position 1
ll.delete_at_position(1)
print("After Deleting Node at Position 1: ", end="")
ll.print_list()
 
# Deleting the last node
ll.delete_last()
print("After Deleting Last Node: ", end="")
ll.print_list()

Output

Original List: 10 -> 20 -> 30 -> 40 -> NULL

After Deleting First Node: 20 -> 30 -> 40 -> NULL

After Deleting Node at Position 1: 20 -> 40 -> NULL

After Deleting Last Node: 20 -> NULL

✅ Traversal in Singly Linked List

📘 What is Traversal?

Traversal means visiting each node in the linked list exactly once to perform some operation, such as displaying data, counting nodes, or searching for a value.

🔁 Algorithm:

Start from the head node.
While the current node is not null:

Print or process the current node's data.
Move to the next node (current = current.next).

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};
 
void traverse(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
 
int main() {
    struct Node* head = malloc(sizeof(struct Node));
    struct Node* second = malloc(sizeof(struct Node));
    struct Node* third = malloc(sizeof(struct Node));
 
    head->data = 10; head->next = second;
    second->data = 20; second->next = third;
    third->data = 30; third->next = NULL;
 
    printf("Linked List: ");
    traverse(head);
    return 0;
}

Output

Linked List: 10 -> 20 -> 30 -> NULL

#include <iostream>
using namespace std;
 
struct Node {
    int data;
    Node* next;
};
 
void traverse(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " -> ";
        current = current->next;
    }
    cout << "NULL" << endl;
}
 
int main() {
    Node* head = new Node{10, nullptr};
    Node* second = new Node{20, nullptr};
    Node* third = new Node{30, nullptr};
 
    head->next = second;
    second->next = third;
 
    cout << "Linked List: ";
    traverse(head);
    return 0;
}

Output

Linked List: 10 -> 20 -> 30 -> NULL

class Node {
    int data;
    Node next;
 
    Node(int data) {
        this.data = data;
    }
}
 
public class LinkedListTraversal {
    public static void traverse(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("NULL");
    }
 
    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);
 
        System.out.print("Linked List: ");
        traverse(head);
    }
}

Output

Linked List: 10 -> 20 -> 30 -> NULL

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
def traverse(head):
    current = head
    while current:
        print(current.data, end=" -> ")
        current = current.next
    print("NULL")
 
# Creating the list
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
 
print("Linked List:")
traverse(head)

Output

Linked List: 10 -> 20 -> 30 -> NULL

✅ Search Operation in Singly Linked List

📘 What is Searching?

Searching in a singly linked list means traversing the list to check whether a specific value exists or not.

✅ Algorithm:

Start from the head node.
Compare each node’s data with the target value.
If a match is found, return the position/index.
If the end of the list is reached and no match is found, return "not found".

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};
 
int search(struct Node* head, int key) {
    int position = 0;
    while (head != NULL) {
        if (head->data == key)
            return position;
        head = head->next;
        position++;
    }
    return -1;
}
 
int main() {
    struct Node* head = malloc(sizeof(struct Node));
    head->data = 10;
    head->next = malloc(sizeof(struct Node));
    head->next->data = 20;
    head->next->next = malloc(sizeof(struct Node));
    head->next->next->data = 30;
    head->next->next->next = NULL;
 
    int key = 20;
    int pos = search(head, key);
 
    if (pos != -1)
        printf("Element %d found at position %d\n", key, pos);
    else
        printf("Element %d not found\n", key);
 
    return 0;
}

Output

Element 20 found at position 1

#include <iostream>
using namespace std;
 
struct Node {
    int data;
    Node* next;
};
 
int search(Node* head, int key) {
    int position = 0;
    while (head != nullptr) {
        if (head->data == key)
            return position;
        head = head->next;
        position++;
    }
    return -1;
}
 
int main() {
    Node* head = new Node{10, nullptr};
    head->next = new Node{20, nullptr};
    head->next->next = new Node{30, nullptr};
 
    int key = 20;
    int pos = search(head, key);
 
    if (pos != -1)
        cout << "Element " << key << " found at position " << pos << endl;
    else
        cout << "Element " << key << " not found" << endl;
 
    return 0;
}

Output

Element 20 found at position 1

class Node {
    int data;
    Node next;
 
    Node(int data) {
        this.data = data;
    }
}
 
public class LinkedListSearch {
    public static int search(Node head, int key) {
        int position = 0;
        while (head != null) {
            if (head.data == key)
                return position;
            head = head.next;
            position++;
        }
        return -1;
    }
 
    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);
 
        int key = 20;
        int pos = search(head, key);
 
        if (pos != -1)
            System.out.println("Element " + key + " found at position " + pos);
        else
            System.out.println("Element " + key + " not found");
    }
}

Output

Element 20 found at position 1

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
def search(head, key):
    position = 0
    while head:
        if head.data == key:
            return position
        head = head.next
        position += 1
    return -1
 
# Create the linked list
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
 
key = 20
pos = search(head, key)
 
if pos != -1:
    print(f"Element {key} found at position {pos}")
else:
    print(f"Element {key} not found")

Output

Element 20 found at position 1

✅ Reversing a Singly Linked List

📘 What is Reversal?

Reversing a singly linked list means changing the direction of pointers so that the last node becomes the first, and the first becomes the last.

✅ Algorithm:

Initialize three pointers: prev = NULL, curr = head, next = NULL.
Iterate through the list:

Save next node: next = curr->next
Reverse current node’s pointer: curr->next = prev
Move prev and curr one step forward.

Update head = prev

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};
 
void reverse(struct Node** head) {
    struct Node* prev = NULL;
    struct Node* curr = *head;
    struct Node* next = NULL;
 
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    *head = prev;
}
 
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}
 
int main() {
    struct Node* head = malloc(sizeof(struct Node));
    head->data = 1;
    head->next = malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->next = malloc(sizeof(struct Node));
    head->next->next->data = 3;
    head->next->next->next = NULL;
 
    printf("Original List: ");
    printList(head);
 
    reverse(&head);
 
    printf("Reversed List: ");
    printList(head);
    return 0;
}

Output

Original List: 1 -> 2 -> 3 -> NULL
Reversed List: 3 -> 2 -> 1 -> NULL

 #include <iostream>
using namespace std;
 
struct Node {
    int data;
    Node* next;
};
 
void reverse(Node*& head) {
    Node* prev = nullptr;
    Node* curr = head;
    Node* next = nullptr;
 
    while (curr != nullptr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
}
 
void printList(Node* head) {
    while (head != nullptr) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "NULL\n";
}
 
int main() {
    Node* head = new Node{1, nullptr};
    head->next = new Node{2, nullptr};
    head->next->next = new Node{3, nullptr};
 
    cout << "Original List: ";
    printList(head);
 
    reverse(head);
 
    cout << "Reversed List: ";
    printList(head);
    return 0;
}

Output

Original List: 1 -> 2 -> 3 -> NULL
Reversed List: 3 -> 2 -> 1 -> NULL

 class Node {
    int data;
    Node next;
 
    Node(int data) {
        this.data = data;
    }
}
 
public class ReverseLinkedList {
    public static Node reverse(Node head) {
        Node prev = null, curr = head, next;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
 
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data + " -> ");
            head = head.next;
        }
        System.out.println("NULL");
    }
 
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
 
        System.out.print("Original List: ");
        printList(head);
 
        head = reverse(head);
 
        System.out.print("Reversed List: ");
        printList(head);
    }
}

Output

Original List: 1 -> 2 -> 3 -> NULL
Reversed List: 3 -> 2 -> 1 -> NULL

 class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
def reverse(head):
    prev = None
    curr = head
    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    return prev
 
def print_list(head):
    while head:
        print(head.data, end=" -> ")
        head = head.next
    print("NULL")
 
# Create list
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
 
print("Original List:")
print_list(head)
 
head = reverse(head)
 
print("Reversed List:")
print_list(head)

Output

Original List: 1 -> 2 -> 3 -> NULL
Reversed List: 3 -> 2 -> 1 -> NULL