Hogyan lehet egy verem adatstruktúrát felépíteni egy láncolt listával?

A verem egy összekapcsolt lista alapjaira építhető, ahol minden elem (csomópont) tartalmaz adatokat és hivatkozást a következő elemre. A verem felső eleme a lista fejét jelenti. Fő műveletek:

• push — új csomópont hozzáadása a lista elejéhez;
• pop — a lista elejéről eltávolítja a csomópontot és visszaadja az értékét;
• peek — megtekinti a fej értékét anélkül, hogy eltávolítaná.

Kotlin példában:

class Node<T>(val data: T, var next: Node<T>? = null)

class Stack<T> {
    private var head: Node<T>? = null

    fun push(value: T) {
        val newNode = Node(value, head)
        head = newNode
    }

    fun pop(): T? {
        val value = head?.data
        head = head?.next
        return value
    }

    fun peek(): T? = head?.data

    fun isEmpty() = head == null
}

Ez a megközelítés O(1) időben biztosítja a verem műveleteit és dinamikus bővítést tesz lehetővé anélkül, hogy nagy tömböt kellene lefoglalni.