[data-structures] Practical uses of different data structures

There's a lot of talk about data structures, but I can't find a simple list of data structures and their practical use out there. I'm trying to study for an interview and I think this would help me out, along with many others. I'm looking for something like this:

Data structure - Example/Used for

Hash table - fast data lookup ...then give an example

Array - ...

Binary tree - ...

If there is a resource like this somewhere, please let me know.

Thanks!

EDIT: I mean wikipedia is good and all, but on most of the pages they don't actually list practical uses. I'm looking for something more than that.

As per my understanding data structure is any data residing in memory of any electronic system that can be efficiently managed. Many times it is a game of memory or faster accessibility of data. In terms of memory again, there are tradeoffs done with the management of data based on cost to the company of that end product. Efficiently managed tells us how best the data can be accessed based on the primary requirement of the end product. This is a very high level explanation but data structures is a vast subjects. Most of the interviewers dive into data structures that they can afford to discuss in the interviews depending on the time they have, which are linked lists and related subjects.

Now, these data types can be divided into primitive, abstract, composite, based on the way they are logically constructed and accessed.

• primitive data structures are basic building blocks for all data structures, they have a continuous memory for them: boolean, char, int, float, double, string.
• composite data structures are data structures that are composed of more than one primitive data types.class, structure, union, array/record.
• abstract datatypes are composite datatypes that have way to access them efficiently which is called as an algorithm. Depending on the way the data is accessed data structures are divided into linear and non linear datatypes. Linked lists, stacks, queues, etc are linear data types. heaps, binary trees and hash tables etc are non linear data types.

I hope this helps you dive in.

The excellent book "Algorithm Design Manual" by Skienna contains a huge repository of Algorithms and Data structure.

For tons of problems, data structures and algorithm are described, compared, and discusses the practical usage. The author also provides references to implementations and the original research papers.

The book is great to have it on your desk if you search the best data structure for your problem to solve. It is also very helpful for interview preparation.

Another great resource is the NIST Dictionary of Data structures and algorithms.

Found the list in a similar question, previously on StackOverflow:

Hash Table - used for fast data lookup - symbol table for compilers, database indexing, caches,Unique data representation.

Trie - dictionary, such as one found on a mobile telephone for autocompletion and spell-checking.

Suffix tree - fast full text searches used in most word processors.

Stack - undo\redo operation in word processors, Expression evaluation and syntax parsing, many virtual machines like JVM are stack oriented.

Queues - Transport and operations research where various entities are stored and held to be processed later ie the queue performs the function of a buffer.

Priority queues - process scheduling in the kernel

Trees - Parsers, Filesystem

Radix tree - IP routing table

BSP tree - 3D computer graphics

Graphs - Connections/relations in social networking sites, Routing ,networks of communication, data organization etc.

Heap - Dynamic memory allocation in lisp

This is the answer originally posted by RV Pradeep

Some other, less useful links:

Applications are only listed for some data structures

Not application focused, by good summary and relevant

I am in the same boat as you do. I need to study for tech interviews, but memorizing a list is not really helpful. If you have 3-4 hours to spare, and want to do a deeper dive, I recommend checking out

mycodeschool
I’ve looked on Coursera and other resources such as blogs and textbooks, but I find them either not comprehensive enough or at the other end of the spectrum, too dense with prerequisite computer science terminologies.

The dude in the video have a bunch of lectures on data structures. Don’t mind the silly drawings, or the slight accent at all. You need to understand not just which data structure to select, but some other points to consider when people think about data structures:

• pros and cons of the common data structures
• why each data structure exist
• how it actually work in the memory
• specific questions/exercises and deciding which structure to use for maximum efficiency
• lucid Big 0 explanation

I also posted notes on github if you are interested.

Few more Practical Application of data structures

Red-Black Trees (Used when there is frequent Insertion/Deletion and few searches) - K-mean Clustering using red black tree, Databases, Simple-minded database, searching words inside dictionaries, searching on web

AVL Trees (More Search and less of Insertion/Deletion) - Data Analysis and Data Mining and the applications which involves more searches

Min Heap - Clustering Algorithms

Any ranking of various data structures will be at least partially tied to problem context. It would help to learn how to analyze time and space performance of algorithms. Typically, "big O notation" is used, e.g. binary search is in O(log n) time, which means that the time to search for an element is the log (in base 2, implicitly) of the number of elements. Intuitively, since every step discards half of the remaining data as irrelevant, doubling the number of elements will increases the time by 1 step. (Binary search scales rather well.) Space performance concerns how the amount of memory grows for larger data sets. Also, note that big-O notation ignores constant factors - for smaller data sets, an O(n^2) algorithm may still be faster than an O(n * log n) algorithm that has a higher constant factor. Complex algorithms often have more work to do on startup.

Besides time and space, other characteristics include whether a data structure is sorted (trees and skiplists are sorted, hash tables are not), persistence (binary trees can reuse pointers from older versions, while hash tables are modified in place), etc.

While you'll need to learn the behavior of several data structures to be able to compare them, one way to develop a sense for why they differ in performance is to closely study a few. I'd suggest comparing singly-linked lists, binary search trees, and skip lists, all of which are relatively simple, but have very different characteristics. Think about how much work it takes to find a value, add a new value, find all values in order, etc.

There are various texts on analyzing algorithms / data structure performance that people recommend, but what really made them make sense to me was learning OCaml. Dealing with complex data structures is ML's strong suit, and their behavior is much clearer when you can avoid pointers and memory management as in C. (Learning OCaml just to understand data structures is almost certainly the long way around, though. :) )