"Play Next" Without Moving Everyone: Linked Lists
Tapping "Play next" on a long up-next queue moves every song in it. Find a way to put a song at the front in two steps at any length, and meet the structure that does it: the linked list.
Apprentice · Data Structures · Updated
After this lesson you can
- Explain how a linked list stores items as nodes, each with a value and a reference to the next
- Walk a linked list from its head to the end, and say why reading a position is O(n)
- Choose between a growing array and a linked list for a job, from what the job does most, and say why
Key takeaways
- A linked list is a chain of nodes. Each node holds one item and a reference to the next node.
- The first node is the head; the last node's next reference is empty (null in C#, Java and JavaScript, None in Python).
- Adding at the front is O(1): point the new node at the old head, then make it the head. No other node moves.
- Walking the list means starting at the head and following next references until there are none: O(n).
- Reading the item at a position is O(n) too, because there's no sum that jumps to a car: you follow the couplings.
Before this: Why Does This Loop Take Seconds? Your Language's List. A growing array is quick at its end, but putting an item at the front moves every item after it.
The music app's up next queue holds the songs that play after this one. People build long ones: a road trip's queue holds 1,000 songs, and a party's can hold far more. The button they tap most is Play next, which puts a song at the front of the queue. The queue is a growing array, so Play next is an insert at index 0, and every song in the queue scoots over one slot to make room.
On a short queue nobody notices. On the road trip, 1,000 taps of Play next move 499,500 songs (0 + 1 + 2 + … + 999), and on a 100,000-song party queue every single tap moves 100,000 songs. The button starts to lag. By the end of this lesson you'll have a structure that puts a song at the front in two steps however long the queue is, the linked list. First, the plain fixes.
What would you try?
Insert at index 0, and hope the queue stays short. That's today's code: O(n) per tap, O(n²) for a long session. It's fine at 10 songs and the reason for the lag at 100,000.
Keep the array backward. Store the queue with the next song at the end, so Play next becomes adding at the end: O(1), nobody moves. But the app has a second button, Add to queue, which puts a song at the back of the line, and in a backward array the back is index 0. You've moved the slow insert to the other button, not removed it.
Leave gaps at the front. Start the array with 100 empty slots before the first song, and let Play next fill them backward. That's O(1), until the gaps run out on the 101st tap. Then everything has to move along to make new gaps: O(n) again, every 100 taps, plus 100 slots of memory that sit empty most of the time.
| What we tried | Play next | Add to queue | Where it breaks |
|---|---|---|---|
| Insert at index 0 | O(n): every song scoots over | O(1) | long queues |
| A backward array | O(1) | O(n): every song scoots over | the other button |
| Gaps at the front | O(1), until the gaps run out | O(1) | every 100th tap moves everyone |
The questions that lead to it
What does the queue do most? Three things: put a song at the front (Play next), put one at the back (Add to queue), and take the front song when the current one ends. All three happen at the ends.
What doesn't it do? It never asks for "song number 500". The array's one great strength, a jump to any position in one sum, is the one thing this job never uses, and its price, songs packed side by side with no gaps, is what makes every front insert move everyone.
So what if the songs didn't sit side by side at all? Then nothing would have to move. But how would the app know which song comes after which? Each song would have to know it: "after me comes Lemon Skies". Then Play next is two small changes: the new song says "after me comes the old first song", and the app remembers the new song as first. Two changes, whether the queue holds 4 songs or 100,000.
How it got its name
This idea was so useful that it got a name: a linked list, where each item knows only where the next one is.
- Each song is held in a node: a small object with one item (the song's title) and a reference to the next node, usually called
next. A reference is the "note that says where" from References: Two Names, One Object. - The first node is the head. Your code keeps a reference to it.
- The last node is the tail. Its
nextis empty:nullin C#, Java, JavaScript and TypeScript, andNonein Python. Empty means "nothing after me".
You already know the everyday version: a freight train. It isn't one long box but a row of separate cars, each hooked to the car behind it by a coupling. The cars could have come from different rail yards; the couplings are what put them in order. Adding a car at the front means coupling one car to the old front car, and none of the others move.

Play next, in code
This code builds the up-next queue as four nodes, coupled by setting each node's next. Describe walks the list: it starts at the head and follows next from node to node until it reaches the empty reference at the end. Then Play next puts Golden Hour at the front with two changes: the new node's next is the old head, and the head becomes the new node. SongAt walks to a position, counting the couplings it follows.
SongNode head = new SongNode("Midnight Bus");
head.Next = new SongNode("Lemon Skies");
head.Next.Next = new SongNode("Slow Rain");
head.Next.Next.Next = new SongNode("Paper Boats");
Console.WriteLine("Up next: " + Describe(head));
SongNode tapped = new SongNode("Golden Hour");
tapped.Next = head;
head = tapped;
Console.WriteLine("After Play next: " + Describe(head));
Console.WriteLine("Song at position 2: " + SongAt(head, 2));
Console.WriteLine("Song at position 9: " + SongAt(head, 9));
string Describe(SongNode first)
{
List<string> titles = new List<string>();
SongNode? current = first;
while (current != null)
{
titles.Add(current.Title);
current = current.Next;
}
return string.Join(" -> ", titles);
}
string SongAt(SongNode first, int position)
{
SongNode? node = first;
for (int i = 0; i < position && node != null; i++)
{
node = node.Next;
}
return node == null ? "no song" : node.Title;
}
class SongNode
{
public string Title;
public SongNode? Next;
public SongNode(string title)
{
Title = title;
}
}
Up next: Midnight Bus -> Lemon Skies -> Slow Rain -> Paper Boats
After Play next: Golden Hour -> Midnight Bus -> Lemon Skies -> Slow Rain -> Paper Boats
Song at position 2: Lemon Skies
Song at position 9: no song
class SongNode {
String title;
SongNode next;
SongNode(String title) {
this.title = title;
}
}
String describe(SongNode first) {
List<String> titles = new ArrayList<>();
SongNode current = first;
while (current != null) {
titles.add(current.title);
current = current.next;
}
return String.join(" -> ", titles);
}
String songAt(SongNode first, int position) {
SongNode node = first;
for (int i = 0; i < position && node != null; i++) {
node = node.next;
}
return node == null ? "no song" : node.title;
}
void main() {
SongNode head = new SongNode("Midnight Bus");
head.next = new SongNode("Lemon Skies");
head.next.next = new SongNode("Slow Rain");
head.next.next.next = new SongNode("Paper Boats");
IO.println("Up next: " + describe(head));
SongNode tapped = new SongNode("Golden Hour");
tapped.next = head;
head = tapped;
IO.println("After Play next: " + describe(head));
IO.println("Song at position 2: " + songAt(head, 2));
IO.println("Song at position 9: " + songAt(head, 9));
}
Up next: Midnight Bus -> Lemon Skies -> Slow Rain -> Paper Boats
After Play next: Golden Hour -> Midnight Bus -> Lemon Skies -> Slow Rain -> Paper Boats
Song at position 2: Lemon Skies
Song at position 9: no song
class SongNode:
def __init__(self, title):
self.title = title
self.next = None
def describe(first):
titles = []
current = first
while current is not None:
titles.append(current.title)
current = current.next
return " -> ".join(titles)
def song_at(first, position):
node = first
i = 0
while i < position and node is not None:
node = node.next
i += 1
return "no song" if node is None else node.title
head = SongNode("Midnight Bus")
head.next = SongNode("Lemon Skies")
head.next.next = SongNode("Slow Rain")
head.next.next.next = SongNode("Paper Boats")
print("Up next: " + describe(head))
tapped = SongNode("Golden Hour")
tapped.next = head
head = tapped
print("After Play next: " + describe(head))
print(f"Song at position 2: {song_at(head, 2)}")
print(f"Song at position 9: {song_at(head, 9)}")
Up next: Midnight Bus -> Lemon Skies -> Slow Rain -> Paper Boats
After Play next: Golden Hour -> Midnight Bus -> Lemon Skies -> Slow Rain -> Paper Boats
Song at position 2: Lemon Skies
Song at position 9: no song
class SongNode {
constructor(title) {
this.title = title;
this.next = null;
}
}
function describe(first) {
const titles = [];
let current = first;
while (current !== null) {
titles.push(current.title);
current = current.next;
}
return titles.join(" -> ");
}
function songAt(first, position) {
let node = first;
for (let i = 0; i < position && node !== null; i++) {
node = node.next;
}
return node === null ? "no song" : node.title;
}
let head = new SongNode("Midnight Bus");
head.next = new SongNode("Lemon Skies");
head.next.next = new SongNode("Slow Rain");
head.next.next.next = new SongNode("Paper Boats");
console.log(`Up next: ${describe(head)}`);
const tapped = new SongNode("Golden Hour");
tapped.next = head;
head = tapped;
console.log(`After Play next: ${describe(head)}`);
console.log(`Song at position 2: ${songAt(head, 2)}`);
console.log(`Song at position 9: ${songAt(head, 9)}`);
Up next: Midnight Bus -> Lemon Skies -> Slow Rain -> Paper Boats
After Play next: Golden Hour -> Midnight Bus -> Lemon Skies -> Slow Rain -> Paper Boats
Song at position 2: Lemon Skies
Song at position 9: no song
class SongNode {
title: string;
next: SongNode | null = null;
constructor(title: string) {
this.title = title;
}
}
function describe(first: SongNode): string {
const titles: string[] = [];
let current: SongNode | null = first;
while (current !== null) {
titles.push(current.title);
current = current.next;
}
return titles.join(" -> ");
}
function songAt(first: SongNode, position: number): string {
let node: SongNode | null = first;
for (let i = 0; i < position && node !== null; i++) {
node = node.next;
}
return node === null ? "no song" : node.title;
}
let head = new SongNode("Midnight Bus");
head.next = new SongNode("Lemon Skies");
head.next.next = new SongNode("Slow Rain");
head.next.next.next = new SongNode("Paper Boats");
console.log(`Up next: ${describe(head)}`);
const tapped = new SongNode("Golden Hour");
tapped.next = head;
head = tapped;
console.log(`After Play next: ${describe(head)}`);
console.log(`Song at position 2: ${songAt(head, 2)}`);
console.log(`Song at position 9: ${songAt(head, 9)}`);
Up next: Midnight Bus -> Lemon Skies -> Slow Rain -> Paper Boats
After Play next: Golden Hour -> Midnight Bus -> Lemon Skies -> Slow Rain -> Paper Boats
Song at position 2: Lemon Skies
Song at position 9: no song
The -> in the output is plain text, an arrow standing for "then". In C# and TypeScript, SongNode? and SongNode | null say "a reference to a node, or nothing", because the last node's next is empty. C# and Java also ship a ready-made linked list (LinkedList<T> and LinkedList); Python and JavaScript have none built in, so a node class like this one is how you make one there.

The price: walking costs a step per car
Play next got cheap. Something else got slower. In an array, slot 2 is "start + 2", one sum. In a linked list there's no sum, because the nodes aren't side by side: to reach position 2 you follow the head's coupling, then the next one. Position 1,000 means following 1,000 couplings. Reading a position is O(n): twice the songs, twice the walk to the far end. Printing the whole queue is O(n) too, which is fine: any structure needs n steps to show n songs.
That's the honest trade. For the up-next queue, which works at its ends and never jumps to song 500, it's a good one. For a playlist that Shuffle jumps around in, the growing array is still the right structure, and Arrays vs Linked Lists puts the two side by side.
Try it. Tap Play next twice more in the code, with Neon Garden and then Quiet Harbor. Which song plays first now? Then add a line that counts the nodes as Describe walks, and check that it says 7.
The cost card so far
| Operation | Big-O | Why, in everyday words |
|---|---|---|
| Add at the front (Play next) | O(1) | Couple one car to the front; no other car moves |
| Read the item at a position | O(n) | Walk car by car from the engine; there's no sum to jump with |
| Walk the whole list | O(n) | One step per car |
| Find an item by its value | O(n) | Check the cars one by one |
Adding at the back (Add to queue) and the Previous button are the next lesson, Reaching the Last Song, and Going Back One: Doubly Linked Lists.
Check yourself
2 questions to try on the lesson page.
So what
A linked list is the first structure you've met that's held together only by references. When a job works at the front of a line, it makes that work two steps at any length. And once "follow next until it's empty" feels natural, the trees and graphs later in this course are the same walk with more than one coupling per car.