Persistent List Implementation in JavaScript

Persistent data structures are immutable; operations on them return a new version of the data structure while preserving the old one. This is incredibly useful for version control, debugging, and concurrency, as it avoids unintended side effects. This challenge asks you to implement a persistent singly-linked list in JavaScript.

Problem Description

You are tasked with creating a PersistentList class in JavaScript. This class represents a singly-linked list where all operations (adding, removing, or checking elements) return a new list instance, leaving the original list unchanged. The list should support the following operations:

• constructor(head = null, tail = null, size = 0): Initializes the list. head is the first node, tail is the last node, and size is the number of elements. Defaults to an empty list.
• add(value): Returns a new PersistentList with the given value added to the end.
• remove(index): Returns a new PersistentList with the element at the given index removed. If the index is out of bounds, return the original list unchanged.
• get(index): Returns the value at the given index in the list. If the index is out of bounds, return undefined.
• size(): Returns the number of elements in the list.

Each node in the list should also be immutable. A node should have value, next, and prev properties. next and prev should point to the next and previous nodes respectively, or null if they are the last or first nodes.

Examples

Example 1:

Input:
const list1 = new PersistentList();
const list2 = list1.add(1);
const list3 = list2.add(2);
const list4 = list3.add(3);

Output:
list1.size() // 0
list2.size() // 1
list3.size() // 2
list4.size() // 3
list4.get(0) // 1
list4.get(1) // 2
list4.get(2) // 3
list1 === list2 // true
list2 === list3 // true
list3 === list4 // true

Explanation: Adding elements creates new lists, but the original lists remain unchanged. get retrieves values from the new lists.

Example 2:

Input:
const list1 = new PersistentList();
list1.add(1);
list1.add(2);
const list2 = list1.remove(1);

Output:
list1.size() // 2
list2.size() // 1
list1.get(0) // 1
list1.get(1) // 2
list2.get(0) // 1
list1 === list2 // true

Explanation: Removing an element creates a new list, but the original list remains unchanged.

Example 3:

Input:
const list1 = new PersistentList();
const list2 = list1.remove(0);

Output:
list1.size() // 0
list2.size() // 0
list1 === list2 // true

Explanation: Removing from an empty list returns the original empty list.

Constraints

• The maximum size of the list will be 1000.
• Index values for remove and get will be non-negative integers.
• The add operation will always be valid.
• Performance: While not strictly enforced, aim for a time complexity of O(n) for remove and get operations, where n is the index. add should be O(1).

Notes

• Immutability is key. Do not modify the original list when performing operations. Create new nodes and lists.
• Consider how to efficiently share nodes between different versions of the list to minimize memory usage. This is a core concept of persistent data structures.
• Think about how to handle edge cases like removing from an empty list or accessing an out-of-bounds index.
• The prev property of the nodes is not strictly required for the functionality, but including it can be helpful for future extensions or understanding the concept. It doesn't need to be used in the provided methods.
• You are not required to implement a toString or other display methods. Focus solely on the core operations.