How do you delete the first node of a singly linked list?

Move the head to the second node. The old first node is no longer referenced, so the garbage collector removes it: This is O(1).

How do you delete the last node of a singly linked list?

Find the second-last node and set its next to null: This takes O(n), because the list must be walked to find the second-last node.

Write a Java method to delete the node at a given position.

Java example: // position is 0-based static Node deleteAt(Node head, int position) { if (head == null) { return null; } if (position == 0) { return head.next; } Node previous = head; for (int i = 0; i < position - 1 && previous.next != null; i++) { previous = previous.next; } if (previous.next != null) { previous.next = previous.next.next; // skip the node } return head; }

Write a Java method to delete the first node with a given value.

Java example: static Node deleteValue(Node head, int value) { if (head == null) { return null; } if (head.data == value) { return head.next; } Node current = head; while (current.next != null && current.next.data != value) { current = current.next; } if (current.next != null) { current.next = current.next.next; } return head; }

Why must deletion methods return the head?

If the first node is deleted, the head changes. Java passes object references by value, so assigning a new head inside the method does not change the caller's variable. Returning the head, as in head = deleteFirst(head);, keeps the caller up to date. Alternatively, store the head as a field of a list class.

How does a dummy node simplify deletion?

A dummy node placed before the head means every real node has a previous node, so deleting the first node needs no special case:

Write a Java method to remove duplicates from a sorted linked list.

Java example: static Node removeDuplicates(Node head) { Node current = head; while (current != null && current.next != null) { if (current.data == current.next.data) { current.next = current.next.next; } else { current = current.next; } } return head; // 1->1->2->3->3 becomes 1->2->3 }

Do you need to free memory after deleting a node in Java?

No. Once no variable references the removed node, the garbage collector reclaims it automatically. In C or C++ you would call free or delete yourself.

Write a Java method to delete the middle node of a linked list.

For 1→2→3→4→5 it removes 3. The slow and fast pointers find the middle in one pass.

What is the time complexity of each deletion?

Delete the first node: O(1). Delete the last node: O(n). Delete at a position k: O(k). Delete by value: O(n). All of them use O(1) extra space.

Deletion in Singly Linked List

Q: Write a Java method to delete the first node with a given value.

Java example: static Node deleteValue(Node head, int value) { if (head == null) { return null; } if (head.data == value) { return head.next; } Node current = head; while (current.next != null && current.next.data != value) { current = current.next; } if (current.next != null) { current.next = current.next.next; } return head; }

Q: Why must deletion methods return the head?

If the first node is deleted, the head changes. Java passes object references by value, so assigning a new head inside the method does not change the caller's variable. Returning the head, as in head = deleteFirst(head);, keeps the caller up to date. Alternatively, store the head as a field of a list class.

Q: How does a dummy node simplify deletion?

A dummy node placed before the head means every real node has a previous node, so deleting the first node needs no special case:

Q: Write a Java method to remove duplicates from a sorted linked list.

Java example: static Node removeDuplicates(Node head) { Node current = head; while (current != null && current.next != null) { if (current.data == current.next.data) { current.next = current.next.next; } else { current = current.next; } } return head; // 1->1->2->3->3 becomes 1->2->3 }

In this Linked List tutorial, we will see all about the delete operation in a single linked list. In the delete operation, we will remove an existing node from the linked list from any position.

In a Singly Linked List, we can delete a node at the following positions:

From the beginning of the linked list.
From middle of the linked list.
From the end of the linked list.

Create a node class

Node.java

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

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

1. Delete a node from the beginning of the linked list

In the below given example we will see how to delete an existing node from the beginning or front the linked list.

DeleteNodeAtBignningInSLL.java

// Java program to delete a node from the beginning of the linked list
public class DeleteNodeAtBignningInSLL {
  // Method to delete the head node
  static Node deleteHead(Node head) {
    // Before deleting a node just make sure list should not be empty
    if (head == null) {
      System.out.println("List is empty");
      return null;
    }

    // Change the head pointer to the next node
    // and free the original head
    Node temp = head;
    head = head.next;

    // Free the original head (handled by garbage collector)
    temp = null;

    // Return the new head
    return head;
  }

  // Method to print the doubly linked list
  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) {
    // Create nodes
    Node head = new Node(10);
    head.next = new Node(20);
    head.next.next = new Node(30);
    head.next.next.next = new Node(40);

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

    // Deleting the head node
    head = deleteHead(head);
    System.out.println("After deleting head, Linked List data: ");
    printList(head);
  }
}

Output

Original Linked List data:

10 -> 20 -> 30 -> 40 -> null

After deleting head, Linked List data:

20 -> 30 -> 40 -> null

2. Delete a node from the middle of the linked list

In the below given example we will see how to delete an existing node from the any position of the linked list.

DeleteNodeAtMiddleInSLL.java

// Java program to delete a node from the linked list at the given position
public class DeleteNodeAtMiddleInSLL {

  // Method to delete a node at a given position
  public static Node deleteNode(Node head, int position) {
    // Before deleting a node just make sure list should not be an empty
    if (head == null) {
      System.out.println("List is empty");
      return head;
    }

    Node temp = head;
    Node prev = null;

    // Case 1: Head is to be deleted
    if (position == 1) {
      head = temp.next;
      return head;
    }

    // Case 2: Node to be deleted is in middle
    // Traverse till given position
    for (int i = 1; temp != null && i < position; i++) {
      prev = temp;
      temp = temp.next;
    }

    // If given position is found, delete node
    if (temp != null) {
      prev.next = temp.next;
    } else {
      System.out.println("Data not present in the list.");
    }

    return head;
  }

  // Method to print a list
  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) {
    // Create nodes
    Node head = new Node(10);
    head.next = new Node(20);
    head.next.next = new Node(30);
    head.next.next.next = new Node(40);
    head.next.next.next.next = new Node(50);

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

    // Deleting node at position 3
    head = deleteNode(head, 3);

    // Print list after deletion
    System.out.print("After deletion, Linked List data:\n");
    printList(head);
  }
}

