What is the complexity of inserting at the end of a list?

The complexity of inserting at the end of a linked list depends on whether a pointer to the last element (tail) is stored.

---

#1. If there is no tail

(only head - as in a simple singly linked list)

To add a new element at the end, you need to:

1. Start at head;
2. Walk through all nodes until you find the last one (next = None);
3. Add a new node and link it.

This requires walking through the entire list - Complexity: O(n).

---

#2. If tail is stored separately

(the list structure holds both pointers: head and tail)

Then:

1. A new node is created;
2. The current tail.next points to it;
3. tail is updated to the new node.

Everything is done in constant time - Complexity: O(1).

---

#3. For a doubly linked list

The same logic applies:

• without tail - O(n);
• with tail - O(1).

---

#Comparison with an array

---

Summary:

Insertion at the end of a linked list is: • O(1), if there is a tail pointer, • O(n), if you need to walk through the entire list to reach the end.