Easy Lists
Remove Duplicates (Doubly Linked List)
Receives an array of integers and builds a doubly linked list, where each node holds a value, a next pointer to the following node, and a prev pointer to the preceding one. It walks the list forward from head to tail using a set to track seen values; the first occurrence of each value is kept and any duplicate node is unlinked by updating both its predecessor's next and its successor's prev. Returns the head of the filtered list with each value appearing exactly once, preserving the original order.
Visualization
- Input
- Result
Algorithm code
/**
* @typedef {{ value: number, prev: DLLNode | null, next: DLLNode | null }} DLLNode
*/
/**
* @param {number[]} arr
* @returns {DLLNode | null} head of the deduplicated doubly linked list
*/
export function removeDuplicatesDLL(arr) {
if (arr.length === 0) return null;
let head = { value: arr[0], prev: null, next: null };
let cur = head;
for (let i = 1; i < arr.length; i++) {
const node = { value: arr[i], prev: cur, next: null };
cur.next = node;
cur = node;
}
const seen = new Set([head.value]);
let prev = head;
let node = head.next;
while (node !== null) {
const next = node.next;
if (seen.has(node.value)) {
prev.next = next;
if (next !== null) next.prev = prev;
} else {
seen.add(node.value);
prev = node;
}
node = next;
}
return head;
}FUNCTION removeDuplicatesDLL(arr):
IF arr is empty: RETURN null
// Build the doubly linked list
head ← Node(arr[0], prev: null, next: null)
cur ← head
FOR i FROM 1 TO length(arr) - 1:
node ← Node(arr[i], prev: cur, next: null)
cur.next ← node
cur ← node
// Remove duplicates using a seen-set
seen ← { head.value }
prev ← head
node ← head.next
WHILE node ≠ null:
next ← node.next
IF node.value IN seen:
prev.next ← next // unlink forward pointer
IF next ≠ null:
next.prev ← prev // repair backward pointer
ELSE:
ADD node.value TO seen
prev ← node
node ← next
RETURN head