Implement a Singly Linked List in JavaScript

Linked lists are fundamental data structures used in computer science. Understanding how to implement them is crucial for grasping concepts like dynamic memory allocation and efficient data manipulation. This challenge will guide you through building a basic singly linked list from scratch.

Problem Description

Your task is to implement a LinkedList class in JavaScript. A singly linked list is a linear data structure where elements are not stored at contiguous memory locations. Each element, called a node, contains two parts: a data field and a reference (or pointer) to the next node in the sequence.

You should implement the following methods for your LinkedList class:

• constructor(): Initializes an empty linked list.
• insert(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.
• delete(value): Removes the first occurrence of a node with the given value from the list.
• find(value): Returns the first node containing the given value, or null if not found.
• toArray(): Returns an array representation of the linked list.

The linked list should maintain a head property, which points to the first node in the list, and potentially a tail property for efficient appending.

Examples

Example 1:

// Initialize an empty list
const list = new LinkedList();

// Insert elements
list.insert(10);
list.insert(20);
list.prepend(5);

// Expected output of toArray()
[5, 10, 20]

Explanation:

1. The list starts empty.

2. insert(10): List becomes 5 -> 10.

3. insert(20): List becomes 5 -> 10 -> 20.

4. prepend(5): List becomes 5 -> 10 -> 20. (Oops, prepend(5) was called after insert(20), so 5 would be at the front: 5 -> 5 -> 10 -> 20. Let's correct the explanation based on the code execution order.)

   • Initialize: head = null, tail = null
   • list.insert(10): head = { value: 10, next: null }, tail = head
   • list.insert(20): head = { value: 10, next: { value: 20, next: null } }, tail = head.next
   • list.prepend(5): head = { value: 5, next: { value: 10, next: { value: 20, next: null } } }
   • list.toArray(): [5, 10, 20]

Example 2:

const list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);

list.delete(2); // Remove the node with value 2

// Expected output of toArray()
[1, 3, 4]

Explanation: The list initially is 1 -> 2 -> 3 -> 4. After deleting 2, the list becomes 1 -> 3 -> 4.

Example 3:

const list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);

const foundNode = list.find(2);
// foundNode will be the node object: { value: 2, next: { value: 3, next: null } }

const notFoundNode = list.find(5);
// notFoundNode will be null

Explanation: The find method should return the actual node object, not just its value, allowing further manipulation if needed.

Constraints

• The LinkedList class should be implemented using plain JavaScript. No external libraries are allowed.
• Nodes should be simple objects with value and next properties.
• The insert method should add to the end of the list.
• The delete method should remove the first occurrence of the value.
• The find method should return the first node matching the value.
• The toArray method should return a standard JavaScript Array.

Notes

• Consider how to handle an empty list when performing operations like delete or find.
• For the insert method, keeping track of the tail node can significantly improve performance for appending.
• Think about how to correctly update pointers when inserting at the beginning or deleting a node.
• The Node class or a factory function for creating nodes might be helpful, but not strictly required. You can simply create node objects directly.