Given a linked list definition as follows, we want to insert a new node at a given position.
public class Node {
public Object value;
public Node next;
public Node previous;
public Node(Node next, Node previous, Object value) {
this.next = next;
this.previous = previous;
this.value = value;
}
Solution:
We start from the root node and keep traversing through the elements of the linked list until the position index we are given to insert.
We then create the new node based on the data passed to us, the next node will be current node next node and the previous node will be current. Mind you, current is at the node we try to insert a new node after. So the above referencing makes sense.
Then lastly we need to fix the the next references of the previous node to be new node and the current node next node previous to be new node.
Moreover, to handle invalid data we can do the following. If position we are asked to insert is negative, assume we can insert at first place. If position is greater than size of the linked list, then we can assume we can insert it at the last position.
public class MyLinkedList {
private Node header;
private int size;
public MyLinkedList() {
header = new Node(null, null, null);
size = 0;
}
public void insert(Object data, int pos) {
if (pos < 0)
pos = 0;
if (pos > size)
pos = size;
Node current = header;
for (int i = 0; i < pos; i++)
current = current.next;
Node n = new Node(current.next, current, data);
//same as inserting at first
if (current.next != null)
// needed if list is empty at first
current.next.previous = n;
current.next = n;
size++;
}