Какви процеси се случват, когато към стек, реализиран чрез свързан списък, се добавя нов елемент?

Когато добавяте нов елемент към стек, реализиран чрез свързан списък, се случва следното:

1. Създава се нов възел (елемент на списъка), който съдържа стойността, която трябва да бъде добавена.
2. Посочващият указател на новия възел се задава на текущия горен елемент на стека (т.е. на главата на свързания списък).
3. Главата на свързания списък се актуализира и сега сочи към новия възел — той става новият горен елемент на стека.

По този начин операцията push се изпълнява за константно време O(1), тъй като не изисква обхождане на списъка.

Пример на 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
    }
}