DEV Community

Discussion on: Looking At Linked Lists

dystroy profile image
Denys Séguret

There are three things to know regarding linked list based structures (including double linked lists and more complex structures):

  • they're very rarely the most efficient structure, even if their theoretical big O cost is pretty. They consume a lot of memory and this memory is fragmented.

  • they almost always imply tricky corner cases which means a big test list and some unexpected bugs after months or years of production (true story, and that was billions of computations during 15 years until a case that I finally understood)

  • sometimes they're useful... probably not for your problem, and you should have checked you didn't in fact need a ring buffer or a vector, but yes there are still some use cases...