What is best and worst case time complexity of deletion of a node in the 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

Introduction to Singly Linked List

Singly Linked List is a variant of Linked List which allows only forward traversal of linked lists. This is a simple form, yet it is effective for several problems such as Big Integer calculations.

A singly linked list is made up of nodes where each node has two parts:

• The first part contains the actual data of the node
• The second part contains a link that points to the next node of the list that is the address of the next node.

The beginning of the node marked by a special pointer named START. The pointer points to the fist node of the list but the link part of the last node has no next node to point to.

The main difference from an array is:

• Elements are not stored in contiguous memory locations.
• Size of Linked List need not be known in advance. It can increase at runtime depending on number of elements dynamically without any overhead.

In Singly Linked List, only the pointer to the first node is stored. The other nodes are accessed one by one.

To get the address of ith node, we need to traverse all nodes before it because the address of ith node is stored with i-1th node and so on.

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.