Implement a Doubly Linked List

Create a doubly linked list that supports these actions:

• addAtHead(int val): Insert a new node containing val at the front of the list.
• addAtTail(int val): Place a new node containing val after the current last node.
• addAtIndex(int index, int val): Insert a node holding val immediately before the node at position index. When index matches the current list length, add the node at the end instead. If index exceeds the list length, leave the list unchanged. For a negative index, insert the node at the front.
• deleteAtIndex(int index): Remove the node at position index when that position exists.

Requirements:

Diagram

Doubly linked list operations and their O(1) pointer updates

• Each stored value is an integer.
• Every operation must run in O(1) time.
• After all commands run, return the resulting state of the list.

Example:

Input:
addAtHead(4)
addAtTail(9)
addAtIndex(1,6)
get(1)
deleteAtIndex(1)
get(1)

Output:
[4, 6, 9]
6
9

Explanation: The value 6 is placed between 4 and 9; after that node is removed, position 1 contains 9.

Data Constraints: Execute no more than 1000 operations.

Example

Input: addAtHead 7
addAtTail 11
addAtIndex 1 8
get 1
deleteAtIndex 1
get 1

Output:
[7, 8, 11]
8
11

Explanation: Inserting 8 at index 1 puts it between 7 and 11; deleting that index leaves 11 as the value at index 1.