Remove First In Linkedlist
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.
3. You are required to complete the body of removeFirst function
3.1. removeFirst - This function is required to remove the first element from
Linked List. Also, if there is only one element, this should set head and tail to
null. If there are no elements, this should print "List is empty".
4. Input and Output is managed for you.
Input is managed for youOutput Format
Output is managed for youQuestion Video
NoneSample Input
addLast 10Sample Output
addLast 20
addLast 30
display
removeFirst
size
addLast 40
addLast 50
removeFirst
display
size
removeFirst
removeFirst
removeFirst
removeFirst
quit
10 20 30
2
30 40 50
3
List is empty
-
Editorial
The problem deals with removing the first element present in the linked list.
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.
To understand the problem better we need to understand the following cases:
1. When size > 1
This is the case when our list is not empty. Say for example our list is 1 -> 2 - > 3 -> 4 -> 5 with head at node with value 1,tail at node with value 5 and size of list as 5. Now when we called our removeFirst() function it gives us an updated list which looks like 2 -> 3 -> 4 -> 5 where head points at the node with value 2, tail points at the node with value 5, and size of the list become 4. Now to achieve this we need to do two things, firstly to update the head to its next node and then decrement the size of the list.
2. 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.
3. 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 point to null and the size is equal to zero, so we just need to update the data members in this case.
Why Case 1 and Case 3 are different?
They are different since for Case 3 we need to update the tail pointer too as deleting a list with one node results in an empty list whereas in Case 1 deleting the first node does not affect the last node, hence different.
Below is the implementation in Java:
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--; } }java false
Time Complexity: O(1)
The time complexity for the function is constant as only shifting of the head pointer is involved in the operation which is independent of the length of the linked list.
Space Complexity: O(1)
The space complexity for the function is constant as we have not used any extra space for our algorithm.
-
Asked in Companies
-
Related Topics
