A graphical toolkit system that stored all the styles applied to components as a linked-list, but each element included a pointer to the the head of the linked list and everytime a new component was instantiated it was added to the head of the linked list. Which meant that creating a new graphical element went from O(1) to O(N) and caused significant slow down (i.e seconds of time).
A well known open-source xml parsing library which stored the attributes of an xml element in a linked-list, as part of it's xml validation it had to ensure attribute uniqueness and do that it had to iterate through every attribute. This means that to insert N attributes would take O(N^2) - again enough to cause a significant performance degradation.
Iteration through hashtables.