Open In App

Singly Linked List Tutorial

Last Updated : 14 Jun, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

What is Singly Linked List?

A singly linked list is a fundamental data structure in computer science and programming. It is a collection of nodes where each node contains a data field and a reference (link) to the next node in the sequence. The last node in the list points to null, indicating the end of the list. This linear data structure allows for efficient insertion and deletion operations, making it a popular choice for various applications.

Understanding Node Structure:

In a singly linked list, each node consists of two parts: data and a pointer to the next node. The data part stores the actual information, while the pointer (or reference) part stores the address of the next node in the sequence. This structure allows nodes to be dynamically linked together, forming a chain-like sequence.

Singly-Linked-List

Singly Linked List

In this representation, each box represents a node, with an arrow indicating the link to the next node. The last node points to NULL, indicating the end of the list.

Node Definition:

In most programming languages, a node in a singly linked list is typically defined using a class or a struct. Here’s an example of a basic node structure in C++:

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

In this example, the Node struct contains an integer data field (data) to store the information and a pointer to another Node (next) to establish the link to the next node in the list.

Operations on Singly Linked List:

  • Traversal
  • Searching
  • Length
  • Insertion:
    • Insert at the beginning
    • Insert at the end
    • Insert at a specific position
  • Deletion:
    • Delete from the beginning
    • Delete from the end
    • Delete a specific node

Let’s go through each of the operations mentioned above, one by one.

Traversal in Singly Linked List:

Traversal involves visiting each node in the linked list and performing some operation on the data. A simple traversal function would print or process the data of each node.

Steps for Traversal in Singly Linked List:

  • Initialize a pointer current to the head of the list.
  • Use a while loop to iterate through the list until the current pointer reaches nullptr.
  • Inside the loop, print the data of the current node and move the current pointer to the next node.

Below is the implementation of the above approach:

C++
#include <iostream>

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

// Function to traverse and print the elements of the linked
// list
void traverseLinkedList(Node* head)
{
    // Start from the head of the linked list
    Node* current = head;

    // Traverse the linked list until reaching the end
    // (nullptr)
    while (current != nullptr) {
        // Print the data of the current node
        std::cout << current->data << " ";

        // Move to the next node
        current = current->next;
    }

    std::cout << std::endl;
}

// Example usage:
// Assuming the linked list is already constructed

int main()
{
    // Create nodes
    Node* head = new Node{ 1 };
    Node* second = new Node{ 2 };
    Node* third = new Node{ 3 };

    // Connect nodes
    head->next = second;
    second->next = third;

    // Call the traverseLinkedList function to print the
    // linked list elements
    traverseLinkedList(head);

    // Memory cleanup (free allocated memory)
    delete head;
    delete second;
    delete third;

    return 0;
}
Java
// Define the Node class
class Node {
    int data;
    Node next;

    public Node(int data)
    {
        this.data = data;
        this.next = null;
    }
}

// Define a LinkedList class to encapsulate operations
public class LinkedList {
    // Function to traverse and print the elements of the
    // linked list
    public static void traverseLinkedList(Node head)
    {
        // Start from the head of the linked list
        Node current = head;

        // Traverse the linked list until reaching the end
        // (null)
        while (current != null) {
            // Print the data of the current node
            System.out.print(current.data + " ");

            // Move to the next node
            current = current.next;
        }

        System.out.println();
    }

    // Main method for example usage
    public static void main(String[] args)
    {
        // Create nodes
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        // Connect nodes
        head.next = second;
        second.next = third;

        // Call the traverseLinkedList function to print the
        // linked list elements
        traverseLinkedList(head);
    }
}
Python
# Define the Node class for the linked list
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Function to traverse and print the elements of the linked list


def traverse_linked_list(head):
    # Start from the head of the linked list
    current = head

    # Traverse the linked list until reaching the end (None)
    while current is not None:
        # Print the data of the current node followed by a space
        print(current.data),

        # Move to the next node
        current = current.next

    print()  # Print a new line after traversing the linked list

# Example usage:
# Assuming the linked list is already constructed


# Create nodes
head = Node(1)
second = Node(2)
third = Node(3)

# Connect nodes
head.next = second
second.next = third

# Call the traverse_linked_list function to print the linked list elements
traverse_linked_list(head)
JavaScript
// Assuming the Node class is defined as follows:
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

