A doubly linked list you can walk both ways

A singly linked list can only be walked forwards, so removing a node means finding its predecessor first. Adding a prev pointer makes removal constant time, which is exactly why caches, playlists and carousels are built on doubly linked lists.

Implement a DoublyLinkedList class. It is constructed with no arguments and starts empty. pushBack(value) and pushFront(value) add a value at that end and each return the new size. popBack() and popFront() remove and return the value at that end, or return undefined when the list is empty. insertAt(index, value) inserts a value so it ends up at that zero-based index, returning true on success; a negative index or one greater than the current size inserts nothing and returns false, while an index equal to the size appends. removeAt(index) removes the node at that index and returns its value, or returns undefined when the index is out of range. size() returns how many values are held. toArray() returns the values front to back and toArrayReverse() returns them back to front, each following the pointers in that direction; both return [] when empty.

Because toArrayReverse() walks the prev pointers, both directions must stay consistent after every operation — this is where a half-updated pointer shows up.

What it has to do

• toArray() and toArrayReverse() are always exact reverses of each other.
• insertAt returns false for a negative index or one past the end, and true when it inserts.
• removeAt returns undefined for an out-of-range index.
• Emptying the list from either end leaves it usable again.
• size() stays accurate after every operation.

Your workspace