What is the time complexity of deleting a node from a singly linked list?

Remove last node of the linked list

Given a linked list, the task is to remove the last node of the linked list and update the head pointer of the linked list.

Examples:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL Output: 1 -> 2 -> 3 -> 4 -> NULL Explanation: The last node of the linked list is 5, so 5 is deleted. Input: 2 -> 4 -> 6 -> 8 -> 33 -> 67 -> NULL Output: 2 -> 4 -> 6 -> 8 -> 33 -> NULL Explanation: The last node of the linked list is 67, so 67 is deleted.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: To delete the last node of a linked list, find the second last node and make the next pointer of that node null.

Algorithm:

1. If the first node is null or there is only one node, then they return null.

if headNode == null then return null if headNode.nextNode == null then free head and return null

2. Create an extra space secondLast, and traverse the linked list till the second last node.

while secondLast.nextNode.nextNode != null secondLast = secondLast.nextNode

3. delete the last node, i.e. the next node of the second last node delete(secondLast.nextNode), and set the value of the next second-last node to null.

Implementation:

C++

// CPP program to remove last node of // linked list. #include <iostream> using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to remove the last node of the linked list */ Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // Find the second last node Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Delete last node delete (second_last->next); // Change next of second last second_last->next = NULL; return head; } // Function to push node at head void push(struct Node** head_ref, int new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } // Driver code int main() { /* Start with the empty list */ Node* head = NULL; /* Use push() function to construct the below list 8 -> 23 -> 11 -> 29 -> 12 */ push(&head, 12); push(&head, 29); push(&head, 11); push(&head, 23); push(&head, 8); head = removeLastNode(head); for (Node* temp = head; temp != NULL; temp = temp->next) cout << temp->data << " "; return 0; }

Java

// Java program to remove last node of // linked list. class GFG { // Link list node / static class Node { int data; Node next; }; // Function to remove the last node // of the linked list / static Node removeLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // Find the second last node Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // Change next of second last second_last.next = null; return head; } // Function to push node at head static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } // Driver code public static void main(String args[]) { // Start with the empty list / Node head = null; // Use push() function to con // the below list 8 . 23 . 11 . 29 . 12 / head = push(head, 12); head = push(head, 29); head = push(head, 11); head = push(head, 23); head = push(head, 8); head = removeLastNode(head); for (Node temp = head; temp != null; temp = temp.next) System.out.print(temp.data + " "); } } // This code is contributed by Arnab Kundu

Python3

# Python3 program to remove the last node of # linked list. import sys import math # Link list node class Node: def __init__(self, data): self.data = data self.next = None # Function to push node at head def push(head, data): if not head: return Node(data) temp = Node(data) temp.next = head head = temp return head # Function to remove the last node # of the linked list def removeLastNode(head): if head == None: return None if head.next == None: head = None return None second_last = head while(second_last.next.next): second_last = second_last.next second_last.next = None return head # Driver code if __name__=='__main__': # Start with the empty list head = None # Use push() function to con # the below list 8 . 23 . 11 . 29 . 12 head = push(head, 12) head = push(head, 29) head = push(head, 11) head = push(head, 23) head = push(head, 8) head = removeLastNode(head) while(head): print("{} ".format(head.data), end ="") head = head.next # This code is contributed by Vikash kumar 37

C#

// C# program to remove last node of // linked list. using System; class GFG { // Link list node / public class Node { public int data; public Node next; }; // Function to remove the last node // of the linked list / static Node removeLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // Find the second last node Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // Change next of second last second_last.next = null; return head; } // Function to push node at head static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } // Driver code public static void Main(String[] args) { // Start with the empty list / Node head = null; // Use push() function to con // the below list 8 . 23 . 11 . 29 . 12 / head = push(head, 12); head = push(head, 29); head = push(head, 11); head = push(head, 23); head = push(head, 8); head = removeLastNode(head); for (Node temp = head; temp != null; temp = temp.next) Console.Write(temp.data + " "); } } /* This code contributed by PrinciRaj1992 */

Javascript

