Redirecting to
NADOS


  Prev   Next

Remove Last in Linked List







The pain you feel today will be the strength you feel tomorrow.

Remove Last in Linked List

Welcome back readers!

We hope that the different functions of Linked List that we discussed lately are clear to you. I'm pretty sure that you found those functions quite easy to understand and code.

In this article also we will discuss another Linked List function that is "Remove Last" as it's quite clear from the name of the function that we need to remove the value of the last index from a given linked list.

Let's jump to the problem.

Important Links : Question Video, Solution Video

Problem Discussion :

Just like previous problems you are given a partially written LinkedList class.

Here is a list of existing functions:

  1. addLast - adds a new element with given value to the end of Linked List
  2. display - Prints the elements of a linked list from front to end in a single line. All elements are separated by space.
  3. size - Returns the number of elements in the linked list.
  4. removeFirst - Removes the first element from Linked List.
  5. getFirst - Returns the data of the first element.
  6. getLast - Returns the data of the last element.
  7. getAt - Returns the data of elements available at the index passed.
  8. addFirst - adds a new element with a given value in front of the linked list.
  9. addAt - adds a new element at a given index.

You are required to complete the body of the "removeLast" function.

  • This function should remove the last element and update appropriate data members.
  • If the size is 0 then it should print "List is empty".
  • If the size is 1then it should set both head and tail to null.

Input and Output are already managed for you.

So, friend, I hope that question is clear to you. But if you still face any difficulty in understanding this then please check out our question video where our team has particularly explained what needs to be done in this question. So that you can get some hint of the problem and give it a fair try.

Approach :

If you have read the above mentioned points regarding what you are required to do and understand them then trust me that we will just follow these steps as it is and we will be done with our problem. Let's talk about each step of this function in detail.

RemoveLast

Time Complexity: O(n)

Space Complexity: O(1)

What does this function say according to our question?

We literally just need to tackle the points mentioned in the question to complete this function. Let's take a look at each of them.

  • remove the last element and update appropriate data members:
    For removing the last element of a given Linked List, define a new variable of type node say temp and initialize it with head. Then we apply a for loop from 0 to less than size - 2 and update our temp to temp.next.
    After exiting the for loop, our temp points toward the last second element of the linked list.
    Then we first update tail to temp, this way tail now points towards the last second element of the linked list and tail.next to null, which was the address where our tail used to point before.
    As we have successfully updated our tail, now we need to decrease the size of the linked list by 1.
    img
  • If the size is 0, print "List is empty":
    Can you even remove any element from a linked list of size 0, forget about last. So, it becomes mandatory to first check this condition and then move to the part of removing any element.
    If the size of the linked list is 0, then we print "List is empty" else we remove the last element using the steps discussed above.
    img
  • If the size is 1 then set both head and tail to null:
    What do you think will happen if we remove the only element of the linked list of size 1?
    Yes, we need to update both head and tail to null and size to 0.
    Because after removing one and only element of the linked list, size becomes 0. And the head and tail pointer does not point towards any element's address.
    img

Yes! We are finally done with the function, removeLast.

import java.io.*; import java.util.*; public class Main { public static class Node { int data; Node next; } public static class LinkedList { Node head; Node tail; int size; void addLast(int val) { Node temp = new Node(); temp.data = val; temp.next = null; if (size == 0) { head = tail = temp; } else { tail.next = temp; tail = temp; } size++; } public int size() { return size; } public void display() { for (Node temp = head; temp != null; temp = temp.next) { System.out.print(temp.data + " "); } System.out.println(); } public void removeFirst() { if (size == 0) { System.out.println("List is empty"); } else if (size == 1) { head = tail = null; size = 0; } else { head = head.next; size--; } } public int getFirst() { if (size == 0) { System.out.println("List is empty"); return -1; } else { return head.data; } } public int getLast() { if (size == 0) { System.out.println("List is empty"); return -1; } else { return tail.data; } } public int getAt(int idx) { if (size == 0) { System.out.println("List is empty"); return -1; } else if (idx < 0 || idx >= size) { System.out.println("Invalid arguments"); return -1; } else { Node temp = head; for (int i = 0; i < idx; i++) { temp = temp.next; } return temp.data; } } public void addFirst(int val) { Node temp = new Node(); temp.data = val; temp.next = head; head = temp; if(size == 0){ tail = temp; } size++; } public void addAt(int idx, int val){ if(idx < 0 || idx > size){ System.out.println("Invalid arguments"); } else if(idx == 0){ addFirst(val); } else if(idx == size){ addLast(val); } else { Node node = new Node(); node.data = val; Node temp = head; for(int i = 0; i < idx - 1; i++){ temp = temp.next; } node.next = temp.next; temp.next = node; size++; } } public void removeLast(){ if (size == 0) { System.out.println("List is empty"); } else if (size == 1) { head = tail = null; size = 0; } else { Node temp = head; for(int i = 0; i < size - 2; i++){ temp = temp.next; } tail = temp; tail.next = null; size--; } } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); LinkedList list = new LinkedList(); String str = br.readLine(); while (str.equals("quit") == false) { if (str.startsWith("addLast")) { int val = Integer.parseInt(str.split(" ")[1]); list.addLast(val); } else if (str.startsWith("size")) { System.out.println(list.size()); } else if (str.startsWith("display")) { list.display(); } else if (str.startsWith("removeFirst")) { list.removeFirst(); } else if (str.startsWith("getFirst")) { int val = list.getFirst(); if (val != -1) { System.out.println(val); } } else if (str.startsWith("getLast")) { int val = list.getLast(); if (val != -1) { System.out.println(val); } } else if (str.startsWith("getAt")) { int idx = Integer.parseInt(str.split(" ")[1]); int val = list.getAt(idx); if (val != -1) { System.out.println(val); } } else if (str.startsWith("addFirst")) { int val = Integer.parseInt(str.split(" ")[1]); list.addFirst(val); } else if (str.startsWith("addAt")) { int idx = Integer.parseInt(str.split(" ")[1]); int val = Integer.parseInt(str.split(" ")[2]); list.addAt(idx, val); } else if (str.startsWith("removeLast")) { list.removeLast(); } str = br.readLine(); } } }
java; true";

This was easy. Wasn't it?

Our desire to make you learn will remain unsatisfactory if you still have doubts. We strongly recommend you to watch our video lecture on Remove Last for clearing any type of doubts.

Suggestions and feedback are always welcomed. You can contact us via our website.

Don't let the thought of quitting enter your mind. Struggle a bit harder everyday because,

All the best for a bright future!

Happy Coding!

Linked List
Java
Author: Nikita Aggarwal
 
Run
Id Name