Doubly linked list playlist with O(1) node-based edits
A music player’s “Up next” queue changes constantly: tracks are added to the end, a song is pinned to play next, a track is dragged to the top, and songs are removed from the middle. With an array, each of those is an O(n) shift. With a doubly linked list, the UI holds a handle (the node) for each row, and every edit is O(1).
Implement a class Playlist backed by a doubly linked list.
const queue = new Playlist();
const node = queue.add(track); // node: { value, prev, next }
Methods that add a track return its node, an object with:
value: the track that was added.prev and next: the neighbouring nodes, or null at the ends.A node belongs to the playlist that created it until it is removed. After removal, its prev and next are null and it no longer belongs to any playlist.
add(track): append to the end. Returns the new node.addFirst(track): insert at the start. Returns the new node.insertAfter(node, track): insert right after node. Returns the new node. Throws an Error if node does not belong to this playlist.remove(node): unlink node and return its value. If node does not belong to this playlist (for example it was already removed, or it came from another playlist), do nothing and return undefined.moveToFront(node): move node (the same object) to the start. Returns true, or false without changing anything if node does not belong to this playlist.find(predicate): the first node, from the start, whose predicate(value) is truthy, or null.reverse(): reverse the order in place and return the playlist. Every node keeps its identity and value; only the links change.toArray(): the values from first to last, as a new array.size, first, last: getters for the number of tracks, the first value, and the last value. first and last are undefined when the playlist is empty.for (const track of queue) and [...queue] yield values from first to last.const queue = new Playlist();
const intro = queue.add('Intro');
const solar = queue.add('Solar');
queue.add('Outro');
queue.toArray(); // => ['Intro', 'Solar', 'Outro']
queue.insertAfter(intro, 'Interlude');
queue.toArray(); // => ['Intro', 'Interlude', 'Solar', 'Outro']
queue.moveToFront(solar); // => true
queue.toArray(); // => ['Solar', 'Intro', 'Interlude', 'Outro']
solar.prev; // => null
solar.next.value; // => 'Intro'
queue.remove(intro); // => 'Intro'
queue.remove(intro); // => undefined (already removed)
queue.size; // => 3
queue.reverse().toArray(); // => ['Outro', 'Interlude', 'Solar']
queue.first; // => 'Outro'
queue.find((title) => title.startsWith('In')).value; // => 'Interlude'
[...queue]; // => ['Outro', 'Interlude', 'Solar']
undefined, objects, and duplicates. Nodes, not values, identify a position.find, reverse, toArray, and iteration must be O(1).next and prev, so keep both directions correct after every operation.