Though, weirdly, the author lists the deletion BigO as O(n). I would have thought maybe they meant traversing to the item to be deleted, but that would imply in

Though, weirdly, the author lists the deletion BigO as O(n). I would have thought maybe they meant traversing to the item to be deleted, but that would imply insertion is also O(n), since you'd have to traverse to the point of insert. Unless they are treating deletion as deleting from an arbitrary location, and insertion only at the head. Very strange. But, yes; while real life performance characteristics vary (cache locality can lead to surprising wins for arrays even on insertions/deletions), at least theoretically, there are use cases where a LinkedList will win out. EDIT: Huh. They also list the insertion and deletion cost of a hash table as being O(n). That...is not right. I mean, they call out "in the case of a perfect hash function it would be 1", but treating the literal worst case as the actual runtime is like saying quicksort runs in O(n^2) (which the author does not do).