Data Structures, Algorithms and Programming Patterns · Part 3 of 9

Data Structures and Algorithms, Part 3: Stacks, Queues, Deques and Linked Lists

Some data structures are defined less by how they store things and more by the rules they enforce. This part covers linked lists, which are built from nodes and pointers, and then stacks, queues and deques, which control the order in which things come out. You will build each one, see its cost, and solve classic problems with them.

1. Linked lists: the idea

In Part 2 you met the array: items stored side by side in one block of memory. That layout makes reading arr[5] instant, but it makes inserting at the front slow, because every other item has to shuffle along.

A linked list takes the opposite deal. Items are not side by side. Each item lives in its own small box called a node, and each node holds two things: the value, and a pointer (also called a reference) to the next node. A pointer is just the address of another object. The last node points to nothing, which we write as null.

Because we only hold head, every other node is reachable only by walking. That one fact explains the whole cost table later in this part.

Inserting at the front

To add a new first item, make a node, point it at the old head, then move head to the new node. Two pointer changes, no shuffling, so it is O(1).

2. Build a singly linked list in Kotlin

We need just one small class. A node has a value and a nullable next. In Kotlin, Node? means “a Node or null”, which is exactly what a pointer that might point to nothing needs.

class Node(var value: Int, var next: Node? = null)

Then a list class that remembers head and the size. Read the comments: each method says what it costs.

class Node(var value: Int, var next: Node? = null)

class MyLinkedList {
    var head: Node? = null
    var size = 0
        private set

    // O(1): the new node becomes the head.
    fun addFirst(value: Int) {
        head = Node(value, head)
        size++
    }

    // O(n): we must walk to the end, because we only hold the head.
    fun addLast(value: Int) {
        val node = Node(value)
        val first = head
        if (first == null) {
            head = node
        } else {
            var cur: Node = first
            while (cur.next != null) cur = cur.next!!
            cur.next = node
        }
        size++
    }

    // O(n): walk until we find it (worst case, it is last or missing).
    fun contains(value: Int): Boolean {
        var cur = head
        while (cur != null) {
            if (cur.value == value) return true
            cur = cur.next
        }
        return false
    }

    // O(n) to find it, O(1) to unlink it.
    fun remove(value: Int): Boolean {
        val first = head ?: return false
        if (first.value == value) {          // removing the head is a special case
            head = first.next
            size--
            return true
        }
        var prev: Node = first
        while (true) {
            val cur = prev.next ?: return false
            if (cur.value == value) {
                prev.next = cur.next          // skip over it: one pointer change
                size--
                return true
            }
            prev = cur
        }
    }

    override fun toString(): String {
        val parts = ArrayList<String>()
        var cur = head
        while (cur != null) { parts.add(cur.value.toString()); cur = cur.next }
        return parts.joinToString(" -> ", postfix = " -> null")
    }
}

fun main() {
    val list = MyLinkedList()
    list.addFirst(3)
    list.addFirst(7)      // 7 -> 3
    list.addLast(9)       // 7 -> 3 -> 9
    println(list)
    println("contains 3? ${list.contains(3)}   contains 4? ${list.contains(4)}")
    println("remove 3: ${list.remove(3)}  -> $list")
    println("remove 7: ${list.remove(7)}  -> $list   (that was the head)")
    println("remove 42: ${list.remove(42)}  size=${list.size}")
}

Notice how remove works. To delete a node we need the node before it, so that we can make that earlier node point past the victim. That is why the loop tracks prev.

3. Three classic list tricks: reverse, middle, cycle

These three small problems appear in almost every course, because they teach you to think in pointers. Draw them on paper before you code them.

Reversing a list

Walk down the list and flip each pointer to face backwards. You need three variables: prev (the already-reversed part), cur (the node you are fixing) and next (saved first, so you do not lose the rest of the list).

Finding the middle

Use two pointers that start together. The fast pointer moves two nodes per step, the slow pointer moves one. When fast reaches the end, slow is halfway. One pass, no need to know the length.

class Node(var value: Int, var next: Node? = null)

fun fromList(items: List<Int>): Node? {
    var head: Node? = null
    for (x in items.reversed()) head = Node(x, head)
    return head
}

fun toList(head: Node?): List<Int> {
    val out = ArrayList<Int>()
    var cur = head
    while (cur != null) { out.add(cur.value); cur = cur.next }
    return out
}

