Reaching the Last Song, and Going Back One: Doubly Linked Lists
A linked list knows its first song, but "Add to queue" needs the last one and the Previous button needs the one before. Make both one step, and add and remove anywhere you already are by changing a couple of references.
Apprentice · Data Structures · Updated
After this lesson you can
- Add and remove nodes at the front, at the end and after a given node by changing references
- Explain what a tail reference and a doubly linked list each make faster
Key takeaways
- Adding or removing at the front of a linked list is O(1): change the head and one next reference, and nothing else moves.
- Inserting after a node you're already at is O(1); getting to that node is the O(n) part.
- Keeping a tail reference makes adding at the end O(1) too.
- A doubly linked list gives each node a previous reference as well, so you can walk both ways and remove the last node in O(1).
- Without a tail or a previous reference, both jobs walk from the head: O(n) each time, O(n²) for a long session.
Before this: "Play Next" Without Moving Everyone: Linked Lists. A linked list puts a song at the front in two steps, but it only knows where its first song is.
Play next is fixed. Two more buttons in the music app now work against the linked list. Add to queue puts a song at the back of the up-next queue, and the list knows only its front. The Previous button steps back one song, and each song knows only the song after it. On a 10,000-song queue, both buttons are slow, and this lesson makes each of them one step.
What would you try?
Walk to the end, then add. Start at the head and follow next until a node's next is empty: that's the last song, and the new one couples on behind it. It works, but on a 10,000-song queue every tap walks 10,000 nodes. A party adding 1,000 songs to a growing queue walks 0 + 1 + 2 + … + 999 = 499,500 steps: the scooting from the array is back, as walking.
Walk from the head to find the song before. To go back from the current song, start at the head and walk until a node's next is the current song. On song 9,999 of 10,000, one tap of Previous walks 9,998 nodes. Stepping all the way back through the queue that way is about 50 million steps.
Keep an array beside the list, for the jumps. The array would know the last song and the one before any song. But every Play next would then insert at index 0 of that array too, and that's the O(n) the linked list was built to get rid of.
| What we tried | Add to queue | Previous | Where it breaks |
|---|---|---|---|
| Walk to the end each time | O(n): 10,000 steps | long queues | |
| Walk from the head to the song before | O(n): up to 9,999 steps | every tap of Previous | |
| An array beside the list | O(1) | O(1) | Play next is O(n) again |
The questions that lead to it
What do the two slow buttons have in common? Each needs one node the list can't point to: the last one, or the one before. Everything else about them is already cheap: coupling a node on behind the last one is one change, and stepping to the song before would be one step if you knew where it was.
The list already keeps a reference to its first node. What if it kept one to its last node too? Then Add to queue couples the new song behind it, and moves that reference to the new song. Two changes.
Each song knows the song after it. What if it knew the song before it as well? Then Previous is one step along that second reference, like Next.
How it got its name
Both answers are so common that they have names. The reference to the last node is the list's tail reference, kept beside its head. A list whose nodes each have two references, next and previous (usually written prev), is a doubly linked list; the one-reference kind is a singly linked list. A music player's previous and next buttons are a doubly linked list, and so are C#'s LinkedList<T> and Java's LinkedList.
Changing the line where you are
A linked list changes its line by changing references, never by moving nodes. Here are the operations, starting with the one from the last lesson.
Adding at the front is two changes: the new node's next becomes the old head, then the head becomes the new node. The order matters. Move the head first and you've lost the rest of the train, because nothing points to the old first car any more.

