Problem Statement

Implement a doubly linked list. Each node in the doubly linked list must have three attributes:

• value – the value of the current node
• next – a pointer/reference to the next node
• prev – a pointer/reference to the previous node

Assume linked list is 0-index based.

Implement the CustomLinkedList class with the following methods:

• CustomLinkedList() – Initializes the CustomLinkedList object.
• int get(int index) – Get the value of the index^th node in the linked list. If the index is invalid, return -1.
• void addAtHead(int value) – Add a node of value value before the first element of the linked list. After insertion, the new node will be the first node.
• void addAtTail(int value) – Append a node of value value as the last element of the linked list.
• void addAtIndex(int index, int value) – Add a node of value value before the index^th node. If index equals the length, the node will be appended to the end. If index is greater than the length, the node will not be inserted.
• void deleteAtIndex(int index) – Delete the index^th node, if the index is valid.

Examples

CustomLinkedList linkedList = new CustomLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1, 2); // linked list becomes 1 ⇄ 2 ⇄ 3 linkedList.get(1); // returns 2 linkedList.deleteAtIndex(1); // now linked list becomes 1 ⇄ 3 linkedList.get(1); // returns 3

Constraints

• 0 ≤ index, value ≤ 1000
• Please do not use the built-in LinkedList library.
• At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex, and deleteAtIndex.