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.

Answer 3

Per the Java LinkedList source code, Java achieves the O(1) for LinkedList tail operations by giving the header Entry a link to the tail element via header.previous. So if you want the last element, the class can always return header.previous, allowing for constant time.

I assume that a lot of other languages use the same basic strategy.

Answer 4

Obviously you've probably looked at the wikipedia entry http://en.wikipedia.org/wiki/Linked%5Flist. I see the table where they are specifying that both inserting/deleting from the end and in the middle of the list have O(1) performance but fail to elaborate on how they determined that.

There's some interesting answers to a similar question here on stackoverflow at http://stackoverflow.com/questions/840648/why-is-inserting-in-the-middle-of-a-linked-list-o1. The original poster of that question editted his post and made a point that he believes when it's said that insertion/deletion is O(1) they're talking about the actual insert operation and not the finding of where to insert at. That makes sense but I haven't seen that formally stated in any of the articles I've found at this point.

Answer 5

If you don't mutate the nodes of your (simply) linked list, you need O(n) time to insert at an arbitrary position in the list (because you need to copy all the nodes from the beginning of the list to the position of the new element. It is O(1) for a mutable list if you already have a pointer to the node where you want to insert an item, and O(n) if you have to search for it. In both cases, you need only O(1) time to insert an element at the beginning of the list. If you often need to insert an element in the middle of the list (O(n) case), you should use another data structure.

Answer 6

I think one reason of your confusion is the fact that you are thinking as if there is a an ideal/canonical linked list, which either has or does not have certain head/tail pointers. The reality is that any linear (i.e. no branching) data structure that accesses elements by going through pointers from previous elements is basically a linked list. Whether you keep pointers to the first, last, k-th etc. elements is entirely up to you. So, if you need a list where you frequently need to insert/delete elements at the 10th position, you can simply implement one that has an extra pointer to the 9th element and do that in O(1) time.

Another thing is that when iterating over the elements of a linked-list, you can insert a new element right after the current element (and just before it if is a double linked list) in O(1), because you already have a pointer to that.

Answer 7

As @Kaleb Brasee points out, inserting at the tail in Java is O(1) because Java uses a doubly-linked list as its LinkedList implementation. I think this is a fairly common choice for a lot of SDK implementations. For instance, the STL list implementation is doubly-linked (source).