O'Reilly logo
  • Kashyap Joshi thinks this is interesting:

So how should we classify clear? The method itself contains two constant time operations, so it sure looks like it’s constant time. But when you invoke it, you make the garbage collector do work that’s proportional to the number of elements. So maybe we should consider it linear!

This is an example of what is sometimes called a performance bug: a program that is correct in the sense that it does the right thing, but it doesn’t belong to the order of growth we expected. In languages like Java that do a lot of work, like garbage collection, behind the scenes, this kind of bug can be har...


Cover of Think Data Structures


setting first node=null in a linked list causes GC to travel through list and find candidate for garbage collection