Add 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.
3. You are required to complete the body of addAt function. This function should add the element at the index mentioned as parameter. If the idx is inappropriate print "Invalid arguments".
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
removeFirst
getFirst
removeFirst
removeFirst
addAt 2 60
display
size
removeFirst
removeFirst
getFirst
quit
10
20
10
20 10
2
40
20
10 40 60
3
60
-
Editorial
The problem deals with adding a node at the desired index of the linked list. Say for example we have a list, 1 -> 2 -> 3 -> 4 -> 5 and we wish to add node with value 10 at index 2 so our list should look like, 1 -> 2 ->10 -> 3 -> 4 -> 5.
Also, 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 different cases:
1. Index < 0 || Index > Size
This is the case when our input parameter is out of range as our index parameter can have values from 0 <= index <= size(here, index == size is valid as we can add an element at the index == size which is equivalent to adding an element at the end of the list) to satisfy 0 based indexing in programming. So in this case we will prompt an error message "Invalid Arguments".
2. Index == 0
This is the case when we wish to add an element at the beginning of the linked list which can also be referred to as the addFirst() function which we discussed in the previous problem, so here we simply call that function and return.
3. Index == Size
This is the case when we wish to add a node at the end of the linked list which can also be referred to as the addLast() function which we discussed in the previous problem, so here we simply call that function and return.
4. 0 < Index< Size
This is the general case for this problem as in this case the new node acquires the position in between the nodes of our linked list. As we wish to add the node at a particular index so we need to traverse the list until we reach the desired index and then we will have to insert the node which can be done by following these simple steps:
a. Create a new node and update its data members (say newNode)
b. Create a temporary reference pointing at the head (say curr)
c. Traverse from head to the node before the desired index
d. Save the next address in a variable (say saveNode)
e. Update the next data member of curr to newNode
f. Update the next data member of newNode to saveNode
g. Return
Below is the implementation in Java:
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++; } }java false
Time Complexity: O(n)
The time complexity for the function is linear as we need to traverse the list to reach the desired location and then perform insertion, which is dependent on the length of the linked list.
Space Complexity: O(1)
The space complexity for the function is constant as we have only created reference variables that take constant space.
-
Asked in Companies
-
Related Topics
