Implement Doubly Linked List

Implement a doubly linked list of integers. Each node holds a value, a prev link and a next link. Do not use an array or list to hold the elements.

Implement the DoublyLinkedList class (indices start at 0):

• DoublyLinkedList() creates an empty list.
• addAtHead(val) inserts a new first node.
• addAtTail(val) appends a new last node.
• addAtIndex(index, val) inserts a node so that it becomes the node at position index. If index equals the length it appends; if index is greater than the length, do nothing.
• deleteAtIndex(index) removes the node at index if it is valid, otherwise does nothing.
• get(index) returns the value at index, or -1 if the index is invalid.
• toList() returns all values from head to tail.
• toListReversed() returns all values from tail to head, by following the prev links.

Negative indices are invalid. Operations at the head or tail must be O(1).