// Function to traverse and print the elements of the linked list
function traverseLinkedList(head) {
    // Start from the head of the linked list
    let current = head;

    // Traverse the linked list until reaching the end (null)
    while (current !== null) {
        // Print the data of the current node
        console.log(current.data + " ");

        // Move to the next node
        current = current.next;
    }

    console.log();
}

// Example usage:
// Assuming the linked list is already constructed

// Create nodes
let head = new Node(1);
let second = new Node(2);
let third = new Node(3);

// Connect nodes
head.next = second;
second.next = third;

// Call the traverseLinkedList function to print the linked list elements
traverseLinkedList(head);

Output
1 2 3 

Searching in Singly Linked List:

Searching in a Singly Linked List refers to the process of looking for a specific element or value within the elements of the linked list.

Steps for Searching in Singly Linked List:

  • Initialize a pointer head to the starting node of the Linked List.
  • Use a while loop to traverse the Linked List until the end is reached (i.e., head becomes nullptr).
  • Inside the loop, check if the current node’s data is equal to the target value.
    • If true, return true indicating that the value is found in the Linked List.
    • If false, move to the next node by updating head to point to the next node in the list.
  • If the loop completes without finding the value, return false indicating that the value is not present in the Linked List.
C++
// Function to search for a value in the Linked List
bool searchLinkedList(Node* head, int target) {
    // Traverse the Linked List
    while (head != nullptr) {
        // Check if the current node's data matches the target value
        if (head-&gt;data == target) {
            return true;  // Value found
        }
        // Move to the next node
        head = head-&gt;next;
    }
    
    return false;  // Value not found
}

Finding Length in Singly Linked List:

Steps for finding length in Singly Linked List:

  • Initialize a counter variable length to 0.
  • Create a pointer current and set it to the head of the linked list.
  • Use a while loop to iterate through the linked list:
    • Increment the length counter.
    • Move the current pointer to the next node in the list.
  • After the loop, return the final value of the length variable.

Below is the implementation of the above approach:

C++
#include <bits/stdc++.h>
using namespace std;

// Define the Node struct
struct Node {
    int data;
    Node* next;
};

// Function to find the length of the linked list
int findLength(Node* head)
{
    // Initialize a counter for the length
    int length = 0;

    // Start from the head of the list
    Node* current = head;

    // Traverse the list and increment the length for each
    // node
    while (current != nullptr) {
        length++;
        current = current->next;
    }

    // Return the final length of the linked list
    return length;
}
Java
public class LinkedList {
    // Define the Node class
    static class Node {
        int data;
        Node next;

        // Constructor to create a new node
        Node(int data)
        {
            this.data = data;
            this.next = null;
        }
    }

    Node head; // head of list

    // Function to find the length of the linked list
    public int findLength()
    {
        int length
            = 0; // Initialize a counter for the length
        Node current
            = head; // Start from the head of the list

        // Traverse the list and increment the length for
        // each node
        while (current != null) {
            length++;
            current = current.next;
        }

        // Return the final length of the linked list
        return length;
    }

    // Helper function to add new node at the front of the
    // list
    public void push(int newData)
    {
        Node newNode
            = new Node(newData); // allocate the Node and
                                 // put in the data
        newNode.next
            = head; // make next of new Node as head
        head = newNode; // move the head to point to the new
                        // Node
    }

    // Main method to create and manipulate a linked list
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();

        // Adding elements to the list
        llist.push(1);
        llist.push(3);
        llist.push(5);

        // Printing the length of the list
        System.out.println("Length of the linked list is: "
                           + llist.findLength());
    }
}
Python
# Define the Node class
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Define the LinkedList class


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

    # Function to find the length of the linked list
    def findLength(self):
        length = 0
        current = self.head

        # Traverse the list and increment the length for each node
        while current:
            length += 1
            current = current.next

        # Return the final length of the linked list
        return length

    # Helper function to add new node at the front of the list
    def push(self, newData):
        newNode = Node(newData)
        newNode.next = self.head
        self.head = newNode


# Main method to create and manipulate a linked list
if __name__ == "__main__":
    llist = LinkedList()

    # Adding elements to the list
    llist.push(1)
    llist.push(3)
    llist.push(5)

    # Printing the length of the list
    print("Length of the linked list is:", llist.findLength())
JavaScript
class LinkedList {
    constructor(data) {
        this.data = data;
        this.next = null;
    }

    findLength() {
        let length = 1; // Start from 1 since the current instance is already counted
        let current = this.next; // Start from the next node

        while (current !== null) {
            length++;
            current = current.next;
        }

        return length;
    }

