Why is inserting in the middle of a linked list O(1)

big olinked list

According to the Wikipedia article on linked lists, inserting in the middle of a linked list is considered O(1). I would think it would be O(n). Wouldn't you need to locate the node which could be near the end of the list?

Does this analysis not account for the finding of the node operation (though it is required) and just the insertion itself?

EDIT:

Linked lists have several advantages over arrays. Insertion of an element at a specific point of a list is a constant-time operation, whereas insertion in an array may require moving half of the elements, or more.

The above statement is a little misleading to me. Correct me if I'm wrong, but I think the conclusion should be:

Arrays:

Finding the point of insertion/deletion O(1)
Performing the insertion/deletion O(n)

Linked Lists:

Finding the point of insertion/deletion O(n)
Performing the insertion/deletion O(1)

I think the only time you wouldn't have to find the position is if you kept some sort of pointer to it (as with the head and the tail in some cases). So we can't flatly say that linked lists always beat arrays for insert/delete options.

Best Answer

You are correct, the article considers "Indexing" as a separate operation. So insertion is itself O(1), but getting to that middle node is O(n).

Related Solutions

Linked List insertion running time confusion

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.

Java – How to detect a loop in a linked list

You can make use of Floyd's cycle-finding algorithm, also known as tortoise and hare algorithm.

The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes.

If the linked list has a loop they will definitely meet.
Else either of the two references(or their next) will become null.

Java function implementing the algorithm:

boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list

    while(true) {

        slow = slow.next;          // 1 hop

        if(fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false;          // next node null => no loop

        if(slow == null || fast == null) // if either hits null..no loop
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop
            return true;
    }
}

Related Topic