Jakie procesy zachodzą, gdy do stosu zaimplementowanego za pomocą listy powiązanej dodawany jest nowy element?

Podczas dodawania nowego elementu do stosu, zaimplementowanego za pomocą listy powiązanej, dzieje się następująco:

1. Tworzony jest nowy węzeł (element listy), który zawiera wartość do dodania.
2. Wskaźnik nowego węzła jest ustawiany na obecny górny element stosu (czyli na głowę listy powiązanej).
3. Głowa listy powiązanej jest aktualizowana i teraz wskazuje na nowy węzeł — staje się nowym górnym elementem stosu.

W ten sposób operacja push jest wykonywana w czasie stałym O(1), ponieważ nie wymaga przechodzenia przez listę.

Przykład w 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
    }
}