    push(newData) {
        const newNode = new LinkedList(newData);
        newNode.next = this.next;
        this.next = newNode;
    }
}

const llist = new LinkedList(1); // Initialize the linked list with a node

// Adding elements to the list
llist.push(3);
llist.push(5);

// Printing the length of the list
console.log("Length of the linked list is: " + llist.findLength());

Insertion in Singly Linked List:

Insertion is a fundamental operation in linked lists that involves adding a new node to the list. There are several scenarios for insertion:

a. Insertion at the Beginning of Singly Linked List:

Insertion-at-the-Beginning-of-Singly-Linked-List

Insertion at the Beginning of Singly Linked List

Approach: 

To insert a node at the start/beginning/front of a Linked List, we need to:

  • Make the first node of Linked List linked to the new node
  • Remove the head from the original first node of Linked List
  • Make the new node as the Head of the Linked List.

Below is the implementation of the approach:

C++
// Given a reference (pointer to pointer)
// to the head of a list and an int,
// inserts a new node on the front of
// the list.
void insertionAtBeginning(Node** head_ref, int new_data)
{
    // 1. Allocate node
    Node* new_node = new Node();

    // 2. Put in the data
    new_node->data = new_data;

    // 3. Make next of new node as head
    new_node->next = (*head_ref);

    // 4. Move the head to point to
    // the new node
    (*head_ref) = new_node;
}
C
/* Given a reference (pointer to pointer) to the head of a
list
and an int, inserts a new node on the front of the list.
*/
void push(struct Node** head_ref, int new_data)
{
    /* 1. allocate node */
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

    /* 2. put in the data */
    new_node->data = new_data;

    /* 3. Make next of new node as head */
    new_node->next = (*head_ref);

    /* 4. move the head to point to the new node */
    (*head_ref) = new_node;
}
Java
/* This function is in LinkedList class. Inserts a
new Node at front of the list. This method is
defined inside LinkedList class shown above */
public void push(int new_data)
{
    /* 1 &amp; 2: Allocate the Node &amp;
            Put in the data*/
    Node new_node = new Node(new_data);

    /* 3. Make next of new Node as head */
    new_node.next = head;

    /* 4. Move the head to point to new Node */
    head = new_node;
}
Python
# This function is in LinkedList class
# Function to insert a new node at the beginning
def push(self, new_data):

    # 1 &amp; 2: Allocate the Node &amp;
    # Put in the data
    new_node = Node(new_data)

    # 3. Make next of new Node as head
    new_node.next = self.head

    # 4. Move the head to point to new Node
    self.head = new_node
C#
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
    /* 1 &amp; 2: Allocate the Node &amp;
            Put in the data*/
    Node new_node = new Node(new_data);

    /* 3. Make next of new Node as head */
    new_node.next = head;

    /* 4. Move the head to point to new Node */
    head = new_node;
}
Javascript
/* This function is in LinkedList class. Inserts a
new Node at front of the list. This method is 
defined inside LinkedList class shown above */

function push(new_data) {
    /* 1 & 2: Allocate the Node & Put in the data*/
    var new_node = new Node(new_data);

    /* 3. Make next of new Node as head */
    new_node.next = head;

    /* 4. Move the head to point to new Node */
    head = new_node;
}

b. Insertion at the End of Singly Linked List:

To insert a node at the end of the list, traverse the list until the last node is reached, and then link the new node to the current last node.-

Insertion-at-the-End-of-Singly-Linked-List

Insertion at the End of Singly Linked List

Approach: 

To insert a node at the end of a Linked List, we need to:

  • Go to the last node of the Linked List
  • Change the next pointer of last node from NULL to the new node
  • Make the next pointer of new node as NULL to show the end of Linked List

Below is the implementation of the approach:

