CODEWITHSUNDEEP
time-complexitysingly-linked-list
SilentDev
SilentDev

Reputation: 22747

How is insertion for a Singly Linked List and Doubly Linked List constant time?

Thinking about it, I thought the time complexity for insertion and search for any data structure should be the same, because to insert, you first have to search for the location you want to insert, and then you have to insert.

According to here: http://bigocheatsheet.com/, for a linked list, search is linear time but insertion is constant time. I understand how searching is linear (start from the front, then keep going through the nodes on the linked list one after another until you find what you are searching for), but how is insertion constant time?

Suppose I have this linked list:

1 -> 5 -> 8 -> 10 -> 8

and I want to insert the number 2 after the number 8, then would I have to first search for the number 8 (search is linear time), and then take an extra 2 steps to insert it (so, insertion is still linear time?)?

#insert y after x in python 
def insert_after(x, y):
    search_for(y)
    y.next = x.next
    x.next = y

Edit: Even for a doubly linked list, shouldn't it still have to search for the node first (which is linear time), and then insert?

Upvotes: 4

Views: 1584

Answers (2)

displayName
displayName

Reputation: 14379

Time to insert = Time to set three pointers = O(3) = constant time.

Time to insert the data is not the same as time to insert the data at a particular location. The time asked is the time to insert the data only.

Upvotes: 1

Dair
Dair

Reputation: 16240

So if you already have a reference to the node you are trying to insert then it is O(1). Otherwise, it is search_time + O(1). It is a bit misleading but on wikipedia there is a chart explains it a bit better: enter image description here

Contrast this to a dynamic array, which, if you want to insert at the beginning is: Θ(n).

Just for emphasis: The website you reference is referring to the actual act of inserting given we already know where we want to insert.

Upvotes: 5

Related Questions