Linked List insertion running time confusion

Question

I've tried to confirm the running time for the insertion for Linked List and it seems like there are two different answers.

For inserting an element at the end of a Linked List, I would think that it would take O(n) since it has to traverse to the end of the list in order to access the tail. But some of the answers I've seen says O(1)? Are they assuming that all linked lists implementation of a pointer to the tail? If so, is that an acceptable assumption?

Second, some places also suggest that insertion an element in the middle of a linked list is O(1) which I'm confused about due to the same reasoning of traverse to the middle of the list to insert it.

Could someone please clarify? Thanks.

Answer 1

Inserting to a linked list is O(1) if you have a pointer to the node where you want to insert the item. Finding this node may be O(n) depending on what you want to do.

If you keep a pointer to the list's tail then you don't need to look for it and then insertion is O(1).

And no, not all linked list implementations have a pointer to the end of the list.

Example

Suppose you have an empty list to which you add a single node, x. Then you add n nodes to the list before and after x. You can still insert a single node after x by simply updating its next pointer (and the new node's), regardless of how many nodes are were the list.

Answer 2

Modifications to linked list involve two operations:

1. locating the node to append the new node to
2. actually appending the node, by changing the node pointers

In Linked List, the second operation is an O(1) operation, so it is a matter of the cost of first operations.

When appending to the last node, naive implementations of linked list would result in O(n) iteration time. However, good linked list libraries would account for the most common uses, and special case accessing the last node. This optimization would result into O(1) retrieval of the last element, resulting in overall O(1) insertion time to end.

As for the middle, your analysis is correct in that locating the node would also take O(n). However, some libraries expose a method that would take a pointer to where the new node should be inserted rather than the index (e.g. C++ list). This eliminates the linear cost, resulting in over all O(1).

While insertion to the middle is usually thought of as O(n) operation, it can be optimized to O(1) in some cases. This is the opposite of array list, where the insertion operation itself (the second operation) is O(n), as all the elements in higher locations need to be relocated. This operation cannot be optimized.

For insertation A naive implementation of a linked list would result in O(n) insertion time. However, good linked list library writers would optimize for the common cases, so they would keep a reference to the last elements (or have a circular linked list implementation), resulting in a O(1) insertion time.

As for insertion to the middle. Some libraries like that of C++, has a suggested location for insertion. They would take a pointer to the list node, where the new one is be appended to. Such insertions would cost O(1). I don't think you can achieve O(1) by index number.

This is apposed to an array list, where insertion to the middle forces reordering of all the elements higher than it, so it has to be an O(n) operation.