Design Doubly Linked List - Solution

// Definition of Doubly Linked List

class DoublyListNode {
int val;
DoublyListNode prev, next;
DoublyListNode(int x){
val = x;
}
}

// Initiate a new Linked List

class MyLinkedList {

private DoublyListNode head;

public MyLinkedList(){
head = null;
}
}

// Traversing the Linked List to get element by index.

private DoublyListNode getNode(int index){
DoublyListNode cur = head;

for(int i=0 ; i < index && cur != null ; i++){
cur = cur.next;
}
return cur;
}


// Function to return last Node of the linked list

private DoublyLinkedList getTail(){

DoublyListNode cur = head;

while(cur !=null && cur.next !=null){
cur = cur.next;
}
return cur;
}


// To fetch the value of the index-th node in the linked list

private int get(int index){

DoublyListNode cur = getNode(index);
return cur == null ? -1 : cur.val;
}


// Add a new Node

// Add a Node if the DoublyListNode is null and add at Head.
public void addAtHead(int val){
DoublyListNode cur = new DoublyListNode(val);
cur.next = head;
if(head != null){
head.prev = cur;
}
head = cur;
return;
}

// Add a Node at Tail 

public void addAtTail (int val){
DoublyListNode prev = getTail();
DoublyListNode cur = new DoublyListNode(val);
if(head == null){
addAtHead(cur);
return;
}
prev.next = cur;
cur.prev = prev;
}

// public void addAtIndex (int index , int val){
if(index == 0){
addAtHead(val);
return;
}

DoublyListNode prev = getNode(index-1);
if(prev == null){
return;
}

DoublyListNode cur = new DoublyListNode(val);
DoublyListNode next = prev.next;

cur.prev = prev;
cur.next = next;
prev.next = cur;
if(next !=null)
next.prev = cur;
}

}

Similar to the SinglyLinkedList it takes O(N) time to get a node by index. where N is the length of the linked list.


// Delete a Node

public void deleteAtIndex (int index){

DoublyListNode cur = get(index);
DoublyListNode prev = cur.prev;
DoublyListNode next = cur.next;

if(cur == null)
return;

if(prev != null){
prev.next = next;
} else {
head = next;
}

if(next != null){
next.prev = prev;
}

}