Doubly Linked List Implementation in JavaScript

Doubly linked lists are a fundamental data structure offering efficient insertion and deletion at both ends and in the middle. This challenge asks you to implement a doubly linked list in JavaScript, providing core functionalities like insertion, deletion, searching, and traversal. Mastering doubly linked lists is crucial for understanding more complex data structures and algorithms.

Problem Description

You are tasked with creating a DoublyLinkedList class in JavaScript. This class should support the following operations:

• constructor(): Initializes an empty doubly linked list.
• append(value): Adds a new node containing the given value to the end of the list.
• prepend(value): Adds a new node containing the given value to the beginning of the list.
• delete(value): Removes the first node containing the given value from the list. If the value is not found, the list remains unchanged.
• search(value): Returns true if a node containing the given value exists in the list, and false otherwise.
• print(): Returns a string representation of the list, with values separated by " -> ". For example, if the list contains 1, 2, and 3, the output should be "1 -> 2 -> 3". If the list is empty, return an empty string.
• toArray(): Returns an array containing the values of the nodes in the list, in the order they appear.

Node Structure:

Each node in the doubly linked list should have the following properties:

• 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).

Key Requirements:

• The implementation must be efficient, minimizing unnecessary operations.
• The delete operation should handle cases where the value appears multiple times in the list (only the first occurrence should be deleted).
• The delete operation should correctly update the next and prev pointers of neighboring nodes.
• The list should remain consistent after each operation.

Examples

Example 1:

Input:
  - Create a DoublyLinkedList
  - append(1)
  - append(2)
  - append(3)
  - print()
Output: "1 -> 2 -> 3"
Explanation: The list is initialized and three nodes are added to the end. The print method returns the string representation of the list.

Example 2:

Input:
  - Create a DoublyLinkedList
  - prepend(5)
  - prepend(4)
  - prepend(3)
  - print()
Output: "3 -> 4 -> 5"
Explanation: Three nodes are added to the beginning of the list. The print method returns the string representation of the list.

Example 3:

Input:
  - Create a DoublyLinkedList
  - append(1)
  - append(2)
  - append(3)
  - delete(2)
  - print()
Output: "1 -> 3"
Explanation: The list is initialized with 1, 2, and 3. The value 2 is deleted, and the print method returns the updated list.

Example 4:

Input:
  - Create a DoublyLinkedList
  - append(1)
  - append(2)
  - search(3)
Output: false
Explanation: The list contains 1 and 2. The search method returns false because 3 is not present.

Constraints

• The values stored in the nodes can be any JavaScript data type.
• The maximum number of nodes in the list will be 1000.
• The delete operation should have a time complexity of O(n) in the worst case (where n is the number of nodes).
• The search operation should have a time complexity of O(n) in the worst case.
• The append and prepend operations should have a time complexity of O(1).

Notes

• Consider creating a separate Node class to represent individual nodes in the list. This will improve code organization and readability.
• Pay close attention to how you update the next and prev pointers when inserting and deleting nodes. Incorrect pointer manipulation can lead to a corrupted list.
• Thoroughly test your implementation with various scenarios, including edge cases like empty lists, deleting the first or last node, and searching for non-existent values.
• Think about how to handle duplicate values when deleting. The problem specifies deleting only the first occurrence.