C++
// Given a reference (pointer to pointer) to the head
// of a list and an int, appends a new node at the end
void insertionAtEnd(Node** head_ref, int new_data)
{
    // 1. allocate node
    Node* new_node = new Node(new_data);

    // Used in step 5
    Node* last = *head_ref;

    // 2. If the Linked List is empty,
    // then make the new node as head
    if (*head_ref == nullptr) {
        *head_ref = new_node;
        return;
    }

    // 3. Else traverse till the last node
    while (last->next != nullptr) {
        last = last->next;
    }

    // 4. Change the next of last node
    last->next = new_node;
}
C
/* Given a reference (pointer to pointer) to the head
of a list and an int, appends a new node at the end */
void append(struct Node** head_ref, int new_data)
{
    /* 1. allocate node */
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

    struct Node* last = *head_ref; /* used in step 5*/

    /* 2. put in the data */
    new_node->data = new_data;

    /* 3. This new node is going to be the last node, so
    make next of it as NULL*/
    new_node->next = NULL;

    /* 4. If the Linked List is empty, then make the new
    * node as head */
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    /* 5. Else traverse till the last node */
    while (last->next != NULL)
        last = last->next;

    /* 6. Change the next of last node */
    last->next = new_node;
    return;
}
Java
/* Appends a new node at the end. This method is
defined inside LinkedList class shown above */
public void append(int new_data) {
    /* 1. Allocate the Node &
    2. Put in the data
    3. Set next as null */
    Node new_node = new Node(new_data);

    /* 4. If the Linked List is empty, then make the
        new node as head */
    if (head == null) {
        head = new Node(new_data);
        return;
    }

    /* 5. This new node is going to be the last node, so
        make next of it as null */
    new_node.next = null;

    /* 6. Else traverse till the last node */
    Node last = head;
    while (last.next != null)
        last = last.next;

    /* 7. Change the next of last node */
    last.next = new_node;
    return;
}
Python
# This function is defined in Linked List class
# Appends a new node at the end. This method is
# defined inside LinkedList class shown above
def append(self, new_data):

        # 1. Create a new node
        # 2. Put in the data
        # 3. Set next as None
        new_node = Node(new_data)

        # 4. If the Linked List is empty, then make the
        # new node as head
        if self.head is None:
            self.head = new_node
            return

        # 5. Else traverse till the last node
        last = self.head
        while (last.next):
            last = last.next

        # 6. Change the next of last node
        last.next = new_node
C#
/* Appends a new node at the end. This method is
defined inside LinkedList class shown above */
public void append(int new_data)
{
    /* 1. Allocate the Node &amp;
    2. Put in the data
    3. Set next as null */
    Node new_node = new Node(new_data);

    /* 4. If the Linked List is empty,
    then make the new node as head */
    if (head == null) {
        head = new Node(new_data);
        return;
    }

    /* 4. This new node is going to be
    the last node, so make next of it as null */
    new_node.next = null;

    /* 5. Else traverse till the last node */
    Node last = head;
    while (last.next != null)
        last = last.next;

    /* 6. Change the next of last node */
    last.next = new_node;
    return;
}
Javascript
/* Appends a new node at the end. This method is
defined inside LinkedList class shown above */
function append(new_data)
{
    /* 1. Allocate the Node &amp;
    2. Put in the data
    3. Set next as null */
    var new_node = new Node(new_data);

    /* 4. If the Linked List is empty, then make the
        new node as head */
    if (head == null)
    {
        head = new Node(new_data);
        return;
    }

    /* 4. This new node is going to be the last node, so
        make next of it as null */
    new_node.next = null;

    /* 5. Else traverse till the last node */
    var last = head;
    while (last.next != null)
        last = last.next;

    /* 6. Change the next of last node */
    last.next = new_node;
    return;
}

c. Insertion at a Specific Position of the Singly Linked List:

To insert a node at a specific position, traverse the list to the desired position, link the new node to the next node, and update the links accordingly.

Insertion-at-a-Specific-Position-of-the-Singly-Linked-List

Insertion at a Specific Position of the Singly Linked List

Steps-by-step approach:

  • Create a new node (newNode) with the given value.
  • Check if the position is 0 or if the list is empty (head == nullptr).
    • If true, set newNode->next to the current head, and update head to newNode. The insertion is done at the beginning.
    • Return from the function.
  • If the position is not at the beginning:
    • Initialize a pointer current to the head of the list.
    • Traverse the list until reaching the node just before the specified position.
      • Move current to the next node in each iteration until position – 1 or the end of the list is reached.
  • Insert the newNode at the specified position:
    • Set newNode->next to current->next.
    • Update current->next to newNode.

Below is the implementation of the approach:

C++
#include <iostream>

struct Node {
    int data;
    Node* next;

    Node(int value) : data(value), next(nullptr) {}
};

Node* head = nullptr; // assuming head is a global variable

