#### 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.  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 Format
`Input is managed for you`
Output Format
`Output is managed for you`
Question Video
Constraints
`None`
Sample Input
`addFirst 10getFirstaddAt 0 20getFirstgetLastdisplaysizeaddAt 2 40getLastaddAt 1 50addFirst 30removeFirstgetFirstremoveFirstremoveFirstaddAt 2 60displaysizeremoveFirstremoveFirstgetFirstquit`
Sample Output
`10201020 10 2402010 40 60 360`

• 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) {
} else if (idx == size) {
} else {
Node node = new Node();
node.data = val;

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.

• Related Topics

Run

Run
Id Name