Prev   Next

Remove First In LinkedList







An algorithm must be seen to be believed.
~ Donald Knuth

Remove First In LinkedList

Dear reader, I hope you are enjoying solving these problems. We are going to add a couple of more operations to our LinkedList. This way our understanding of the topic will get better. So let's understand the problem.

Important Links :Problem Link, Question Video, Solution Video

Problem Discussion :
  1. You are given a partially written LinkedList class.
  2. Here is a list of existing functions:
    1. addLast - adds a new element with a given value to the end of the Linked List
    2. display - Prints the elements of the 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.
  3. You are required to complete the body of removeFirst function
    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 are managed for you.

If you have difficulty understanding the problem watch the question video.

Approach :

To understand this better, look at the illustrations. Let's assume we will represent a node this way:

img

Here we can see the value in the node, the current address of the node, and the next pointer. The next is nothing but stores the address of the next element in the linked list. This way we can traverse and perform other operations in the Linked List.

So, the linked list will look like:

img

Now, if someone tries to traverse the node, they will do so from head to tail. What if the head is actually misplaced, like let's say right now the head points to address 5k which has a value of 10. So if someone traverses now, they will see 10, 20, 30, 40, 50.

But what if we misplace the head to say address 6k, then? Whoever will try to traverse will only be able to get the data 20, 30, 40, 50. Isn't that what we want? We want to remove the first element, so we can simply make the head point to the next element instead. But will that be enough? No, we also have to reduce the value of size.

img

You can see that now head points address 6k and the size is 4. But can we consider it deleted? Well to understand that let's answer this question first. Can we anyhow get the node with the value 10? For explanation purposes, I assumed that the address of that node is 5k but in real life, we will not know that. So in a way, we can never recover that element. Hence we can consider that the node is deleted. Also keep in mind that if the Linked List has just 1 node, then we will make both the head and tail null.

But is that all? Any edge cases that come to your mind? Yes, what if the list is already empty. We can handle that separately. So the pseudocode is:

Pseudo Code
img

You should try to code yourself first. If you are stuck you can look below

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--; } else { head = head.next; 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(); } str = br.readLine(); } } }
java; true";
Analysis
Time Complexity:

O(1)

This is a constant-time operation. Cause all we are doing is just a few operations, no loops or anything. Hence the time complexity is O(1).

Space Complexity:

O(1)

We are not using any extra space, so the space complexity is also O(1).

I hope you have understood the problem and the explanation. If you have some doubts I would insist you watch the solution video. And try to dry run the code, this will make everything clear. See you in the next problem.

Functions and Arrays
Strings and Linked List
Author: Arnab Sen
 
Run
Id Name