Come si può costruire una struttura dati stack usando una lista collegata?

Lo stack può essere implementato utilizzando una lista collegata, in cui ogni elemento (nodo) contiene i dati e un riferimento al nodo successivo. L'elemento superiore dello stack è la testa della lista. Operazioni principali:

• push — aggiungere un nuovo nodo all'inizio della lista;
• pop — rimuovere il nodo dall'inizio della lista e restituirne il valore;
• peek — visualizzare il valore della testa senza rimuoverlo.

Esempio in Kotlin:

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
}

Questo approccio garantisce operazioni di pila in O(1) e un'espansione dinamica senza la necessità di allocare un grande array.