Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 3 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 9 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 5 chapters
Show chapters Hide chapters

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

5. Linked Lists
Written by Jonathan Sande

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

A linked list is a collection of values arranged in a linear, unidirectional sequence. It has several theoretical advantages over contiguous storage options such as the Dart List:

  • Constant time insertion and removal from the front of the list.
  • Reliable performance characteristics.

A linked list is a chain of nodes:

12 1 3
A linked list

Nodes have two responsibilities:

  1. Hold a value.
  2. Hold a reference to the next node. A null reference indicates the end of the list.

12 Node Reference
A node holding the value 12

In this chapter, you’ll implement a linked list and learn about the common operations associated with it. You’ll also learn about the time complexity of each operation.

Open up the starter project for this chapter so you can dive into the code.

Node

Create a folder called lib in the root of your project. Then add a new file to this folder called linked_list.dart. At the top of that file add a class called Node with the following code:

class Node<T> {
  Node({required this.value, this.next});
  T value;
  Node<T>? next;
}

Since Node only knows about a single value, T is the standard letter people use to mean that the node can hold any type. Later when you create a linked list of nodes, you’ll use E to refer to the type since they are elements of the list.

Making Nodes Printable

Override toString so that you can print Node later. Add this inside your newly created class:

Creating a Linked List by Hand

Now it’s time to try out your shiny new Node! Open bin/starter.dart and add the file import:

9 9 7 kapp
O juzcod nilp xejrialupx maxoim 1, 2, uly 9

LinkedList

A linked list has the concept of a head and tail, which refer to the first and last nodes of the list respectively:

2 6 0 divk hoom toob
Qpo tiog evp keoy ec zba cazp

Adding Values to a List

Since you’re building a manager for Node objects, you must provide a way to add values. There are three ways to add values to a linked list, each having its own unique performance characteristics:

Pushing to the Front of a List

Adding a value at the front of the list is known as a push operation. This is also known as head-first insertion. The code for it is refreshingly simple.

Appending to the End of a List

The next operation you’ll look at is append. This is meant to add a value at the end of the list, and it’s known as tail-end insertion.

Inserting in Middle of a List

The third and final operation for adding values is insertAfter. This operation inserts a value after a particular node in the list, and requires two steps:

Performance

Whew! You’ve made good progress so far. To recap, you’ve implemented the three operations that add values to a linked list and a method to find a node at a particular index.

Nurohiij duzq iwzuql ocloxvAmrak ninaAt Luta hubpzufutn etzuyq ep voic ohwuff oy kiot anjuzl obloc u pita qawiytk o jonu ob coqep ugvin O(6) E(0) I(3) U(u), xzobu o ih rdi levog esvik

Removing Values From a List

There are three main operations for removing nodes:

Popping From the Front of a List

Removing a value at the front of a linked list is often referred to as pop. This operation is almost as simple as push, so dive right in.

Removing From the End of a List

Removing the last node of the list is somewhat inconvenient. Although you have a reference to the tail node, you can’t chop it off without getting the reference to the node before it. Thus, you’ll have to do an arduous traversal.

Removing a Value From the Middle of a List

The final remove operation is removing a node at a particular point in the list. This is achieved much like insertAfter. You’ll first find the node immediately before the node you wish to remove and then unlink it.

9 2 7 3 7 6
Pivabuxg hmu godcju puwi

Performance

You’ve hit another checkpoint! To recap, you’ve implemented the three operations that remove values from a linked list:

Legewuaz buq taxudeNakw fuzofoEdruq Dixi geymjiturb riyogu on noam foduqo il heib buweye xsu zabr sepi E(9) U(v) A(6)

Making a List Iterable

With most Dart collections, you can iterate through them using a for loop. For example, here is a basic implementation of looping through a standard list:

What’s an Iterator?

An iterator tells an iterable class how to move through its elements. To make an iterator, you create a class that implements the Iterator interface. This abstract class has the following simple form:

Creating an Iterator

Now that you know what an iterator is, you can make one yourself. Create the following incomplete class below LinkedList:

Implementing current

First add the following code for current:

Implementing moveNext

Add the missing moveNext method now:

Looping Through a List

Now that your iterator is finished, you can use it in your LinkedList. Replace the unimplemented iterator getter that you added earlier to LinkedList with the following:

Challenges

These challenges will serve to solidify your knowledge of data structures. You can find the answers at the end of the book and in the supplemental materials.

Challenge 1: Find the Middle Node

Create a function that finds the middle node of a linked list. For example:

Challenge 2: Reverse a Linked List

Create a function that reverses a linked list. You do this by manipulating the nodes so that they’re linked in the other direction. For example:

Challenge 3: Remove All Occurrences

Create a function that removes all occurrences of a specific element from a linked list. The implementation is similar to the removeAfter method that you implemented earlier. For example:

Key Points

  • Linked lists are linear and unidirectional. As soon as you move a reference from one node to another, you can’t go back.
  • Linked lists have O(1) time complexity for head first insertions, whereas standard lists have O(n) time complexity for head-first insertions.
  • Implementing the Dart Iterable interface allows you to loop through the elements of a collection as well as offering a host of other helpful methods.

Where to Go From Here?

The nodes in this chapter only pointed to the next node in the list. This type of linked list is called a singly linked list. If a node also points to the previous node, this is called a doubly linked list.

4. Stacks
6. Queues
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2026 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now