Millised protsessid toimuvad, kui seotud nimekirja kaudu rakendatud virna juurde lisatakse uus element?

Kui lisate uue elemendi virna, mis on rakendatud seotud nimekirja abil, toimub järgmine:

1. Loome uue sõlme (nimekirja elemendi), kuhu salvestatakse lisatav väärtus.
2. Uue sõlme näitaja määratakse praegusele virna ülaelemendile (st seotud nimekirja päisele).
3. Seotud nimekirja päis uuendatakse ja nüüd näitab see uuele sõlmele — see muutub uueks virna ülaelemendiks.

Seega, push operatsioon toimub konstantsel ajal O(1), kuna see ei nõua nimekirja läbimist.

Kotlin näide:

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