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

The time complexity of adding an element to the end of a linked list depends on whether the list has a pointer to the last element.

• If there is a pointer to the tail, then the addition occurs in O(1) time, as you can immediately add a new element after the tail.
• If there is no pointer to the tail, then you need to traverse the entire list to find the last element, and the complexity will be O(n), where n is the number of elements in the list.

Example with a tail pointer:

class LinkedList {
    Node head;
    Node tail;

    void addLast(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }
}