What will be the complexity of the operation to remove an element from the end of the linear linked list?
What will be the complexity of the operation to remove an element from the end of the linear 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>
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 will be the complexity of the operation to remove an element from the end of the linear linked list?
Time Complexity: O(n). The algorithm involves traversal of the linked list till its end, so the time complexity required is O(n).
What will be the complexity of removing the element from the stack?
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 time complexity to delete an element?
It takes O(n) time to find the element you want to delete. Then in order to delete it, you must shift all elements to the right of it one space to the left. This is also O(n) so the total complexity is linear. Also, if you’re talking about statically allocated arrays, insert takes O(n) as well.
What is the time complexity of deleting a record from the end of linked list?
It just inserts the element at the end of the list and that’s why time complexity is O(1) .
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.
Linked List Operations: Traverse, Insert and Delete
In this tutorial, you will learn different operations on a linked list. Also, you will find implementation of linked list operations in C/C++, Python and Java.
There are various linked list operations that allow us to perform different actions on linked lists. For example, the insertion operation adds a new element to the linked list.
Here’s a list of basic linked list operations that we will cover in this article.
- Traversal – access each element of the linked list
- Insertion – adds a new element to the linked list
- Deletion – removes the existing elements
- Search – find a node in the linked list
- Sort – sort the nodes of the linked list
Before you learn about linked list operations in detail, make sure to know about Linked List first.
Things to Remember about Linked List
- head points to the first node of the linked list
- next pointer of the last node is NULL, so if the next current node is NULL, we have reached the end of the linked list.
In all of the examples, we will assume that the linked list has three nodes 1 —>2 —>3 with node structure as below:
struct node { int data; struct node *next; };
What will be the complexity of the operation to remove an element from the end of the linear linked list?
Posted by: pskji.org
