# 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

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.

{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

#include <iostream>

using namespace std;

struct Node {

int data;

struct Node* next;

};

/* Function to remove the last node

{

return NULL;

return NULL;

}

// Find the second last node

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;

}

// 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;

}

// Driver code

int main()

{

/* Use push() function to construct

the below list 8 -> 23 -> 11 -> 29 -> 12 */

for (Node* temp = head; temp != NULL; temp = temp->next)

cout << temp->data << ” “;

return 0;

}

Java

// Java program to remove last node of

class GFG {

static class Node {

int data;

Node next;

};

// Function to remove the last node

// of the linked list /

{

return null;

return null;

}

// Find the second last node

while (second_last.next.next != null)

second_last = second_last.next;

// Change next of second last

second_last.next = null;

}

// 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;

}

// Driver code

public static void main(String args[])

{

// Use push() function to con

// the below list 8 . 23 . 11 . 29 . 12 /

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

import sys

import math

class Node:

def __init__(self, data):

self.data = data

self.next = None

# Function to push node at head

return Node(data)

temp = Node(data)

# Function to remove the last node

return None

return None

while(second_last.next.next):

second_last = second_last.next

second_last.next = None

# Driver code

if __name__==’__main__’:

# Use push() function to con

# the below list 8 . 23 . 11 . 29 . 12

# This code is contributed by Vikash kumar 37

C#

// C# program to remove last node of

using System;

class GFG {

public class Node {

public int data;

public Node next;

};

// Function to remove the last node

// of the linked list /

{

return null;

return null;

}

// Find the second last node

while (second_last.next.next != null)

second_last = second_last.next;

// Change next of second last

second_last.next = null;

}

// 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;

}

// Driver code

public static void Main(String[] args)

{

// Use push() function to con

// the below list 8 . 23 . 11 . 29 . 12 /

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

class Node {

constructor() {

this.data = 0;

this.next = null;

}

}

// Function to remove the last node

// of the linked list /

{

return null;

return null;

}

// Find the second last node

while (second_last.next.next != null)

second_last = second_last.next;

// Change next of second last

second_last.next = null;

}

// Function to push node at head

{

var new_node = new Node();

new_node.data = new_data;

}

// Driver code

// Use push() function to con

// the below list 8 . 23 . 11 . 29 . 12 /

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

Technical Scripter

Technical Scripter 2018

Practice Tags :

Data Structures

Popular:   Pembentukan Mea Dibutuhkan Untuk Meningkatkan

## 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.
Popular:   Distinguish between pop and clear methods in lists with example

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.

• Traversal – access each element of the linked list
• Deletion – removes the existing elements
• Search – find a node in the linked list
• Sort – sort the nodes of the linked list

Popular:   Lagu Peramah Dan Sopan Memiliki Birama