Redirecting to
NADOS


  Prev   Next

Remove At Index in Linked List







Never give up on a dream just because of the time it will take to accomplish it. Time will pass anyway.
~Earl Nightingale

Remove At Index in Linked List

Welcome back readers!

Are you enjoying learning about different functions of linked lists?

Linked List is a very interesting data structure which you will be able to see even more when we will solve some problems using it. But for now let's stick to its function only. In case you are thinking about how many more functions then you should be happy to know that this one is last.

Yes! After this one you will be successfully done with all the different functions.

We hope that the different functions of Linked List that we discussed lately are clear to you. I'm pretty sure that you found those functions quite easy to understand and code.

In this article also we will discuss the last Linked List function that is 'Remove At Index' as it's quite clear from the name of the function that we need to remove the value at any particular index from a given linked list.

Important Links : Question Video, Solution Video

Let's jump to the problem.

Problem Discussion :

Just like previous problems you are given a partially written LinkedList class.

Here is a list of existing functions:

  1. addLast - adds a new element with given value to the end of Linked List
  2. display - Prints the elements of a 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.
  4. removeFirst - Removes the first element from Linked List.
  5. getFirst - Returns the data of the first element.
  6. getLast - Returns the data of the last element.
  7. getAt - Returns the data of elements available at the index passed.
  8. addFirst - adds a new element with a given value in front of the linked list.
  9. addAt - adds a new element at a given index.
  10. removeLast - removes the last element of the linked list.

You are required to complete the body of the "removeAt" function.

  • This function should remove the element available at the index passed as parameter.
  • If the size is 0 then it should print "List is empty".
  • If the index is inappropriate print "Invalid arguments".
  • Also consider the case when a list has a single element.

Input and Output are already managed for you.

So, friend, I hope that question is clear to you. But if you still face any difficulty in understanding this then please check out our question video where our team has particularly explained what needs to be done in this question. So that you can get some hint of the problem and give it a fair try before you continue with the article.

Approach :

We will understand this function by taking into consideration all possible special cases. If you have read the above mentioned points regarding what you are required to do in this function and understand them then trust me that we will just follow these steps as it is and we will be done with our problem. Let's talk about each step of this function in detail.

RemoveLast

Time Complexity: O(n)

Space Complexity: O(1)

What does this function say according to our question?

We literally just need to tackle the points mentioned in the question one at a time to complete this function. Let's take a look at each of them.

  • remove the element available at index passed as parameter:
    For removing the ith element of a given Linked List, we define a new variable of type node, say temp and initialize it with head. Then we apply a for loop from 0 to less than index - 1 and update our temp to temp.next in each iteration.
    After exiting the for loop, our temp points toward the element at index, index - 1 of the linked list.
    Now we update temp.next to temp.next.next, this way we break the link of node at index i with rest of the list.
    At last decrease the size of the linked list by 1.
    img
  • If invalid index is passed, should return -1 and print "Invalid arguments":
    It is also possible that the index which the user passes is an invalid index. An invalid index is defined if the index is not in the range of 0 to size -1 that means either the index is smaller than 0 or greater than or equal to size.
    Before taking the control to for loop it is necessary that you check this using an 'if' condition.
    If the index is either smaller than 0 or greater than or equal to size then we print "Invalid Arguments".
    img
  • If the size is 0 then it should print "List is empty" and also consider the case when a list has a single element.
    img

Yes! We are finally done with the function, removeLast.

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 = 0; } else { head = head.next; size--; } } public int getFirst() { if (size == 0) { System.out.println("List is empty"); return -1; } else { return head.data; } } public int getLast() { if (size == 0) { System.out.println("List is empty"); return -1; } else { return tail.data; } } public int getAt(int idx) { if (size == 0) { System.out.println("List is empty"); return -1; } else if (idx < 0 || idx >= size) { System.out.println("Invalid arguments"); return -1; } else { Node temp = head; for (int i = 0; i < idx; i++) { temp = temp.next; } return temp.data; } } public void addFirst(int val) { Node temp = new Node(); temp.data = val; temp.next = head; head = temp; if (size == 0) { tail = temp; } size++; } public void addAt(int idx, int val) { if (idx < 0 || idx > size) { System.out.println("Invalid arguments"); } else if (idx == 0) { addFirst(val); } else if (idx == size) { addLast(val); } else { Node node = new Node(); node.data = val; Node temp = head; for (int i = 0; i < idx - 1; i++) { temp = temp.next; } node.next = temp.next; temp.next = node; size++; } } 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--; } } c 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(); } else if (str.startsWith("getFirst")) { int val = list.getFirst(); if (val != -1) { System.out.println(val); } } else if (str.startsWith("getLast")) { int val = list.getLast(); if (val != -1) { System.out.println(val); } } else if (str.startsWith("getAt")) { int idx = Integer.parseInt(str.split(" ")[1]); int val = list.getAt(idx); if (val != -1) { System.out.println(val); } } else if (str.startsWith("addFirst")) { int val = Integer.parseInt(str.split(" ")[1]); list.addFirst(val); } else if (str.startsWith("addAt")) { int idx = Integer.parseInt(str.split(" ")[1]); int val = Integer.parseInt(str.split(" ")[2]); list.addAt(idx, val); } else if (str.startsWith("removeLast")) { list.removeLast(); } else if (str.startsWith("removeAt")) { int idx = Integer.parseInt(str.split(" ")[1]); list.removeAt(idx); } str = br.readLine(); } } }
java; true";
Analysis
Time Complexity:

O(n)

A 'for' loop has been used therefore the time complexity becomes O(n).

Space Complexity:

O(1)

Since no extra space has been used therefore the space complexity becomes O(1).

This was easy. Wasn't it?

Our desire to make you learn will remain unsatisfactory if you still have doubts. We strongly recommend you to watch our video lecture on Remove At Index clearing any type of doubts.

Suggestions and feedback are always welcomed. You can contact us via our website.

All the best for a bright future!

Happy Coding!

Node
Head
Linked List
Author: Nikita Aggarwal
 
Run
Id Name