void insertAtPosition(int value, int position) {
    // Create a new node with the given data
    Node* newNode = new Node(value);

    // If position is 0 or the list is empty, insert at the beginning
    if (position == 0 || head == nullptr) {
        newNode->next = head;
        head = newNode;
        return;
    }

    // Traverse to the node just before the specified position
    Node* current = head;
    for (int i = 1; i < position && current->next != nullptr; ++i) {
        current = current->next;
    }

    // Insert the new node at the specified position
    newNode->next = current->next;
    current->next = newNode;
}

// Example usage:
// insertAtPosition(5, 2); // Inserts value 5 at position 2
Java
// Assuming the Node class is defined like this:
class Node {
    public int data;
    public Node next;

    public Node(int value) {
        this.data = value;
        this.next = null;
    }
}

// Declare the head pointer globally
Node head = null;

// Function to insert a new node at a specific position in the list
void insertAtPosition(int value, int position) {
    // Create a new node with the given data
    Node newNode = new Node(value);

    // If position is 0 or the list is empty, insert at the beginning
    if (position == 0 || head == null) {
        newNode.next = head;
        head = newNode;
        return;
    }

    // Traverse to the node just before the specified position
    Node current = head;
    for (int i = 1; i < position && current.next != null; ++i) {
        current = current.next;
    }

    // Insert the new node at the specified position
    newNode.next = current.next;
    current.next = newNode;
}
Python
# Class to represent a node
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# Function to insert a new node at a specific position in the list
def insertAtPosition(head, value, position):
    # Create a new node with the given data
    newNode = Node(value)

    # If position is 0 or the list is empty, insert at the beginning
    if position == 0 or head is None:
        newNode.next = head
        head = newNode
        return head

    # Traverse to the node just before the specified position
    current = head
    for i in range(1, position):
        if current.next is None:
            break
        current = current.next

    # Insert the new node at the specified position
    newNode.next = current.next
    current.next = newNode

    return head
JavaScript
// Assuming the Node class is defined like this:
class Node {
    constructor(value) {
        this.data = value;
        this.next = null;
    }
}

// Declare the head pointer globally
let head = null;

// Function to insert a new node at a specific position in the list
function insertAtPosition(value, position) {
    // Create a new node with the given data
    let newNode = new Node(value);

    // If position is 0 or the list is empty, insert at the beginning
    if (position === 0 || head === null) {
        newNode.next = head;
        head = newNode;
        return;
    }

    // Traverse to the node just before the specified position
    let current = head;
    for (let i = 1; i < position && current.next !== null; ++i) {
        current = current.next;
    }

    // Insert the new node at the specified position
    newNode.next = current.next;
    current.next = newNode;
}

Deletion in Singly Linked List:

Deletion involves removing a node from the linked list. Similar to insertion, there are different scenarios for deletion:

a. Deletion at the Beginning of Singly Linked List:

To delete the first node, update the head to point to the second node in the list.

Deletion-at-the-Beginning-of-Singly-Linked-List

Deletion at the Beginning of Singly Linked List

Steps-by-step approach:

  • Check if the linked list is empty (head == nullptr).
  • If the list is empty, print a message indicating that the list is empty, and return without performing any deletion.
  • If the list is not empty:
    • Store the current head node in a temporary variable (Node* temp = head).
    • Update the head to point to the next node (head = head->next).
    • Delete the old head node using delete temp

Below is the implementation of the approach:

C++
#include <iostream>

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

Node* head = nullptr; // assuming head is a global variable

void deleteAtBeginning() {
    // If the list is empty, do nothing
    if (head == nullptr) {
        std::cout << "List is empty. Cannot delete from the beginning." << std::endl;
        return;
    }

    // Store the current head in a temporary variable
    Node* temp = head;

    // Update the head to the next node
    head = head->next;

    // Delete the old head node
    delete temp;
}

void insertAtBeginning(int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = head;
    head = newNode;
}

