What is the time complexity of adding a new element to the end of a singly linked list?

The time complexity of adding a new element to the end of a singly linked list depends on whether the list has a pointer to the last element (tail).

• If there is a tail pointer, then the addition occurs in O(1) time, as you can directly access the last element and add the new one.
• If there is no pointer, then you need to traverse the entire list from the head to the end, which takes O(n) time, where n is the number of elements in the list.

Example with a tail pointer:

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

Here, the addition occurs in constant time O(1).