Every Built-in Method: Queue, LinkedList & the rest of dart:collection
After this lesson you will know how a stack, a queue and a deque are built inside Dart (a ring buffer, a chain of nodes, a list whose items are the nodes), why list.removeAt(0) is O(n) while queue.removeFirst() is O(1), and you will have seen every public member of Queue, ListQueue, DoubleLinkedQueue, DoubleLinkedQueueEntry, LinkedList, LinkedListEntry, the Unmodifiable...View wrappers, MapView, and the build-your-own bases ListBase, SetBase and MapBase, each with its cost, the exceptions it can throw, whether it changes the object, and a runnable example whose exact output was produced by the real Dart SDK. You will then use a queue for breadth-first search, a deque for a sliding-window maximum, and a stack for "next greater element".
Related lessons: D08 collections internals, D22 mutable vs immutable, D26 every List method, D27 every Set and Map method (HashMap, LinkedHashMap, SplayTreeMap and the sets are there), and the Stacks, Queues, Linked Lists lesson (the algorithmic version of everything here). Source of truth: the Dart SDK 3.11 sources collection/queue.dart, collection/linked_list.dart, collection/list.dart, collection/set.dart, collection/maps.dart, collection/collections.dart, collection/iterator.dart and internal/internal.dart (DoubleLinkedQueueEntry). All complexities describe the native VM. Every printed result in this lesson was produced by running the code on Dart 3.11 and is asserted in verify/d28.dart. Everything here needs import 'dart:collection';.
1. Stack, queue, deque: the three shapes
A stack is a pile of plates: you put a plate on top and you take a plate from the top, so the last plate in is the first out (LIFO). A queue is the line at a ticket counter: people join at the back and are served from the front, so the first in is the first out (FIFO). A deque (say "deck", short for double-ended queue) is a train carriage with a door at each end: you may board or leave at the front and at the back.
These are shapes of use, not memory layouts. Dart gives you three different memory layouts that can play them, and the lesson is about choosing well. A ring buffer is an array treated as a circle. A linked list is a chain of small objects ("nodes"), each holding links (references) to its neighbours. Complexity is how the number of steps grows with the number n of elements; O(1) means "the same few steps whatever n is", O(n) means "about n steps".
| Shape | Add | Remove | In Dart |
|---|---|---|---|
| Stack (LIFO) | at the end | from the end | List: add, removeLast, last |
| Queue (FIFO) | at the back | from the front | Queue: add / addLast, removeFirst, first |
| Deque | front or back | front or back | Queue: addFirst, addLast, removeFirst, removeLast |
Dart has no separate Stack class because a List already makes a perfect stack: its end is the cheap end.
Why list.removeAt(0) is O(n)
A List keeps element 0 in array slot 0, element 1 in slot 1, and so on, with no gaps. Taking the first element out leaves a hole in slot 0, and the only way to close it is to slide every later element one slot to the left: n − 1 copies. Doing that to empty a list of n elements costs (n−1) + (n−2) + … + 0 = n(n−1)/2 copies: 45 for n = 10, about 5×109 for n = 105 (seconds), 5×1011 for n = 106 (minutes). A queue avoids the copies by never moving elements: it moves a head index instead. Step through it, then change n.
Input size → feasible: n ≤ 103 elements removed from the front of a list is harmless (5×105 copies); n = 105 is already too slow for a 1-second limit; use a Queue from there on. Taking from the end of a list (removeLast) is always O(1).
List is cheap. A Queue (ring buffer) has two cheap ends. A LinkedList or DoubleLinkedQueue has cheap ends and cheap insert/remove next to a node you already hold.2. ListQueue inside: the ring buffer
Picture a round sushi conveyor belt with 8 numbered plates slots. A pointer called head marks the first plate in the queue; a pointer called tail marks the next empty slot. Serving a customer moves head one slot along the belt; adding a dish drops it on the slot at tail and moves tail one slot. When a pointer passes slot 7 it comes round to slot 0 again: the belt is a ring, nothing is ever shifted. If head and tail meet after an add, the belt is full and the restaurant swaps it for a belt twice as long.
Technically a ListQueue object has four fields: _table (a fixed-length array), _head, _tail and _modificationCount (used to detect changes during iteration). The table length is always a power of two (8, 16, 32, …; the minimum is 8). That makes "go to the next slot, wrapping round" a single bit operation: (i + 1) & (capacity - 1). For capacity 8, capacity - 1 is 0b111, so & 7 keeps only the last three bits: 7 + 1 = 8 = 0b1000 becomes 0b000 = 0, and −1 (all one-bits) becomes 0b111 = 7. No division is needed.
Rules read off queue.dart: empty means head == tail. add stores at tail and moves it forward; addFirst moves head backwards first and then stores; removeFirst clears the head slot and moves head forward; removeLast moves tail backwards and clears that slot. After an add, if head == tail again the table has become completely full, which would look exactly like "empty", so it is grown at once: allocate a table of twice the size, copy the part from head to the end of the old table to the front of the new one, then the part before head behind it, set head = 0 and tail = old capacity. Doubling makes the copies amortised O(1) per add (see D26 for the same argument for lists).
Watch the four things that matter: the object with its two indexes, the table, the wrap-around, and the growth. The first player fills an 8-slot ring; the second makes the tail wrap past the end; the third makes the head wrap backwards; the fourth shows an empty queue, a removal in the middle and clear. The last one is yours: type any script (the format is explained in the box under the player).
Script format: start with a list [1,2,3] (= ListQueue.of), or from[1,2,3] (= ListQueue.from), or cap 16 (= ListQueue(16)); then operations separated by ;: add 5, addLast 5, addFirst 5, removeFirst, removeLast, remove 5, addAll [1,2], clear. Values are whole numbers from -999 to 999, at most 12 values per list, 12 operations, and the table may not exceed 64 slots. The capacity is an implementation detail you cannot read from Dart; these pictures follow the Dart 3.11 sources.
ListQueue never shrinks: after a burst of 106 elements the table stays large until the queue object is dropped. clear() empties it but keeps the table. Input size → feasible: a queue holding 107 ints needs a table of up to 224 = 16.7 million slots (about 134 MB of references); fine on a laptop, careful on a phone.ListQueue member. You can write the same data structure yourself in about 40 lines: see the interview question Write your own growable deque (ring buffer) below, which is tested against the real ListQueue on thousands of random operations.3. Every member, grouped by type
Each card shows: the signature, what it means in plain words, a badge telling you what happens to the object, the cost and why, the exceptions, and a runnable example with its exact output. Some cards cover several members that are one-line variations of each other (the card lists them all); every member still appears with its own line of code in the example. The Members line under each heading names exactly which SDK members the card covers.
| Badge | Meaning |
|---|---|
| mutates | changes this object (its contents, length or links) |
| returns new | builds a new object (list, set, string); the original is untouched |
| lazy view | returns a cheap wrapper that reads the original when used; nothing is copied now, later changes show through |
| read-only | reads or reports; changes nothing, allocates nothing important |
| creates | a constructor (or a type alias): makes a new object |
| blocked | exists only to throw UnsupportedError (the mutators of an unmodifiable view) |
Queue, 24 of ListQueue, 24 of DoubleLinkedQueue, 7 of DoubleLinkedQueueEntry, 14 of LinkedList, 7 of LinkedListEntry, 25 of UnmodifiableListView, 14 of UnmodifiableSetView, 23 of MapView, 11 of UnmodifiableMapView, 1 of UnmodifiableMapBase, 64 of ListBase, 46 of SetBase, 24 of MapBase, 3 of HasNextIterator, 5 of the five aliases (constructors, factories, getters, setters, operators, methods and static helpers; the members you must write yourself in a base class count too). Deprecated: only HasNextIterator is marked @Deprecated in Dart 3.11 (the typedefs ListMixin, MapMixin, SetMixin carry a "use the Base name" note in the source but no annotation). Not repeated here: HashMap, LinkedHashMap, HashSet, LinkedHashSet, SplayTreeMap, SplayTreeSet belong to D27; IterableExtensions and NullableIterableExtensions (firstOrNull, indexed, …) to D26/D25; UnmodifiableListBase is internal (not exported). Inherited and not overridden members (for example where or fold on a ListQueue) are the plain Iterable ones (lesson D25) and are covered where a base class re-implements them (the ListBase and SetBase cards).Player scripts below use a small mini-language so you can type your own experiments; the box under each custom player lists its words. A predicate P is even, odd, >N, <N or =N.
Index of every member (click a name to jump to its card)
3.1 The Queue interface (shared by ListQueue and DoubleLinkedQueue)
Queue<E> is an interface (a list of promises) with two implementations: ListQueue (ring buffer, the default) and DoubleLinkedQueue (chain of nodes). Every card in this group runs the same code on both and shows both costs. A Queue is also an Iterable, so for-in, map, where, toList and the other Iterable members work too (lesson D25). Input size → feasible: 107 add / removeFirst pairs run in well under a second; the dangerous calls are remove(value), removeWhere and retainWhere on a ListQueue (each match can shift up to n/2 slots).
3.2 ListQueue only
These are the members ListQueue declares or overrides itself, mostly because the ring buffer can answer them faster than the generic Iterable versions: length from two indexes, elementAt by arithmetic, toList by a straight copy.
3.3 DoubleLinkedQueue and DoubleLinkedQueueEntry
A DoubleLinkedQueue is a conga line where every dancer holds the shoulders of the dancer in front (previous) and behind (next). A hidden dancer called the sentinel S stands between the last and the first, so the line is a circle and there are no special cases for "empty" or "at the end". To add or remove anywhere you only change who holds whose shoulders: four pointer writes, no shifting. The price: one extra object per element and no index access (elementAt(i) walks i steps).
DoubleLinkedQueueEntry is a handle to one node. firstEntry(), lastEntry(), nextEntry() and previousEntry() give you handles; with one you can append, prepend, remove or overwrite element in O(1), which a List or ListQueue cannot do. Positions in the scripts are counted from 0 and mean "start at firstEntry() and step nextEntry() that many times".
Script format: a list [1,2,3] (= DoubleLinkedQueue.of, at most 10 values), then ;-separated: add x, addLast x, addFirst x, removeFirst, removeLast, remove x, append i x, prepend i x, removeEntry i, setEntry i x, removeWhere P, retainWhere P, clear (i is a position from 0, at most 12 operations).
DoubleLinkedQueue members
DoubleLinkedQueueEntry members
3.4 LinkedList and LinkedListEntry
A DoubleLinkedQueue is like a carriage of passengers who hold hands only while they are in the carriage. A LinkedList is different: each passenger wears the handles sewn into their own coat. The class of your items is the node (it extends LinkedListEntry), so there is no separate node object. That is called an intrusive list. Because each item knows its list and its neighbours, it can unlink itself from anywhere in O(1), and contains is O(1). The price: an item can be in only one list at a time, and every item must be a LinkedListEntry.
The entries form a circle (the last entry's hidden _next is the first entry), so last is just first._previous. The public getters next and previous hide the circle and return null at the ends. Entries below are Item objects (base class Item extends LinkedListEntry<Item> with one int v, shown in the Build-your-own section below). Input size → feasible: 106 entries means 106 objects (each with three extra fields); add, unlink, insertAfter are O(1), but there is no []: reaching position i costs i steps.
Script format: a list [1,2,3] of Item values (at most 10), then ;-separated: add x, addFirst x, unlink i, remove i, insertAfter i x, insertBefore i x, addAgain i (adds an entry that is already linked: StateError), next i, previous i, first, last, clear. Positions i count from 0 (the code uses list.elementAt(i) to fetch the entry).
LinkedList members
LinkedListEntry members
3.5 Unmodifiable views and MapView
A view is a small object that holds a reference to another collection and forwards calls to it. UnmodifiableListView, UnmodifiableSetView and UnmodifiableMapView are views whose mutating methods throw UnsupportedError. MapView is the plain forwarding wrapper (base class for decorators). The crucial difference from List.unmodifiable(src), Set.unmodifiable(src) and Map.unmodifiable(src) (see D22): the constructors copy into a frozen copy, the view classes do not copy, so they show every later change to the source. Step through it for lists, then for maps and sets.
Script format: a list [3,1,2] (at most 8 values; src, view and copy are created from it), then ;-separated: src add x, src removeLast, src set i x, view add x, view set i x, view print, view length, copy add x, copy set i x, copy print, copy length.
3.6 Build your own: ListBase, SetBase, MapBase (and the rest)
Suppose you want a collection that behaves like a List, Set or Map but stores or checks things differently (a case-insensitive map, a list that logs, a fixed-size ring). Implementing List directly means writing ~60 members. The base classes ListBase, SetBase and MapBase write almost all of them for you in terms of a few primitive members that you provide: 4 for a list (length, length=, [], []=), 7 for a set, 5 for a map. Here are the three tiny classes the cards use (all verified; they are deliberately simple, not fast). TraceBox is Box plus a log, and Item / Countdown are used in the LinkedList and IterableBase cards.
Because every derived member calls your primitives, the cost of a ListBase member = (number of primitive calls) × (cost of your primitive). The next players use TraceBox to show exactly which primitives ListBase calls, in order. This is also why your length setter must be able to grow the collection: add is literally this[this.length++] = element.
Script format: a list [5,6] (at most 8 values), then ;-separated: add x, removeLast, clear, first, indexOf x, removeAt i, insert i x. These traces assume asserts are off (the default for dart run and release builds); with asserts on (Flutter debug mode), addAll additionally checks length once per element.
ListBase
SetBase
MapBase
HasNextIterator and the type aliases
4. Algorithms: BFS, sliding-window maximum, monotonic stack
This is why these structures exist. Each player runs the very function shown beside it (the same text is in verify/d28.dart, where it is compared with a brute-force version on random inputs). Edit the input and press Run.
4.1 Breadth-first search: a Queue as the frontier
BFS explores a graph (dots joined by lines) in rings: first the start, then everything one step away, then two steps, and so on. The queue holds the discovered-but-not-yet-explored vertices; first in, first out means closer vertices are always explored before farther ones, so the first time you reach a vertex is by a shortest route. Cost: O(V + E) with removeFirst in O(1); with List.removeAt(0) every dequeue would copy the whole frontier. Input size → feasible: V, E up to 106 run in about a second with a Queue. The full algorithm is in the BFS, DFS, Topological Sort, SCC lesson; the queue operations are covered in the Stacks, Queues, Linked Lists lesson as enqueue and dequeue.
Input: edges as a-b separated by commas (single-digit vertices 0..9, at most 20 edges, undirected), then ; and the start vertex.
4.2 Sliding-window maximum: a deque of indexes
For every window of k neighbouring numbers we want the largest. The trick: keep a deque of indexes whose values decrease from front to back. A newcomer that is bigger than the numbers at the back makes them useless forever (it is larger and will stay in the window longer), so they are popped from the back; an index that has slid out of the window is dropped from the front. The front is always the window maximum. Both ends are used, which a stack or a plain queue cannot do, and each index is added once and removed once: O(n) instead of O(n·k). Input size → feasible: n = 105, k = 5×104: the naive rescan is 2.5×109 steps, the deque about 3×105.
Input: the array (1 to 14 whole numbers), then ; and k (1 to the array length).
4.3 Monotonic stack: next greater element
"For each number, find the first larger number to its right." A stack of indexes still waiting for an answer, with values that never increase from bottom to top ("monotonic"), solves it in one pass: when the new value is bigger than the top, it is the answer for the top, so the top is popped and answered, repeatedly. Everything left on the stack at the end has no answer. The same stack idea solves "daily temperatures", the largest rectangle in a histogram and trapping rain water (see the question bank). Input size → feasible: n = 106 in a few milliseconds; the naive "scan right from every element" is O(n²) = 1012 on a decreasing array.
Input: 1 to 14 whole numbers separated by commas.
5. Mutable vs immutable: views, copies, aliases
"Mutable" means the object can change after it is made. Everything in dart:collection that is a queue or linked list is mutable, and Dart has no unmodifiable queue and no const queue (the constructors are not const). The immutable-style tools are the views and the copies:
| Type | Can change after creation? | Live view of a source | Frozen copy | Notes |
|---|---|---|---|---|
ListQueue, DoubleLinkedQueue | yes, always | UnmodifiableListView(queue) (read-only list over the queue; elementAt is O(1) for ListQueue, O(i) for DoubleLinkedQueue) | queue.toList() or List.unmodifiable(queue) | iterating while adding/removing throws ConcurrentModificationError |
LinkedList + entries | yes, always | none (an entry belongs to one list) | list.toList() (new list, same entry objects!) | the copied list still shares the entries: entry.unlink() affects the original |
List | depends (growable / fixed / unmodifiable / const) | UnmodifiableListView(list) | List.unmodifiable(list) | D26, D22 |
Set | depends | UnmodifiableSetView(set) | Set.unmodifiable(set) | D27 |
Map | depends | UnmodifiableMapView(map) | Map.unmodifiable(map) | MapView(map) is a modifiable forwarding view |
Aliases, shallow copies and views in one go (each line was run on Dart 3.11):
Three rules follow. 1. Aliasing: b = a copies only the reference, so a and b are the same queue. 2. Shallow copy: Queue.of(a) makes a new queue but the elements are the same objects (a queue of lists shares the inner lists). 3. A read-only view of something you keep changing is not immutable: hand out UnmodifiableListView(x) only when you want callers to watch your changes, and a frozen copy when you want a snapshot. Changing while looping: ListQueue, DoubleLinkedQueue and LinkedList all throw ConcurrentModificationError on the next step; forEachEntry on a DoubleLinkedQueue is the safe way to remove while walking.
UnmodifiableListView(listOfLists)[0].add(1) works, because it is the inner list that is changed. For deep immutability you need frozen copies all the way down (D22).6. Choosing the right structure
Complexities are for n elements on the native VM; "amortised" means averaged over many calls (an occasional call is slower because it copies).
| Operation | List | ListQueue | DoubleLinkedQueue | LinkedList | Set (LinkedHashSet) |
|---|---|---|---|---|---|
| read by index | O(1) | O(1) (elementAt) | O(i) walk | no index (O(i) walk) | no index |
| add at the end | O(1) amortised | O(1) amortised | O(1) | O(1) | O(1) expected |
| add / remove at the front | O(n) (everything shifts) | O(1) amortised | O(1) | O(1) | n/a |
| remove from the end | O(1) | O(1) | O(1) | O(1) via last.unlink() | n/a |
| insert / remove next to a position you hold | O(n) | O(n) | O(1) with an entry | O(1) (insertAfter, unlink) | remove O(1) expected |
| remove by value | O(n) | O(n) | O(n) find, O(1) unlink | O(1) if you hold the entry | O(1) expected |
contains | O(n) | O(n) | O(n) | O(1) (identity of the entry) | O(1) expected |
| duplicates / order | yes / by index | yes / by position | yes / by position | entry in one list only / by position | unique / insertion order |
| memory per element | 1 slot + spare capacity | 1 slot + spare (table up to 2× the elements) | 1 node object (element, 2 links, owner) | 0 extra objects, 3 extra fields in your item | hash entry |
| iterate while modifying | ConcurrentModificationError | ConcurrentModificationError | ConcurrentModificationError (use forEachEntry) | ConcurrentModificationError | ConcurrentModificationError |
| You need… | Use | Why |
|---|---|---|
| a stack (LIFO) | List with add / removeLast | the end of an array is the cheap end; contiguous memory is fast |
| a queue (FIFO), BFS frontier, task buffer | Queue (= ListQueue) | O(1) at both ends without per-element objects |
| a deque (sliding window, 0-1 BFS) | Queue | same: addFirst / addLast / removeFirst / removeLast are all O(1) |
| to insert/remove at a spot you already found | DoubleLinkedQueue + entries, or LinkedList | O(1) neighbours rewiring |
| an LRU cache or an ordered "recent use" list | LinkedList + a Map from key to entry | the map finds the entry in O(1), the entry unlinks itself in O(1) (see the question bank) |
| to give callers read-only access | UnmodifiableListView / UnmodifiableSetView / UnmodifiableMapView, or a frozen copy | view = cheap and live; copy = snapshot |
| a custom collection type | extends ListBase / SetBase / MapBase | write 4 / 7 / 5 primitives, get the rest |
Rule of thumb: default to List; reach for Queue the moment you remove from the front; reach for LinkedList only when you really need O(1) removal of a node you already hold (it is rarely the fastest in practice because nodes are scattered in memory, while arrays are contiguous and cache-friendly). Input size → feasible: for n ≤ 103 any of them is fine; the choice matters from n ≈ 105 upward.
Quiz
Interview questions
Cheat sheet: every member
Generated from the same member data as the cards above: every member with its cost and whether it mutates or returns something new.