Time complexity of Single Link List Insertion and deletion

c++, data-structures, linked-list

Solution

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.

Problem

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) ?

Original source