<script> // javascript program to remove last node of // linked list. // Link list node / class Node { constructor() { this.data = 0; this.next = null; } } // Function to remove the last node // of the linked list / function removeLastNode(head) { if (head == null) return null; if (head.next == null) { return null; } // Find the second last node var second_last = head; while (second_last.next.next != null) second_last = second_last.next; // Change next of second last second_last.next = null; return head; } // Function to push node at head function push(head_ref , new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } // Driver code // Start with the empty list / var head = null; // Use push() function to con // the below list 8 . 23 . 11 . 29 . 12 / head = push(head, 12); head = push(head, 29); head = push(head, 11); head = push(head, 23); head = push(head, 8); head = removeLastNode(head); for (temp = head; temp != null; temp = temp.next) document.write(temp.data + " "); // This code contributed by Rajput-Ji </script>

Output: 8 23 11 29

Complexity Analysis:

• Time Complexity: O(n).
  The algorithm involves traversal of the linked list till its end, so the time complexity required is O(n).
• Space Complexity: O(1).
  No extra space is required, so the space complexity is constant.

Article Tags :

Data Structures

Linked List

Technical Scripter

Technical Scripter 2018

Practice Tags :

Data Structures

Linked List

What is the space complexity for deleting a linked list O'n O 1 either O 1 or O N?

What is the space complexity for deleting a linked list O'n O 1 either O 1 or O N?

Discussion Forum

What is space complexity of linked list?

Space. Linked lists hold two main pieces of information (the value and pointer) per node. This means that the amount of data stored increases linearly with the number of nodes in the list. Therefore, the space complexity of the linked list is linear: Space - O(n) .

What's the time complexity of removing an element from a doubly-linked list?

The time complexity for removal is only O(1) for a doubly-linked list if you already have a reference to the node you want to remove. Removal for a singly-linked list is only O(1) if you already have references to the node you want to remove and the one before.

What is the the best case time complexity of deleting a node in a singly linked list?

What is the best case time complexity of deleting a node in a Singly Linked list? Explanation: Deletion of the head node in the linked list is taken as the best case. The successor of the head node is changed to head and deletes the predecessor of the newly assigned head node. This process completes in O(1) time.

What is the time complexity of removing the first element of a linked list?

If you want to delete a specific element, the time complexity is O(n) (where n is the number of elements) because you have to find the element first. If you want to delete an element at a specific index i , the time complexity is O(i) because you have to follow the links from the beginning.

What is the complexity of removing the minimum item from a sorted linked list?

2 Answers. It is O(n), because after removing the element, all other elements need to be moved 1 place to the left. If you would have a Linked List, this would not be necessary, so for this data structure it would be O(1).

Why are linked lists useful?

Linked lists are useful because they support the efficient insertion and removal of elements at the expense of inefficient element access, as opposed to arrays. When a variable is created, the computer must allocate memory.

What is the complexity of removing the maximum item from a sorted linked list?

The time complexity for removal is only O(1) for a doubly-linked list if you already have a reference to the node you want to remove. Removal for a singly-linked list is only O(1) if you already have references to the node you want to remove and the one before.

How to calculate time complexity of deletion in linked list?

1.If pointer is given in this case Time Complexity is O (1). 2.You DON'T have pointer to the node to be deleted (Search and Delete). In this case Time Complexity is O (n). I might be wrong, but for your first point, you would need a pointer to the node before the one you're deleting, not the one you're deleting. – MarkB Sep 29 at 8:16

What is the time complexity of insertion in linked list?

The time complexity of insertion is only O(1) if you already have a reference to the node you want to insert after. The time complexity for removal is only O(1) for a doubly-linked list if you already have a reference to the node you want to remove.

Which is more efficient filtering or deleting a linked list?

This means for example that filtering a linked list is more efficient than filtering a list based on an array. Your are correct. 1.If pointer is given in this case Time Complexity is O (1). 2.You DON'T have pointer to the node to be deleted (Search and Delete). In this case Time Complexity is O (n).

What happens at the end of a singly linked list?

Once you reach the end of the list, setNext of ‘temp’ to null, ‘cur’ is not being pointed to by any node, and hence it is available for garbage collection. 5. What is the functionality of the following code?

Related Posts:

How do I maximize my earnings on Instacart?

What are the considerations in the deflection of beams?

How much does it cost to have a baby in 2020?

What helped break the stalemate of trench warfare?

Singly Linked List vs Doubly Linked List

Before looking at the differences between the singly linked list and doubly linked list, we first understand what is singly linked list and doubly linked list separately.