fun reverse(head: Node?): Node? {
    var prev: Node? = null
    var cur = head
    while (cur != null) {
        val next = cur.next     // 1. remember the rest
        cur.next = prev         // 2. flip the pointer
        prev = cur              // 3. move both forward
        cur = next
    }
    return prev                 // prev ends on the old last node: the new head
}

fun middle(head: Node?): Node? {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow!!.next
        fast = fast.next!!.next
    }
    return slow
}

fun main() {
    val list = fromList(listOf(1, 2, 3, 4, 5))
    println("middle of 1..5 = ${middle(list)?.value}")                       // 3
    println("middle of 1..4 = ${middle(fromList(listOf(1, 2, 3, 4)))?.value}") // 3 (second of two)
    println("reversed: ${toList(reverse(list))}")
    println("reverse empty: ${toList(reverse(null))}")
}

Detecting a cycle

Normally the last node points to null. If a bug makes some node point back to an earlier one, the list becomes a loop, and walking it would never end. How can you tell without walking forever?

The two-speed trick again, known as Floyd’s tortoise and hare. Slow moves one step, fast moves two. If there is no cycle, fast falls off the end. If there is a cycle, both run round it, and the fast one gains one step per lap on the slow one until they stand on the same node.

class Node(var value: Int, var next: Node? = null)

fun hasCycle(head: Node?): Boolean {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow!!.next
        fast = fast.next!!.next
        if (slow === fast) return true      // === compares identity: the very same node
    }
    return false
}

fun main() {
    val a = Node(1); val b = Node(2); val c = Node(3); val d = Node(4)
    a.next = b; b.next = c; c.next = d
    println("straight list: ${hasCycle(a)}")   // false
    d.next = b                                  // close a loop: 4 points back to 2
    println("with a loop:   ${hasCycle(a)}")   // true
    println("empty list:    ${hasCycle(null)}") // false
}

4. Doubly linked lists, and lists versus arrays

A doubly linked list gives each node two pointers: next and prev. You can walk both ways, and if you already hold a node, you can remove it in O(1) without hunting for its predecessor.

The price is one extra pointer per node, and a bit more care when changing links (four pointer updates instead of two). Java’s LinkedList is a doubly linked list. Real uses include an editor’s list of lines, a browser’s back and forward history, and the least-recently-used cache.

class DNode(var value: Int) {
    var prev: DNode? = null
    var next: DNode? = null
}

// Insert `node` right after `at`: four pointer updates.
fun insertAfter(at: DNode, node: DNode) {
    node.prev = at
    node.next = at.next
    at.next?.prev = node
    at.next = node
}

// Unlink a node we already hold: O(1).
fun unlink(node: DNode) {
    node.prev?.next = node.next
    node.next?.prev = node.prev
}

So, lists or arrays?

On paper, linked lists win at inserting and deleting in the middle (once you hold the spot). Arrays win at reading by position. In practice, arrays usually win overall, for two reasons:

• Cache. A computer loads memory in chunks. Array items sit side by side, so one load brings in many neighbours for free. Linked nodes are scattered, so each step may need a fresh, slow trip to memory.
• Memory. Every node carries a pointer, and often an object header too. A list of numbers can take several times the memory of an array of the same numbers.

5. Stacks: last in, first out

A stack allows work at one end only, called the top. The last item you put in is the first one to come out. This rule is called LIFO: last in, first out.

A stack has three core operations:

• push(x): put x on top.
• pop(): remove and return the top item.
• peek(): look at the top item without removing it.

Implementing a stack

You do not need to write a node class. Kotlin’s ArrayDeque is a resizable array that is fast at both ends, so a stack is just addLast to push and removeLast to pop. Wrapping it in a small class makes the intent obvious.

class Stack<T> {
    private val items = ArrayDeque<T>()
    fun push(x: T) = items.addLast(x)                 // O(1) on average
    fun pop(): T = items.removeLast()                 // O(1); throws if empty
    fun peek(): T? = items.lastOrNull()               // O(1); null if empty
    fun isEmpty() = items.isEmpty()
    val size get() = items.size
}

