Implement a Doubly Linked List in JavaScript

A doubly linked list is a fundamental data structure that allows for efficient insertion and deletion of elements from both ends. Mastering its implementation is crucial for understanding more complex data structures and algorithms. This challenge will test your ability to construct and manipulate such a list.

Problem Description

You are tasked with creating a DoublyLinkedList class in JavaScript. This class should represent a doubly linked list and provide methods for common operations.

Key Requirements:

1. Node Structure: Each node in the list should contain:

   • value: The data stored in the node.
   • next: A reference to the next node in the list (or null if it's the last node).
   • prev: A reference to the previous node in the list (or null if it's the first node).

2. DoublyLinkedList Class: The DoublyLinkedList class should have:

   • head: A reference to the first node in the list (initially null).
   • tail: A reference to the last node in the list (initially null).
   • length: A property to keep track of the number of nodes in the list (initially 0).

3. Methods to Implement:

   • add(value): Adds a new node with the given value to the end of the list.
   • prepend(value): Adds a new node with the given value to the beginning of the list.
   • remove(value): Removes the first occurrence of a node with the given value from the list. If the value is not found, do nothing.
   • find(value): Returns the node with the given value if it exists, otherwise returns null.
   • toArray(): Returns an array containing the values of all nodes in the list, in order from head to tail.

Expected Behavior:

• When adding or prepending, the head, tail, and length properties should be updated correctly.
• When removing a node, the next and prev pointers of surrounding nodes should be updated, and head or tail should be adjusted if the removed node was at either end.
• The length property should always accurately reflect the number of nodes.

Edge Cases to Consider:

• An empty list.
• Adding to an empty list.
• Prepending to an empty list.
• Removing the only node in the list.
• Removing the head node.
• Removing the tail node.
• Removing a node from the middle of the list.
• Attempting to remove a value that does not exist.

Examples

Example 1: Basic Operations

const list = new DoublyLinkedList();
list.add(10);
list.add(20);
list.prepend(5);
// list.toArray() should be [5, 10, 20]
// list.head.value should be 5
// list.tail.value should be 20
// list.length should be 3

Example 2: Removal

const list = new DoublyLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.remove(2);
// list.toArray() should be [1, 3, 4]
// list.head.value should be 1
// list.tail.value should be 4
// list.length should be 3

list.remove(1); // Remove head
// list.toArray() should be [3, 4]
// list.head.value should be 3
// list.tail.value should be 4
// list.length should be 2

list.remove(4); // Remove tail
// list.toArray() should be [3]
// list.head.value should be 3
// list.tail.value should be 3
// list.length should be 1

Example 3: Edge Cases

const list = new DoublyLinkedList();
list.add(7);
list.remove(7); // Remove the only node
// list.toArray() should be []
// list.head should be null
// list.tail should be null
// list.length should be 0

list.remove(100); // Remove from empty list
// list.toArray() should be []
// list.length should be 0

Constraints

• The value can be any JavaScript primitive type (numbers, strings, booleans) or null/undefined.
• Do not use any built-in array methods or other data structures to store the list's elements. You must manage the nodes and their pointers manually.
• The time complexity for add and prepend should be O(1).
• The time complexity for remove and find should be O(n) in the worst case, where n is the number of nodes in the list.
• The time complexity for toArray should be O(n).

Notes

• Consider creating a separate Node class or factory function to encapsulate the node structure.
• Pay close attention to updating prev and next pointers, especially when dealing with the head and tail.
• When removing a node, ensure that the length is decremented correctly.
• Test your implementation thoroughly with all the provided examples and edge cases.