Time complexity of Single Link List Insertion and deletion

Question

I am a bit confused about time complexity of Linked Lists. In this article here it states that insertion and deletion in a linked list is O(1). I wanted to know how this is possible ? Is it assumed that the forward and next pointers are known ? Wouldn't that be Double Linked List then ? I would appreciate it if someone could clarify this . And how the time complexity of insertion/deletion of single linked list is O(1) ?

Answer 1

Is it assumed that the forward and next pointers are known ?

In singly linked lists, for both insertion and deletion, you need a pointer to the element before the insertion/deletion point. Then everything works out.

For example:

# insert y after x in O(1)
def insert_after(x, y): 
    y.next = x.next
    x.next = y

# delete the element after x in O(1)
def delete_after(x):
    x.next = x.next.next

For many applications it is easily possible to carry the predecessor of the item you are currently looking at through your algorithm, to allow for dynamic insertion and deletion in constant time. And of course you can always insert and delete at the front of the list in O(1), which allows for a stack-like (LIFO) usage pattern.

Deleting an item when you just know the pointer to the item is generally not possible in O(1). EDIT: As codebeard demonstrates, we can insert and delete by just knowing a pointer to the insertion/deletion point. It involves copying the data from the successor, thus avoiding fixing up the next pointer of the predecessor.

Answer 2

Yes, it's assuming that you already know the place at which you want to insert the data.

Suppose you have some item p in the list, and you want to insert a new element new after p in the list:

new->next = p->next;
p->next = new;

Alternatively, suppose you want to insert new before p. This can still be done in O(1) time:

if (p == head) {
    new->next = head;
    head = new;
} else {
    tmp = p->data;
    p->data = new->data;
    new->data = tmp;
    new->next = p->next;
    p->next = new;
}

As for deleting items in a conventional singly linked list, it's not strictly O(1)!

It is O(1) for deleting any element except the last element. If you are trying to delete the last element in a singly linked list, you need to know the element before it (which requires O(N) time assuming you didn't know it before).

To delete the item p:

free_if_necessary(p->data);
if (p->next) {
    /* O(1) */
    nextnext = p->next->next;
    nextdata = p->next->data;
    destroy_if_necessary(p->next);
    p->data = nextdata;
    p->next = nextnext;
} else if (p == head) {
    destroy_if_necessary(p);
    head = NULL;
} else {
    /* O(n) */
    prev = find_prev(head, p);
    destroy_if_necessary(p);
    prev->next = NULL;
}