Suggest an editImprove this articleRefine the answer for “What is the complexity of inserting at the end of a list?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)The complexity of **inserting at the end of a linked list** depends on whether a pointer to the last element (**`tail`**) is stored. **Key point:** insertion at the end takes O(1) if a `tail` pointer exists, and O(n) if you need to walk through the entire list to reach the end.Shown above the full answer for quick recall.Answer (EN)ImageThe 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** | Structure | Insertion at the end | |---|---| | Array (dynamic) | amortized **O(1)**, but sometimes **O(n)** on resizing | | Linked list with `tail` | **O(1)** | | Linked list without `tail` | **O(n)** | --- **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.For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.