ExampleDifficulty: Intermediate2 min

Linked List Example: A Playlist That Moves Songs

Moving a song to the front changes six references, however long the playlist is.

A doubly linked list, in which every node refers to the node before it as well as the one after, earns its extra reference when a program removes and reinserts nodes it already holds. This card covers that choice through a music player that moves a song to the top of its queue.

The queue holds songs A, B, C and D, and the listener drags C to the top. The player keeps a dictionary from each song's name to its node, so it holds C's node without walking the queue. Moving C means unlinking it from between B and D, then linking it in front of A and making it the head.

Before the run: how many references change to move C to the front?

Six: two to unlink C, three to link it in front of A, and the head.

A run made the changes and printed the queue from both ends after each group:

Move song C to the front of the queue

Start

The queue reads A B C D from the head and D C B A from the tail.

text

head -> [A] -> [B] -> [C] -> [D] -> null
tail -> [D] -> [C] -> [B] -> [A] -> null

Unlink C: B.next = D, D.prev = B

B and D now point at each other, so neither walk passes through C.

text

head -> [A] -> [B] -> [D] -> null
tail -> [D] -> [B] -> [A] -> null

Link C at the front: C.next = A, A.prev = C, C.prev = null, head = C

C points forward to A, A points back to C, and the head moves to C. The run counted six changed references.

text

head -> [C] -> [A] -> [B] -> [D] -> null
tail -> [D] -> [B] -> [A] -> [C] -> null

The changes read only C, its two neighbours and the head, so the count is six however long the queue is. A dynamic array would shift every song before C one place, and a singly linked list would walk from the head to find B, the node before C.

The same shape appears wherever recent use reorders a sequence. A cache that keeps the most recently read entries moves each entry it reads to the front, and an editor's list of open files moves the file opened most recently to the top. In each, the program finds the node by a key, not by a walk, and the doubly linked list turns the move into a fixed number of rewires.

← → move through sections and cards