Introducing dslib: academic data structures library

hacker_compWhen I was studying Computer Science in an engineering institution in India 15 years earlier, there weren’t too many resources to check out. Lab computers were shared in tiny slots. They were tortoises compared to today’s regular smartphones. We accessed internet on a 64Kbps modem. Most of the academic subjects were studied by referring the text and a little bit of hands-on development. For many students, these didn’t reflect well on their careers.

Things have improved in India, but in many third-world and developing countries it’s still the same… or worse. So in my free time I wrote dslib, a library of data structures which grows on itself. The intent is to share a clearer picture of how data structures relate and work together. I believe it’s better than numerous examples of unrelated code for each data structure in textbooks.

Other than the most obvious cases like node deletion from trees, I have used iterative algorithms. The code is reasonably commented and adheres to the Linux kernel coding style as much as possible (I had to add some stuff like typedefs among few other deviations).

It’s still under development and there’s a lot more to be done. I am yet to make the first release. Patches, ideas and suggestions are welcome.

Overview

  1. A circular doubly linked list is at the heart of dslib
  2. A queue and stack written using 1
  3. A tree with regular methods
  4. An AVL tree with regular methods (lacks node deletion at the time of writing). Uses the stack from 2 for iterative insertion
  5. BFS and DFS of the tree and AVL tree (uses the stack and queue from 2)

dslib is GPLv3. Special thanks to my sister for spending her time on this.

Leave a Reply

Your email address will not be published. Required fields are marked *