Data Structures

[Jeremy Kubica]

Following the theme of my book promotion for Data Structures the Fun Way, I'm interested to hear: What data structures everyone here finds themselves consistently turning to? Or what uses of data structures came as a surprise?

I have long had an interest in spatial data structures like kd-trees, ball trees, and metric trees. These end up being my go-to structures for a lot of spatial problems. But I also find that hashtables come up surprisingly often in a lot of problems.

[ludoviko azuaje]

Dear  Jeremy Kubica,


I am starting to work with geo data and geo analysis and came across k-nearest neighbor algorithm, I am pretty sure your book will prove useful, I have already bought it, it is already fully available.


Can you explain what inspired you to write on data structures -the fun way- ?


How did you choose the structures given the broad choice ?


Thanks.

[Campbell Ritchie]

What about stacks? I know the Collections Framework thinks a stack is simply a Queue running backwards, but I think it is a distinct structure in its own right. I also see stacks and queues in real life, including how I pack the shelves when helping at Food Bank.

[Jeremy Kubica]

ludoviko azuaje wrote:Can you explain what inspired you to write on data structures -the fun way- ?


How did you choose the structures given the broad choice ?

Data Structures the Fun Way actually started as a slightly different project. I was initially working on a book that expanded the non-fiction parts of one of my earlier books, The CS Detective (which I did a book promotion for years ago). I wrote a few of the data structures chapters early on and kept returning to the theme of the importance of data organization for efficient programs.  This made sense given my background. I spent a large part of my graduate studies looking at how we could improve complex spatial searches using data structures, and, since then, it is something I've seen in practice time and again. I quickly realized that I wanted to write a fun introduction to those concepts.

As for choosing the data structures, the goal was to cover specific computational concepts from how data is stored in memory to pruning in tree-based algorithms to the use of mathematical hash functions. The final selection was a combination of covering the core data structures that pop up everywhere (binary search trees, stacks, queues, etc.) and covering some less well known data structures that illustrated specific concepts from computational thinking. For example I included Bloom Filters because they demonstrate how a data structure can save space by giving approximate answers and I included skiplists because they are a great example of the power of randomization.

[Jeremy Kubica]

Campbell Ritchie wrote:What about stacks? I know the Collections Framework thinks a stack is simply a Queue running backwards, but I think it is a distinct structure in its own right. I also see stacks and queues in real life, including how I pack the shelves when helping at Food Bank.

Stacks are definitely important and are distinct from queues. Stacks pop up everywhere in both programs and real life. My favorite geeky (real-world?) reference is the "Conversation Stack", which is when someone tries to unwind a conversation by going back through topics. I had multiple conversations where someone says "How did we get on this topic, let me go through the conversation stack."

[Campbell Ritchie]

Jeremy Kubica wrote:. . . "How did we get on this topic . . .

Isn't that a question as difficult to answer as, “How long is a piece of string?”