Dear reader, I hope you are enjoying solving these problems. We will be solving more problems on LinkedList because practice makes a person perfect. Let's try to understand the problem.
Important Links : Problem Link Question Video, Solution Video
Prev Next
Add At Index In Linked List
I don't care if it works on your machine! We are not shipping your machine!
~ Vidiu Platon
Add At Index In Linked List
Problem Discussion :
- You are given a partially written LinkedList class.
- Here is a list of existing functions:
- addLast - adds a new element with a given value to the end of the Linked List
- display - Prints the elements of linked list from front to end in a single line. All elements are separated by space
- size - Returns the number of elements in the linked list.
- removeFirst - Removes the first element from Linked List.
- getFirst - Returns the data of the first element.
- getLast - Returns the data of the last element.
- getAt - Returns the data of elements available at the index passed.
- addFirst - adds a new element with a given value in front of the linked list.
- You are required to complete the body of addAt function. This function should add the element at the index mentioned as a parameter. If the idx is inappropriate print "Invalid arguments".
- Input and Output is managed for you.
If you faced difficulty understanding the problem I would suggest you watch the question video.
Approach :
So, let's remind ourselves of the linked list representations.
To understand this better, look at the illustrations. Let's assume we will represent a node this way:
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 this:
Let's look into what are the possible values of the index where the new node will be inserted.
Case 1. (idx < 0 or idx > size)
If the index is negative or greater than size then it makes no sense we will simply print invalid arguments and return.
Case 2. (idx is 0)
This is nothing but the addFirst logic, so we can simply reuse that.
Case 3. (idx is size)
This is the case of adding to the last. Thus, we can use the addLast logic.
Case 4. everything else
Now, we can discuss this, here we are guaranteed that there will be a previous node and a next node because the index is neither the first position nor the last position. Let's say we want to add a node of value 200 in the 2nd index. Here I have shown it.
You can see the dotted lines show the expected connections we need to have to include this new node in the linked list.
In other words, we will get the node of the 2-1 -th index, and make it point to the new node, and make the new node point to the previous 2-nd index. Let's look at it step by step.
Step 1: Create a new node
Step 2: Iterate to idx-1 th node from head.
temp now points to 2-1 = 1st node
Step 3: node.next = temp.next
Step4: temp.next = node
And there you go, we have successfully inserted a new element.
Try to write this in code.
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 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);
}
str = br.readLine();
}
}
}
java;
true";
Analysis:
Time Complexity:
We are running a single loop to idx-1, at the worst case it might be size-1, so the time complexity will be O(n) linear.
Space Complexity:
We are not using any auxiliary space other than a single new node, So the space complexity is constant as well.
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.
