Remove Last In Linked List
1. You are given a partially written LinkedList class.Input Format
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 is managed for youOutput Format
Output is managed for youQuestion Video
NoneSample Input
addFirst 10Sample Output
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
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