Practical uses of different data structures

Question

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

[data-structures] Practical uses of different data structures

Examples related to data-structures