tags:

views:

65

answers:

2
Q: 

Why the time complexity in dll is faster than deletion of a node in sll?

Why the time complexity in doubly linked list which is O(1) is faster than deletion of a node in singly linked list which is O(n)?

+1  A: 

It has to do with the complexity of fixing up the next pointer in the node previous to the one you're deleting.

jeffamaphone  2009-12-13 06:53:51
+1  A: 

Because you can't look backwards...

Paul  2009-12-15 03:15:29

related questions

How much to log within an application??? How much is too much...
Is list::size() really O(n)?
multiset, map and hash map complexity
C++ STL: Container Recreation or Reuse after clearing?
How do I find the running time given algorithm speed and computer speed?
Dealing with complexity
Recursion and Big O
Efficient traversal of a changelist
Constant Amortized Time
In-memory LINQ performance
which tools are helpful in determining the cyclomatic complexity of a given C source code
Hashtable in C++?
What is Big O notation? Do you use it?
Tool for calculating cyclomatic complexity
What is the time complexity of indexing, inserting and removing from common data structures?
Did you apply computational complexity theory in real life?
What's "P=NP?", and why is it such a famous question?
How do you prevent over complicated solutions or designs?
Prim's Algorithm, Priority First Search and Minimum Spanning Trees (MST)
What level of complexity requires a framework?
Where can I find the time and space complexity of the built-in sequence types in Python
Complexity of Regex substitution
What tools do you use for static code analysis?
What's your/a good limit for cyclomatic complexity?
Big O, how do you calculate/approximate it?