Remove First In Linkedlist

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.
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 Format
Input is managed for you
Output Format
Output is managed for you
Question Video
Constraints
None
Sample Input
addLast 10
addLast 20
addLast 30
display
removeFirst
size
addLast 40
addLast 50
removeFirst
display
size
removeFirst
removeFirst
removeFirst
removeFirst
quit
Sample Output
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






Video Solution

Code Solution

Run
 
Run
Id Name