Remove At Index 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.
2.10. removeLast - removes the last element of linked list.
3. You are required to complete the body of removeAt function. The function should remove the element available at the index passed as parameter. If the size is 0, should print "List is empty". If the index is inappropriate print "Invalid arguments". Also consider the case when list has a single element.
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
removeAt 2
getFirst
removeAt 0
removeAt 1
addAt 2 60
display
size
removeAt 0
removeAt 1
getFirst
quit
10
20
10
20 10
2
40
30
20 40 60
3
40
-
Editorial
The problem deals with removing the node present at the desired index in the linked list. Say for example we have a list 1 -> 2 -> 3 -> 4 -> 5 and we wish to remove node at 3rd index so after removeAt() operation our list will be 1 -> 2 -> 3 -> 5.
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. Index < 0 || Index >= Size
This is the case when the input parameter is out of range, as to follow 0 based indexing the index parameter should be in the range of )<= Index < Size which is clearly violated in this case. So, here we would simply prompt an error message and return.
2. Index == 0
This is the case of removing the first element from the list which we have already implemented in previous lessons, hence here we could just call our removeFirst() function and return.
3. Index == Size - 1
This is the case of removing the last element from the list which we have already implemented in previous lessons, hence here we could just call our removeLast() function and return.
4. 0 < Index < Size -1
This is the general case of our problem where the element to be removed is present in between the elements of the list. To remove an element from the list, we need the node previous to it and the node next to the node to be deleted. So here we can traverse the list till we reach the previous node and we can update the next data member of the previous node by pointing it to the next node of its next node i.e., prevNode.next = prevNode.next.next(which is the same ascurrNode.nextwherecurrNodeis the node to be deleted). After updating the list all we need to do is to decrement the size of our list and then return.
Below is the implementation in Java:
public void removeAt(int idx) { if (idx < 0 || idx >= size) { System.out.println("Invalid arguments"); } else if (idx == 0) { removeFirst(); } else if (idx == size - 1) { removeLast(); } else { Node temp = head; for (int i = 0; i < idx - 1; i++) { temp = temp.next; } temp.next = temp.next.next; 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
