Kāda ir laika sarežģītība, pievienojot jaunu elementu vienkāršā saistītā saraksta beigās?

Jauna elementa pievienošanas laika sarežģītība vienkāršā saistītā sarakstā ir atkarīga no tā, vai sarakstā ir norādītājs uz pēdējo elementu (asti).

• Ja ir norādītājs uz asti, pievienošana notiek O(1) laikā, jo var tieši piekļūt pēdējam elementam un pievienot jaunu.
• Ja norādītājs nav, ir jāiziet cauri visam sarakstam no galvas līdz beigām, kas aizņem O(n) laika, kur n ir elementu skaits sarakstā.

Piemērs ar norādītāju uz asti:

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

Šeit pievienošana notiek konstanta laikā — O(1).