Welche Prozesse treten auf, wenn ein neues Element zu einem Stapel hinzugefügt wird, der über eine verkettete Liste implementiert ist?

Beim Hinzufügen eines neuen Elements zum Stapel, der durch eine verkettete Liste implementiert ist, passiert Folgendes:

1. Es wird ein neuer Knoten (Listenelement) erstellt, der den hinzuzufügenden Wert enthält.
2. Der Zeiger des neuen Knotens wird auf das aktuelle obere Element des Stapels gesetzt (also auf den Kopf der verketteten Liste).
3. Der Kopf der verketteten Liste wird aktualisiert und zeigt nun auf den neuen Knoten — er wird zum neuen oberen Element des Stapels.

Auf diese Weise wird die Push-Operation in konstanter Zeit O(1) ausgeführt, da sie keine Listendurchlauf erfordert.

Beispiel 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
    }
}