single vs double Linked list

Question

There is a table I found below

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.

Answer 1

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.