How to determine 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 (tail).

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

Example in Python with a tail pointer:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

Here, the append method operates in constant time O(1).