Removing the front node is one change: the head becomes the second node (head = head.next). The old first node has nothing pointing to it any more, and your language clears it away. O(1).
Inserting after a node is two changes, once you're standing at that node: the new node's next becomes that node's next, then that node's next becomes the new node. O(1). The catch is getting there: if you only know the song's title, you walk from the head to find it, which is O(n). A linked list is fast at changing the line where you already are.
Adding at the end, with a tail reference, couples the new node behind the tail and moves the tail to it: O(1).
This SongList keeps a head, a tail and a count, and uses all four operations.
SongList train = new SongList();
train.AddLast("Lemon Skies");
train.AddLast("Slow Rain");
train.AddFirst("Midnight Bus");
Console.WriteLine("Start: " + train.Describe());
train.InsertAfter("Lemon Skies", "Paper Boats");
Console.WriteLine("Paper Boats after Lemon Skies: " + train.Describe());
Console.WriteLine("Removed from the front: " + train.RemoveFirst());
Console.WriteLine("Now: " + train.Describe() + " (" + train.Count + " songs, tail: " + train.TailTitle + ")");
class SongNode
{
public string Title;
public SongNode? Next;
public SongNode(string title)
{
Title = title;
}
}
class SongList
{
private SongNode? head;
private SongNode? tail;
public int Count { get; private set; }
public string TailTitle => tail == null ? "none" : tail.Title;
public void AddFirst(string title)
{
SongNode node = new SongNode(title);
node.Next = head;
head = node;
if (tail == null) tail = node;
Count++;
}
public void AddLast(string title)
{
SongNode node = new SongNode(title);
if (tail == null)
{
head = node;
}
else
{
tail.Next = node;
}
tail = node;
Count++;
}
public void InsertAfter(string after, string title)
{
SongNode? current = head;
while (current != null && current.Title != after) current = current.Next;
if (current == null) return;
SongNode node = new SongNode(title);
node.Next = current.Next;
current.Next = node;
if (current == tail) tail = node;
Count++;
}
public string RemoveFirst()
{
if (head == null) return "none";
string title = head.Title;
head = head.Next;
if (head == null) tail = null;
Count--;
return title;
}
public string Describe()
{
List<string> titles = new List<string>();
for (SongNode? node = head; node != null; node = node.Next) titles.Add(node.Title);
return string.Join(" -> ", titles);
}
}
Start: Midnight Bus -> Lemon Skies -> Slow Rain
Paper Boats after Lemon Skies: Midnight Bus -> Lemon Skies -> Paper Boats -> Slow Rain
Removed from the front: Midnight Bus
Now: Lemon Skies -> Paper Boats -> Slow Rain (3 songs, tail: Slow Rain)
class SongNode {
String title;
SongNode next;
SongNode(String title) {
this.title = title;
}
}
class SongList {
private SongNode head;
private SongNode tail;
private int count;
int count() {
return count;
}
String tailTitle() {
return tail == null ? "none" : tail.title;
}
void addFirst(String title) {
SongNode node = new SongNode(title);
node.next = head;
head = node;
if (tail == null) tail = node;
count++;
}
void addLast(String title) {
SongNode node = new SongNode(title);
if (tail == null) {
head = node;
} else {
tail.next = node;
}
tail = node;
count++;
}
void insertAfter(String after, String title) {
SongNode current = head;
while (current != null && !current.title.equals(after)) current = current.next;
if (current == null) return;
SongNode node = new SongNode(title);
node.next = current.next;
current.next = node;
if (current == tail) tail = node;
count++;
}
String removeFirst() {
if (head == null) return "none";
String title = head.title;
head = head.next;
if (head == null) tail = null;
count--;
return title;
}
String describe() {
List<String> titles = new ArrayList<>();
for (SongNode node = head; node != null; node = node.next) titles.add(node.title);
return String.join(" -> ", titles);
}
}
void main() {
SongList train = new SongList();
train.addLast("Lemon Skies");
train.addLast("Slow Rain");
train.addFirst("Midnight Bus");
IO.println("Start: " + train.describe());
train.insertAfter("Lemon Skies", "Paper Boats");
IO.println("Paper Boats after Lemon Skies: " + train.describe());
IO.println("Removed from the front: " + train.removeFirst());
IO.println("Now: " + train.describe() + " (" + train.count() + " songs, tail: " + train.tailTitle() + ")");
}
Start: Midnight Bus -> Lemon Skies -> Slow Rain
Paper Boats after Lemon Skies: Midnight Bus -> Lemon Skies -> Paper Boats -> Slow Rain
Removed from the front: Midnight Bus
Now: Lemon Skies -> Paper Boats -> Slow Rain (3 songs, tail: Slow Rain)
class SongNode:
def __init__(self, title):
self.title = title
self.next = None
class SongList:
def __init__(self):
self.head = None
self.tail = None
self.count = 0
def tail_title(self):
return "none" if self.tail is None else self.tail.title
def add_first(self, title):
node = SongNode(title)
node.next = self.head
self.head = node
if self.tail is None:
self.tail = node
self.count += 1
def add_last(self, title):
node = SongNode(title)
if self.tail is None:
self.head = node
else:
self.tail.next = node
self.tail = node
self.count += 1
def insert_after(self, after, title):
current = self.head
while current is not None and current.title != after:
current = current.next
if current is None:
return
node = SongNode(title)
node.next = current.next
current.next = node
if current is self.tail:
self.tail = node
self.count += 1
def remove_first(self):
if self.head is None:
return "none"
title = self.head.title
self.head = self.head.next
if self.head is None:
self.tail = None
self.count -= 1
return title
def describe(self):
titles = []
node = self.head
while node is not None:
titles.append(node.title)
node = node.next
return " -> ".join(titles)
train = SongList()
train.add_last("Lemon Skies")
train.add_last("Slow Rain")
train.add_first("Midnight Bus")
print("Start: " + train.describe())
train.insert_after("Lemon Skies", "Paper Boats")
print("Paper Boats after Lemon Skies: " + train.describe())
print("Removed from the front: " + train.remove_first())
print(f"Now: {train.describe()} ({train.count} songs, tail: {train.tail_title()})")
Start: Midnight Bus -> Lemon Skies -> Slow Rain
Paper Boats after Lemon Skies: Midnight Bus -> Lemon Skies -> Paper Boats -> Slow Rain
Removed from the front: Midnight Bus
Now: Lemon Skies -> Paper Boats -> Slow Rain (3 songs, tail: Slow Rain)
class SongNode {
constructor(title) {
this.title = title;
this.next = null;
}
}
class SongList {
head = null;
tail = null;
count = 0;
tailTitle() {
return this.tail === null ? "none" : this.tail.title;
}
addFirst(title) {
const node = new SongNode(title);
node.next = this.head;
this.head = node;
if (this.tail === null) this.tail = node;
this.count++;
}
addLast(title) {
const node = new SongNode(title);
if (this.tail === null) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
this.count++;
}
insertAfter(after, title) {
let current = this.head;
while (current !== null && current.title !== after) current = current.next;
if (current === null) return;
const node = new SongNode(title);
node.next = current.next;
current.next = node;
if (current === this.tail) this.tail = node;
this.count++;
}
removeFirst() {
if (this.head === null) return "none";
const title = this.head.title;
this.head = this.head.next;
if (this.head === null) this.tail = null;
this.count--;
return title;
}
describe() {
const titles = [];
for (let node = this.head; node !== null; node = node.next) titles.push(node.title);
return titles.join(" -> ");
}
}
const train = new SongList();
train.addLast("Lemon Skies");
train.addLast("Slow Rain");
train.addFirst("Midnight Bus");
console.log(`Start: ${train.describe()}`);
train.insertAfter("Lemon Skies", "Paper Boats");
console.log(`Paper Boats after Lemon Skies: ${train.describe()}`);
console.log(`Removed from the front: ${train.removeFirst()}`);
console.log(`Now: ${train.describe()} (${train.count} songs, tail: ${train.tailTitle()})`);
Start: Midnight Bus -> Lemon Skies -> Slow Rain
Paper Boats after Lemon Skies: Midnight Bus -> Lemon Skies -> Paper Boats -> Slow Rain
Removed from the front: Midnight Bus
Now: Lemon Skies -> Paper Boats -> Slow Rain (3 songs, tail: Slow Rain)
class SongNode {
title: string;
next: SongNode | null = null;
constructor(title: string) {
this.title = title;
}
}
class SongList {
private head: SongNode | null = null;
private tail: SongNode | null = null;
count = 0;
tailTitle(): string {
return this.tail === null ? "none" : this.tail.title;
}
addFirst(title: string): void {
const node = new SongNode(title);
node.next = this.head;
this.head = node;
if (this.tail === null) this.tail = node;
this.count++;
}
addLast(title: string): void {
const node = new SongNode(title);
if (this.tail === null) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
this.count++;
}
insertAfter(after: string, title: string): void {
let current = this.head;
while (current !== null && current.title !== after) current = current.next;
if (current === null) return;
const node = new SongNode(title);
node.next = current.next;
current.next = node;
if (current === this.tail) this.tail = node;
this.count++;
}
removeFirst(): string {
if (this.head === null) return "none";
const title = this.head.title;
this.head = this.head.next;
if (this.head === null) this.tail = null;
this.count--;
return title;
}
describe(): string {
const titles: string[] = [];
for (let node = this.head; node !== null; node = node.next) titles.push(node.title);
return titles.join(" -> ");
}
}
const train = new SongList();
train.addLast("Lemon Skies");
train.addLast("Slow Rain");
train.addFirst("Midnight Bus");
console.log(`Start: ${train.describe()}`);
train.insertAfter("Lemon Skies", "Paper Boats");
console.log(`Paper Boats after Lemon Skies: ${train.describe()}`);
console.log(`Removed from the front: ${train.removeFirst()}`);
console.log(`Now: ${train.describe()} (${train.count} songs, tail: ${train.tailTitle()})`);
Start: Midnight Bus -> Lemon Skies -> Slow Rain
Paper Boats after Lemon Skies: Midnight Bus -> Lemon Skies -> Paper Boats -> Slow Rain
Removed from the front: Midnight Bus
Now: Lemon Skies -> Paper Boats -> Slow Rain (3 songs, tail: Slow Rain)
Look at the special cases the code handles: adding to an empty list sets both head and tail; inserting after the last node moves the tail; removing the only node empties the tail too. Forgetting one of these is the most common linked-list bug, and the tests in this chapter's exercise check every one.

