Redirecting to
NADOS

Remove Last In Linked List

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a partially written LinkedList class.
2. Here is a list of existing functions:
     2.1 addLast - adds a new element with given value to the end of Linked List
    2.2. display - Prints the elements of linked list from front to end in a single line. 
    All elements are separated by space
    2.3. size - Returns the number of elements in the linked list.
    2.4. removeFirst - Removes the first element from Linked List. 
    2.5. getFirst - Returns the data of first element.
    2.6. getLast - Returns the data of last element. 
    2.7. getAt - Returns the data of element available at the index passed. 
    2.8. addFirst - adds a new element with given value in front of linked list.
    2.9. addAt - adds a new element at a given index.
3. You are required to complete the body of removeLast function. This function should remove the last element and update appropriate data members. If the size is 0, should print "List is empty". If the size is 1, should set both head and tail to null.
4. Input and Output is managed for you.
Input Format 
Input is managed for you
Output Format 
Output is managed for you
Question Video
Constraints 
None
Sample Input 
addFirst 10
getFirst
addAt 0 20
getFirst
getLast
display
size
addAt 2 40
getLast
addAt 1 50
addFirst 30
removeFirst
getFirst
removeLast
removeLast
addAt 2 60
display
size
removeFirst
removeLast
getFirst
quit
Sample Output 
10
20
10
20 10 
2
40
20
20 50 60 
3
50


  • Editorial

    The problem deals with removing the last element present in the linked list. Say for example we have a list 1 -> 2 -> 3 -> 4 -> 5 so after removeLast() operation our list will be 1 -> 2 -> 3 -> 4.

    We are given a linked list class which has three data members:

    1. Head: It points to the starting node of the linked list.

    2. Tail: It points to the last node of the linked list.

    3. Size: It stores the current length (or size) of the linked list.

    The problem can be categorized into the following cases:

    1. When size == 0

    This is the case when our list is empty. As we can not remove an element from an empty list so in this case we just need to prompt an error message and return without changing the data members of the linked list class.

    2. When size == 1

    This is the case when our list has only one node. Removing this node will result in an empty list. As we know that for an empty list both head and tail points to null and the size is equal to zero, so we just need to update the data members in this case.

    3. When size > 1

    This is the general case of our problem. Earlier in our removeFirst() problem we just update our head with head.next and we get our result, but in a singly linked list there is no way to do something like this, tail = tail.prev so we need to go the traditional way, i.e. by traversing the list up to the node before tail node and then set its next data member to null and we also need to decrement the size of our list.

    Below is the implementation in Java: 

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

    java false

    Time Complexity: O(n)

    The time complexity for the function is linear as the traversal of the linked list is involved.

    Space Complexity: O(1)

    The space complexity for the function is constant as we have only used referenced variables in our algorithm.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name