Koja je vremenska složenost dodavanja novog elementa na kraj jednostruke povezane liste?

Vremenska složenost dodavanja novog elementa na kraj jednostruko povezane liste zavisi od toga da li lista ima pokazivač na poslednji element (rep).

• Ako postoji pokazivač na rep, dodavanje se vrši u O(1), jer se može direktno pristupiti poslednjem elementu i dodati novi.
• Ako ne postoji pokazivač, potrebno je proći kroz celu listu od glave do kraja, što zahteva O(n) vremena, gde je n broj elemenata u listi.

Primer sa pokazivačem na rep:

class Node {
    var value: Int
    var next: Node?
    init(value: Int) {
        self.value = value
    }
}

class LinkedList {
    var head: Node?
    var tail: Node?

    func append(_ value: Int) {
        let newNode = Node(value: value)
        if let tailNode = tail {
            tailNode.next = newNode
        } else {
            head = newNode
        }
        tail = newNode
    }
}

Ovde, dodavanje se vrši u konstantnom vremenu O(1).