Quali processi avvengono quando un nuovo elemento viene aggiunto a uno stack implementato tramite una lista collegata?

Quando si aggiunge un nuovo elemento allo stack, implementato tramite una lista collegata, accade quanto segue:

1. Viene creato un nuovo nodo (elemento della lista), che contiene il valore da aggiungere.
2. Il puntatore del nuovo nodo viene impostato sull'elemento superiore corrente dello stack (cioè sulla testa della lista collegata).
3. La testa della lista collegata viene aggiornata e ora punta al nuovo nodo — che diventa il nuovo elemento superiore dello stack.

In questo modo, l'operazione push viene eseguita in tempo costante O(1), poiché non richiede di attraversare la lista.

Esempio in Kotlin:

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

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

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

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