Output

Original Linked List data:

10 -> 20 -> 30 -> 40 -> 50 -> null

After deletion, Linked List data:

10 -> 20 -> 40 -> 50 -> null

3. Delete a node from the end of the linked list

In the below given example we will see how to delete an existing node from the end or last the linked list.

DeleteNodeAtEndInSLL.java

// Java program to delete the end or last node of linked list
public class DeleteNodeAtEndInSLL {
  // Method to remove the last node from the linked list
  static Node removeLastNode(Node head) {

    // Before deleting a node just make sure list should not be empty
    if (head == null) {
      System.out.println("List is empty");
      return null;
    }

    // If the list has only one node, delete it and return null
    if (head.next == null) {
      return null;
    }

    // Find the second last node
    Node secondLast = head;
    while (secondLast.next.next != null) {
      secondLast = secondLast.next;
    }

    // Delete the last node
    secondLast.next = null;

    return head;
  }

  // Method to print the list
  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) {
    // Create nodes
    Node head = new Node(10);
    head.next = new Node(20);
    head.next.next = new Node(30);
    head.next.next.next = new Node(40);

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

    // Removing the last node from the list
    head = removeLastNode(head);

    System.out.println("After removing last node, Linked List data: ");
    printList(head);
  }
}

Output

Original Linked List data:

10 -> 20 -> 30 -> 40 -> null

After removing last node, Linked List data:

10 -> 20 -> 30 -> null

Help Us Improve

Deletion in Singly Linked List

Create a node class

1. Delete a node from the beginning of the linked list

2. Delete a node from the middle of the linked list

3. Delete a node from the end of the linked list

Frequently Asked Questions (FAQ)