CODEWITHSUNDEEP
linked-listbig-o
Math4Life
Math4Life

Reputation: 125

single vs double Linked list

There is a table I found below enter image description here

My question is whether or not it is true that a single and double linked list have the same operation run times like the table seems to show. I would think in the deletion case for example, a double linked list would be better since we have access to previous. So is the table wrong on that being O(n) for singly linked lists?

If they are all the same, does this similarity hold for a circular one as well?

Thanks.

Upvotes: 0

Views: 1241

Answers (1)

kenshinji
kenshinji

Reputation: 2091

Here is my answer to your question:

  1. No matter whether the double linked list enable you have access to previous or not, it doesn't affect the time complexity we calculate in terms of Big O notation, I think it does give you some convenience though.
  2. Yes, they are all the same, and the similarity holds for a circular one as well.

Upvotes: 1

Related Questions