void printList() {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

int main() {
    // Inserting nodes for testing
    insertAtBeginning(3);
    insertAtBeginning(2);
    insertAtBeginning(1);

    std::cout << "Initial List:" << std::endl;
    printList();

    // Deleting the node at the beginning
    deleteAtBeginning();

    std::cout << "List after deleting the node at the beginning:" << std::endl;
    printList();

    return 0;
}
Java
class Node {
    int data;
    Node next;

    // Constructor to create a new node
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedList {
    static Node head = null; // assuming head is a global variable

    // Method to delete the node at the beginning
    public static void deleteAtBeginning() {
        // If the list is empty, do nothing
        if (head == null) {
            System.out.println("List is empty. Cannot delete from the beginning.");
            return;
        }

        // Store the current head in a temporary variable
        Node temp = head;

        // Update the head to the next node
        head = head.next;

    }

    // Method to insert a node at the beginning (for testing purposes)
    public static void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Method to print the list (for testing purposes)
    public static void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Inserting nodes for testing
        insertAtBeginning(3);
        insertAtBeginning(2);
        insertAtBeginning(1);

        System.out.println("Initial List:");
        printList();

        // Deleting the node at the beginning
        deleteAtBeginning();

        System.out.println("List after deleting the node at the beginning:");
        printList();
    }
}
Python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = None  # assuming head is a global variable

def delete_at_beginning():
    global head
    # If the list is empty, do nothing
    if head is None:
        print("List is empty. Cannot delete from the beginning.")
        return

    # Store the current head in a temporary variable
    temp = head

    # Update the head to the next node
    head = head.next

    # Delete the old head node
    del temp

def insert_at_beginning(data):
    global head
    new_node = Node(data)
    new_node.next = head
    head = new_node

def print_list():
    global head
    current = head
    while current:
        print(current.data, end=" ")
        current = current.next
    print()

# Inserting nodes for testing
insert_at_beginning(3)
insert_at_beginning(2)
insert_at_beginning(1)

print("Initial List:")
print_list()

# Deleting the node at the beginning
delete_at_beginning()

print("List after deleting the node at the beginning:")
print_list()

# This code is contributed by Shivam

b. Deletion at the End of Singly Linked List:

To delete the last node, traverse the list until the second-to-last node and update its next field to None.

Deletion-at-the-End-of-Singly-Linked-List

Deletion at the End of Singly Linked List

Below is the implementation of the approach:

C++
#include <iostream>

using namespace std;

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

    Node(int data) {
        this->data = data;
        this->next = nullptr;
    }
};

class LinkedList {
public:
    static Node* head; // assuming head is a static variable

    static void deleteAtEnd() {
        // If the list is empty, do nothing
        if (head == nullptr) {
            cout << "List is empty. Cannot delete from the end." << endl;
            return;
        }

        // If there is only one node, delete it and set head to null
        if (head->next == nullptr) {
            delete head;
            head = nullptr;
            return;
        }

        // Traverse to the second last node
        Node* current = head;
        while (current->next->next != nullptr) {
            current = current->next;
        }

        // Delete the last node
        delete current->next;
        current->next = nullptr;
    }

    static void printList(Node* node) {
        while (node != nullptr) {
            cout << node->data << " ";
            node = node->next;
        }
        cout << endl;
    }
};

Node* LinkedList::head = nullptr;

int main() {
    // Example usage
    LinkedList::head = new Node(1);
    LinkedList::head->next = new Node(2);
    LinkedList::head->next->next = new Node(3);

    cout << "Original List:" << endl;
    LinkedList::printList(LinkedList::head);

    LinkedList::deleteAtEnd();

    cout << "List after deleting at end:" << endl;
    LinkedList::printList(LinkedList::head);

    return 0;
}
Java
class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedList {
    static Node head = null; // assuming head is a static variable

    public static void deleteAtEnd() {
        // If the list is empty, do nothing
        if (head == null) {
            System.out.println("List is empty. Cannot delete from the end.");
            return;
        }

        // If there is only one node, delete it and set head to null
        if (head.next == null) {
            head = null;
            return;
        }

        // Traverse to the second last node
        Node current = head;
        while (current.next.next != null) {
            current = current.next;
        }

        // Delete the last node
        current.next = null;
    }

    public static void main(String[] args) {
        // Example usage
        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);

        System.out.println("Original List:");
        printList(head);

        deleteAtEnd();

        System.out.println("List after deleting at end:");
        printList(head);
    }

    // Helper method to print the list
    public static void printList(Node node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println();
    }
}

// This code is contributed by Shivam
Python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    head = None  # assuming head is a static variable

    @staticmethod
    def delete_at_end():
        # If the list is empty, do nothing
        if LinkedList.head is None:
            print("List is empty. Cannot delete from the end.")
            return

        # If there is only one node, delete it and set head to None
        if LinkedList.head.next is None:
            del LinkedList.head
            LinkedList.head = None
            return

        # Traverse to the second last node
        current = LinkedList.head
        while current.next.next is not None:
            current = current.next

        # Delete the last node
        del current.next
        current.next = None

    @staticmethod
    def print_list(node):
        while node is not None:
            print(node.data, end=" ")
            node = node.next
        print()