fun main() {
    val s = Stack<Int>()
    s.push(1); s.push(2); s.push(3)
    println("peek=${s.peek()} size=${s.size}")
    println("pop=${s.pop()} pop=${s.pop()} left=${s.size}")

    // Undo: remember each edit on a stack, undo by popping the latest.
    var text = ""
    val history = Stack<String>()
    for (word in listOf("Hello", " there", " world")) {
        history.push(text)       // save the state BEFORE the change
        text += word
        println("typed -> \"$text\"")
    }
    while (!history.isEmpty()) {
        text = history.pop()
        println("undo  -> \"$text\"")
    }
}

Where stacks show up

• Undo and redo in editors, as in the demo.
• The call stack. When function a calls b, which calls c, the computer pushes a frame for each call. When c returns, its frame is popped and b continues. This is why too-deep recursion ends in a stack overflow: the stack ran out of room.
• Matching brackets and parsing, below.
• Depth-first search, which you will see in Part 5.

Balanced brackets

Is {[()]} well formed? Is ([)]? Scan left to right. Push every opening bracket. On a closing bracket, the top of the stack must be its matching opener; pop it. At the end the stack must be empty. The most recent unclosed opener is always the one that must close first, which is LIFO again.

fun isBalanced(s: String): Boolean {
    val pairs = mapOf(')' to '(', ']' to '[', '}' to '{')
    val stack = ArrayDeque<Char>()
    for (c in s) {
        when {
            c in pairs.values -> stack.addLast(c)                       // opener: push
            c in pairs.keys -> {                                         // closer: must match top
                if (stack.isEmpty() || stack.removeLast() != pairs[c]) return false
            }
            // any other character is ignored
        }
    }
    return stack.isEmpty()      // leftover openers mean it is not balanced
}

fun main() {
    for (s in listOf("{[()]}", "([)]", "((", "", "a(b)c")) {
        println("%-8s -> %s".format("\"$s\"", isBalanced(s)))
    }
}

Evaluating postfix

We usually write maths infix: (3 + 4) * 2. Postfix (also called reverse Polish notation) puts the operator after its operands: 3 4 + 2 *. It needs no brackets and no precedence rules, and a stack evaluates it in one pass: push numbers; on an operator, pop two numbers, apply it, push the result.

fun evalPostfix(tokens: List<String>): Int {
    val stack = ArrayDeque<Int>()
    for (t in tokens) {
        when (t) {
            "+", "-", "*", "/" -> {
                val right = stack.removeLast()     // popped first: the RIGHT operand
                val left = stack.removeLast()
                stack.addLast(when (t) {
                    "+" -> left + right
                    "-" -> left - right
                    "*" -> left * right
                    else -> left / right
                })
            }
            else -> stack.addLast(t.toInt())
        }
    }
    return stack.removeLast()
}

fun main() {
    println(evalPostfix("3 4 + 2 *".split(" ")))        // (3 + 4) * 2 = 14
    println(evalPostfix("5 1 2 + 4 * + 3 -".split(" ")))  // 5 + (1+2)*4 - 3 = 14
    println(evalPostfix("10 2 -".split(" ")))             // 8, not -8: order matters
}

6. Queues: first in, first out

A queue is the fair line at a shop. Items join at the back and leave from the front. The first one to arrive is the first one served: FIFO, first in, first out.

• enqueue(x): join the back of the line.
• dequeue(): remove and return the front item.
• peek(): look at the front item.

With ArrayDeque a queue is addLast to enqueue and removeFirst to dequeue. Both are O(1) on average.

Warning: do not build a queue on a plain ArrayList by calling removeAt(0). Removing the first item shifts all the others, so each dequeue costs O(n).

A tiny circular buffer

How can an array give a fast queue? Keep a head index (where the front is) and a count. When an index runs off the end, wrap around to 0 using the remainder operator %. No shuffling is ever needed, so the array behaves like a ring. This is what ArrayDeque does inside, with extra code to grow when it is full.

class RingQueue(private val capacity: Int) {
    private val data = IntArray(capacity)
    private var head = 0          // index of the front item
    var size = 0
        private set

    fun enqueue(x: Int): Boolean {
        if (size == capacity) return false          // full
        data[(head + size) % capacity] = x          // wrap around with %
        size++
        return true
    }

    fun dequeue(): Int? {
        if (size == 0) return null                  // empty
        val x = data[head]
        head = (head + 1) % capacity
        size--
        return x
    }
}