Walking both ways
SongList is singly linked, so the Previous button is still the slow walk from the head, and so is removing the last node: you need the node before it, to make it the new tail.
In a doubly linked list every node also knows the node in front of it. Previous moves one step along prev, and removing the last node is O(1): the tail moves to tail.prev, and the new tail's next becomes empty. The price is one more reference to store, and to keep right, in every node: every time you set a next, the matching prev has to change too.

That price is worth paying only when a job goes backward. A line that only adds at the back and takes from the front, such as the coffee shop's orders in First Come, First Served at Rush Hour: Queues, needs a head and a tail and nothing more.
Try it. Add a RemoveLast method to SongList (remove_last in Python). How do you find the node before the tail? How many steps does that take for a train of n songs, and how many would it take in a doubly linked list?
The linked list's cost card
| Operation | Big-O | Why, in everyday words |
|---|---|---|
| Add or remove at the front | O(1) | Couple one car and point the engine at it; nothing else moves |
| Add at the end, with a tail reference | O(1) | Couple the new car behind the last one |
| Insert or remove right after a node you're at | O(1) | Change two couplings |
| Step back one (Previous) | O(n) singly, O(1) doubly | Without a prev reference, you walk from the front to find the car before |
| Remove the last node | O(n) singly, O(1) doubly | The same walk, to find the new last car |
| Get to a position, or find a value | O(n) | Walk car by car from the front |
Check yourself
2 questions to try on the lesson page.
So what
Changing a couple of references instead of moving everything is the linked list's whole trick, and a tail and a prev reference let it reach both ends and both directions. Whenever a job adds and removes at the ends of a line, or right where your code already is, that trick is worth reaching for.