# Example usage
LinkedList.head = Node(1)
LinkedList.head.next = Node(2)
LinkedList.head.next.next = Node(3)

print("Original List:")
LinkedList.print_list(LinkedList.head)

LinkedList.delete_at_end()

print("List after deleting at end:")
LinkedList.print_list(LinkedList.head)

# This code is contributed by SHIVAM GUPTA
JavaScript
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    static head = null;  // assuming head is a static variable

    static deleteAtEnd() {
        // If the list is empty, do nothing
        if (LinkedList.head === null) {
            console.log("List is empty. Cannot delete from the end.");
            return;
        }

        // If there is only one node, delete it and set head to null
        if (LinkedList.head.next === null) {
            LinkedList.head = null;
            return;
        }

        // Traverse to the second last node
        let current = LinkedList.head;
        while (current.next.next !== null) {
            current = current.next;
        }

        // Delete the last node
        current.next = null;
    }

    static printList(node) {
        while (node !== null) {
            process.stdout.write(node.data + " ");
            node = node.next;
        }
        console.log();
    }
}

// Example usage
LinkedList.head = new Node(1);
LinkedList.head.next = new Node(2);
LinkedList.head.next.next = new Node(3);

console.log("Original List:");
LinkedList.printList(LinkedList.head);

LinkedList.deleteAtEnd();

console.log("List after deleting at end:");
LinkedList.printList(LinkedList.head);

// This code is contributed by SHIVAM

Output
Original List:
1 2 3 
List after deleting at end:
1 2 

c. Deletion at a Specific Position of Singly Linked List:

To delete a node at a specific position, traverse the list to the desired position, update the links to bypass the node to be deleted.

Deletion-at-a-Specific-Position-of-Singly-Linked-List

Deletion at a Specific Position of Singly Linked List

Below is the implementation of the approach:

C++
void deleteAtPosition(int position)
{
    // If the list is empty, do nothing
    if (head == nullptr) {
        cout << "List is empty. Cannot delete from a "
                "specific position."
             << endl;
        return;
    }

    // If deleting the head node
    if (position == 0) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }

    // Traverse to the node just before the specified
    // position
    Node* current = head;
    for (int i = 1;
         i < position && current->next != nullptr; ++i) {
        current = current->next;
    }

    // If position is beyond the end of the list, do nothing
    if (current->next == nullptr) {
        cout << "Position is beyond the end of the list. "
                "Cannot delete."
             << endl;
    }
    else {
        // Delete the node at the specified position
        Node* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
}
Java
// Define a class named GFG
public class GFG {
    
    // Define a Node class for the linked list
    static class Node {
        int data; // Data stored in the node
        Node next; // Pointer to the next node

        // Constructor to initialize node with given value
        Node(int val) {
            data = val;
            next = null;
        }
    }
    
    // Define the deleteAtPosition method
    public static void deleteAtPosition(Node head, int position) {
        // If the list is empty, do nothing
        if (head == null) {
            System.out.println("List is empty. Cannot delete from a specific position.");
            return;
        }

        // If deleting the head node
        if (position == 0) {
            Node temp = head;
            head = head.next;
            temp = null; // Free memory by making the node eligible for garbage collection
            return;
        }

        // Traverse to the node just before the specified position
        Node current = head;
        for (int i = 1; i < position && current.next != null; ++i) {
            current = current.next;
        }

        // If position is beyond the end of the list, do nothing
        if (current.next == null) {
            System.out.println("Position is beyond the end of the list. Cannot delete.");
        } else {
            // Delete the node at the specified position
            Node temp = current.next;
            current.next = current.next.next;
            temp = null; // Free memory by making the node eligible for garbage collection
        }
    }
}
Python
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

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

    def deleteAtPosition(self, position):
        # If the list is empty, do nothing
        if self.head is None:
            print("List is empty. Cannot delete from a specific position.")
            return

        # If deleting the head node
        if position == 0:
            temp = self.head
            self.head = self.head.next
            del temp
            return

        # Traverse to the node just before the specified position
        current = self.head
        for i in range(1, position):
            if current.next is None:
                break
            current = current.next

        # If position is beyond the end of the list, do nothing
        if current.next is None:
            print("Position is beyond the end of the list. Cannot delete.")
        else:
            # Delete the node at the specified position
            temp = current.next
            current.next = current.next.next
            del temp