fun main() {
    val q = RingQueue(3)
    println(listOf(q.enqueue(1), q.enqueue(2), q.enqueue(3), q.enqueue(4)))  // last is false: full
    println("dequeue -> ${q.dequeue()}")      // 1
    println("enqueue 5 -> ${q.enqueue(5)}")    // true: it reuses the freed slot
    val out = ArrayList<Int?>()
    repeat(4) { out.add(q.dequeue()) }
    println(out)                               // [2, 3, 5, null]
}

Where queues show up

• Task scheduling: print jobs, web requests waiting for a server, messages waiting to be handled. Fairness is the whole point.
• Buffers: keyboard input and network data wait their turn.
• Breadth-first search (BFS): visiting things in rings, nearest first. A preview follows; Part 5 explains it fully.

fun main() {
    // Who is connected to whom. Start at A and visit nearest first.
    val friends = mapOf(
        "A" to listOf("B", "C"),
        "B" to listOf("D"),
        "C" to listOf("D", "E"),
        "D" to listOf("F"),
        "E" to listOf("F"),
        "F" to emptyList()
    )
    val queue = ArrayDeque<String>()
    val seen = HashSet<String>()
    queue.addLast("A"); seen.add("A")
    val order = ArrayList<String>()
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()           // the one that has waited longest
        order.add(node)
        for (next in friends.getValue(node)) {
            if (seen.add(next)) queue.addLast(next)   // join the back, once only
        }
    }
    println(order)     // [A, B, C, D, E, F]: A, then its neighbours, then theirs
}

7. Deques: both ends

A deque (say “deck”, short for double-ended queue) lets you add and remove at both ends in O(1). It is more general than a stack or a queue, which is why Kotlin’s one ArrayDeque class can act as either.

fun isPalindrome(text: String): Boolean {
    val dq = ArrayDeque<Char>()
    for (c in text) if (c.isLetterOrDigit()) dq.addLast(c.lowercaseChar())
    while (dq.size > 1) {
        if (dq.removeFirst() != dq.removeLast()) return false   // compare the two ends
    }
    return true
}

fun main() {
    println(isPalindrome("A man, a plan, a canal: Panama"))   // true
    println(isPalindrome("kotlin"))                            // false
    println(isPalindrome(""))                                  // true
}

Deques also power a few clever tricks, such as sliding-window maximum, which Part 8 covers. For now, remember: if you need both ends, reach for ArrayDeque.

8. A classic puzzle: a queue from two stacks

Can you build a FIFO queue when the only tool you have is two LIFO stacks? Yes, and it teaches something deep: reversing the order twice gives back the original order.

Keep an in stack and an out stack.

• enqueue(x): push onto in.
• dequeue(): if out is empty, pour everything from in into out (this reverses it, so the oldest item lands on top). Then pop out.

Pouring costs O(n) once, but each item is poured exactly once in its life. So over many operations the average cost per call is O(1). We call that amortised O(1): expensive occasionally, cheap on average.

class QueueFromStacks {
    private val inbox = ArrayDeque<Int>()    // used only as a stack
    private val outbox = ArrayDeque<Int>()   // used only as a stack

    fun enqueue(x: Int) { inbox.addLast(x) }

    fun dequeue(): Int {
        if (outbox.isEmpty()) {
            while (inbox.isNotEmpty()) outbox.addLast(inbox.removeLast())   // pour: reverses order
        }
        return outbox.removeLast()
    }

    fun isEmpty() = inbox.isEmpty() && outbox.isEmpty()
}

fun main() {
    val q = QueueFromStacks()
    q.enqueue(1); q.enqueue(2); q.enqueue(3)
    println(q.dequeue())      // 1
    q.enqueue(4)
    println(q.dequeue())      // 2  (still in the outbox from the earlier pour)
    println(q.dequeue())      // 3
    println(q.dequeue())      // 4
    println(q.isEmpty())      // true
}

The reverse puzzle, a stack from queues, also works: after each push, rotate the queue so the new item comes to the front. It makes push cost O(n). Try it on paper; it is a good check of your understanding of FIFO.

9. Comparing the costs

Here is everything side by side. “Avg” for the array’s append means amortised: the occasional resize is spread over many appends.

The pattern to take away: a stack or queue gives you fewer operations on purpose. That restriction is a feature. When code uses a stack, the reader instantly knows the order is LIFO, and the structure guarantees nothing else can reach the middle.

10. Practice

Five exercises, from pointer wiring to stack tricks. Draw the picture on paper first, then write the code. The edge cases (empty, one item) are in the tests on purpose.