JavaScript
function deleteAtPosition(position) {
    // If the list is empty, do nothing
    if (!head) {
        console.log("List is empty. Cannot delete from a specific position.");
        return;
    }

    // If deleting the head node
    if (position === 0) {
        let temp = head;
        head = head.next;
        temp = null; // Clearing memory
        return;
    }

    // Traverse to the node just before the specified position
    let current = head;
    let prev = null;
    for (let i = 0; i < position && current.next !== null; ++i) {
        prev = current;
        current = current.next;
    }

    // If position is beyond the end of the list, do nothing
    if (current === null) {
        console.log("Position is beyond the end of the list. Cannot delete.");
        return;
    }

    // Delete the node at the specified position
    prev.next = current.next;
    current = null; // Clearing memory
}




Previous Article
Next Article

Similar Reads

Difference between Singly linked list and Doubly linked list
Introduction to Singly linked list : A singly linked list is a set of nodes where each node has two fields 'data' and 'link'. The 'data' field stores actual piece of information and 'link' field is used to point to next node. Basically the 'link' field stores the address of the next node. Introduction to Doubly linked list : A Doubly Linked List (D
2 min read
Convert Singly Linked List to XOR Linked List
Prerequisite: XOR Linked List – A Memory Efficient Doubly Linked List | Set 1XOR Linked List – A Memory Efficient Doubly Linked List | Set 2 An XOR linked list is a memory efficient doubly linked list in which the next pointer of every node stores the XOR of previous and next node's address. Given a singly linked list, the task is to convert the gi
9 min read
When is Doubly Linked List more Efficient than Singly Linked List?
Did you know there are some cases where a Doubly Linked List is more efficient than a Singly Linked List, even though it takes more memory compared to a Singly Linked List? What are those Cases? Well, we will discuss that in the following article, But first, let's talk about Singly and linked lists: What is a Singly Linked List?A singly linked list
4 min read
Convert singly linked list into circular linked list
Given a singly linked list, we have to convert it into circular linked list. For example, we have been given a singly linked list with four nodes and we want to convert this singly linked list into circular linked list. Approach: The idea is to traverse the singly linked list and check if the node is the last node or not. If the node is the last no
14 min read
Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
A simple solution is to traverse the linked list until you find the node you want to delete. But this solution requires a pointer to the head node which contradicts the problem statement. The fast solution is to copy the data from the next node to the node to be deleted and delete the next node. Something like this: It is important to note that thi
7 min read
Reverse alternate K nodes in a Singly Linked List
Given a linked list, write a function to reverse every alternate k nodes (where k is an input to the function) in an efficient way. Give the complexity of your algorithm. Example: Inputs: 1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;6-&gt;7-&gt;8-&gt;9-&gt;NULL and k = 3 Output: 3-&gt;2-&gt;1-&gt;4-&gt;5-&gt;6-&gt;9-&gt;8-&gt;7-&gt;NULL. Method 1 (Process 2k node
15+ min read
Select a Random Node from a Singly Linked List
Given a singly linked list, select a random node from the linked list (the probability of picking a node should be 1/N if there are N nodes in the list). You are given a random number generator.Below is a Simple Solution Count the number of nodes by traversing the list. Traverse the list again and select every node with a probability of 1/N. The se
15 min read
Alternate Odd and Even Nodes in a Singly Linked List
Given a singly linked list, rearrange the list so that even and odd nodes are alternate in the list.There are two possible forms of this rearrangement. If the first data is odd, then the second node must be even. The third node must be odd and so on. Notice that another arrangement is possible where the first node is even, second odd, third even an
15+ min read
Find middle of singly linked list Recursively
Given a singly linked list and the task is to find the middle of the linked list. Examples: Input : 1-&gt;2-&gt;3-&gt;4-&gt;5 Output : 3 Input : 1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;6 Output : 4 We have already discussed Iterative Solution. In this post iterative solution is discussed. Count total number of nodes in the list in recursive manner and do hal
5 min read
Binary Search on Singly Linked List
Given a singly linked list and a key, the task is to find the key in the Linked List using Binary Search. Examples: Input: LinkedList = 1-&gt;4-&gt;7-&gt;8-&gt;9-&gt;10, key = 7 Output: Present Input: LinkedList = 1-&gt;4-&gt;7-&gt;8-&gt;9-&gt;10, key = 12 Output: Value Not Present Approach: To solve the problem using Binary search follow the below
9 min read