class Node(var value: Int, var next: Node? = null)

fun fromList(items: List<Int>): Node? {
    var head: Node? = null
    for (x in items.reversed()) head = Node(x, head)
    return head
}

fun toList(head: Node?): List<Int> {
    val out = ArrayList<Int>()
    var cur = head
    while (cur != null) { out.add(cur.value); cur = cur.next }
    return out
}

fun reverse(head: Node?): Node? {
    TODO("flip each next pointer; keep prev, cur and a saved next")
}

class Node(var value: Int, var next: Node? = null)

fun fromList(items: List<Int>): Node? {
    var head: Node? = null
    for (x in items.reversed()) head = Node(x, head)
    return head
}

fun toList(head: Node?): List<Int> {
    val out = ArrayList<Int>()
    var cur = head
    while (cur != null) { out.add(cur.value); cur = cur.next }
    return out
}

fun reverse(head: Node?): Node? {
    var prev: Node? = null
    var cur = head
    while (cur != null) {
        val next = cur.next
        cur.next = prev
        prev = cur
        cur = next
    }
    return prev
}

class Node(var value: Int, var next: Node? = null)

fun hasCycle(head: Node?): Boolean {
    TODO("slow moves 1, fast moves 2; do they ever meet?")
}

class Node(var value: Int, var next: Node? = null)

fun hasCycle(head: Node?): Boolean {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow!!.next
        fast = fast.next!!.next
        if (slow === fast) return true
    }
    return false
}

fun isBalanced(s: String): Boolean {
    TODO("push openers, match closers against the top")
}

fun isBalanced(s: String): Boolean {
    val pairs = mapOf(')' to '(', ']' to '[', '}' to '{')
    val stack = ArrayDeque<Char>()
    for (c in s) {
        if (c in pairs.values) stack.addLast(c)
        else if (c in pairs.keys) {
            if (stack.isEmpty() || stack.removeLast() != pairs[c]) return false
        }
    }
    return stack.isEmpty()
}

fun evalPostfix(tokens: List<String>): Int {
    TODO("push numbers; on an operator pop right, pop left, push the result")
}

fun evalPostfix(tokens: List<String>): Int {
    val stack = ArrayDeque<Int>()
    for (t in tokens) {
        when (t) {
            "+", "-", "*", "/" -> {
                val right = stack.removeLast()
                val left = stack.removeLast()
                stack.addLast(when (t) {
                    "+" -> left + right
                    "-" -> left - right
                    "*" -> left * right
                    else -> left / right
                })
            }
            else -> stack.addLast(t.toInt())
        }
    }
    return stack.removeLast()
}

class MyQueue {
    private val inbox = ArrayDeque<Int>()
    private val outbox = ArrayDeque<Int>()

    fun enqueue(x: Int) {
        TODO("push onto inbox")
    }

    private fun refill() {
        TODO("if outbox is empty, pour all of inbox into it")
    }

    fun dequeue(): Int? {
        TODO("refill, then pop from outbox")
    }

    fun peek(): Int? {
        TODO("refill, then look at the top of outbox")
    }

    fun isEmpty(): Boolean {
        TODO("both stacks empty")
    }
}

class MyQueue {
    private val inbox = ArrayDeque<Int>()
    private val outbox = ArrayDeque<Int>()

    fun enqueue(x: Int) {
        inbox.addLast(x)
    }

    private fun refill() {
        if (outbox.isEmpty()) {
            while (inbox.isNotEmpty()) outbox.addLast(inbox.removeLast())
        }
    }

    fun dequeue(): Int? {
        refill()
        return outbox.removeLastOrNull()
    }

    fun peek(): Int? {
        refill()
        return outbox.lastOrNull()
    }

    fun isEmpty(): Boolean = inbox.isEmpty() && outbox.isEmpty()
}

11. Takeaways

• A node holds a value and a pointer; a linked list is only as good as its pointer handling, so draw it first.
• Linked lists give O(1) insert and delete at a spot you hold, but O(n) access by position.
• Stacks are for undo, nesting, matching and call chains; queues are for fairness and nearest-first order.
• Use ArrayDeque for a stack, a queue or a deque, and never removeAt(0) on a list as a queue.
• Two pointers at different speeds solve middle and cycle problems in O(1) space.
• Next up: trees, heaps and tries, where each node has more than one next.