List of fundamental data structures - what am I missing?

Question

I've been studying my fundamental data structures a bunch recently, trying to make sure I've got them down cold.

By "fundamental", I mean the real basic ones. Fancy ones like Red-Black Trees and Bloom Filters are clearly worth knowing, but they're usually either enhancements of fundamental ones (Red-Black Trees are binary search trees with special properties to keep them balanced) or they're only useful in very specific situations (Bloom Filters).

So far, I'm "fluent" in the following data structures:

• Arrays
• Linked Lists
• Stacks/Queues
• Binary Search Trees
• Heaps/Priority Queues
• Hash Tables

However, I feel like I'm missing something. Are there any fundamental ones that I'm forgetting about?

EDIT: Added these after posting the question

• Strings (suggested by catchmeifyoutry)
• Sets (suggested by Peter)
• Graphs (suggested by Nick D and aJ)
• B-Trees (Suggested by tloach)
  • I'm a little on-the-fence about whether these are too fancy or not, but I think they're different enough from the fundamental structures (and important enough) to be worth studying as fundamental.

Answer 1

Sets

As a principle I never say try [anySearhEngine] on it, but you can checkout this list : http://en.wikipedia.org/wiki/List%5Fof%5Fdata%5Fstructures

Answer 2

You've forgot the basic ones: struct, object and enums.

Answer 3

B-Trees and other multi-trees

Answer 4

I would add maps unless you want to consider that to be under sets.

Answer 5

Matrices since they serve as basis for modelling problems such as:

• Graphs
• Affine transformations
• Solving linear systems
• Markov chains
• etc

Answer 6

Also the Graph data structure is fundamental.

Answer 7

For help, read the Java Collections documentation. They break things down into an abstract tier (Set, List and Map) and an implementation tier (ArraySet, HashSet, ArrayList, LinkedList, TreeMap, HashMap).

For help, read the Python Collections documentation. They break things down into abstract base classes like Set, Sequence and Map which are built up from mixin features of a collection.

Answer 8

Matrices

Graphs

Answer 9

strings, although they may be implemented as arrays under the hood (as are several other data structures).

Any program that interacts with the user will use strings. It's important to know how to manipulate strings.

Answer 10

some may be considered less fundamental than others:

• mathematical vectors/matricies
• graphs, adjacency lists/matricies
• tries prefix/suffix trees
• spatial indexing - quad trees/ kd-trees r-trees
• streams/ sequences null terminated strings / big ints

Answer 11

Quadtrees, as the most simple kind of spatial index.

Answer 12

Bit array is not fundamental but it is very handy and it can represented efficiently using integers (and bitwise operators)

Answer 13

You might consider union/find datastructures. They are fundamental to some graph algorithms.

Answer 14

Associative Array is the generic way of saying Dictionaries, Maps, etc. You can find this in almost every framework.

http://en.wikipedia.org/wiki/Associative_array

Answer 15

Tuples.

Also, if I could nominate one not-basic data structure, it would be the persistent bit-partitioned prefix Hash Tries from Clojure. In general, I believe persistence to be a very important and often overlooked property of any data structure.

Answer 16

Cons cell. With that you can build several other data structures (lists, trees, etc.)

http://en.wikipedia.org/wiki/Cons

Answer 17

i think your question is unclear, because you're mixing implementation and purpose ...

the following types describe implementation:

• linked list
• double linked list
• skip list
• array
• dynamic array
• hash table
• (binary) tree
• "managed" (binary) trees (heaps, leveled trees etc., i.e. trees where insertion and deletion is not done directly but through a procedure that guarantees certain constraints for the tree)
• graph (although very fancy)

the following describe purpose:

• stack (means FILO & can be implemented by a linked list, but also with an array or vector)
• queue (means FIFO & can be implemented by a double linked list, or maybe in other sensible ways)
• dequeue (...)
• priority queue (means "Highest/Lowest Key First Out" this is an abstract concept, that can be implemented in many different ways)
• map/associative array/dictionary (means you map keys to values. often requires an extra function to convert keys into valid keys for the underlying hash table or tree)
• set (means, it's a collection, that is iterable and can tell, whether a value is an element of the set or not. every value, that is an element of the set must apear exactly once during iteration. a set may be mutable, or not (may allow to add or remove elements). routines for intersection, union, difference may be provided (e.g. as methods in OOP). when it comes to implementation, there's a number of possibilities)

well, there'd be one last thing I consider very much worth mentioning: algebraic data types ... depending on the language, they either exist natively, or you have to emulate them ... haXe and C# (as far as I've heard) would be two imperative languages offering them by simply allowing parameters for enums ... they can be used to implement lists, trees and many other nice things ... for example, they are perfect to represent ASTs and a lot of other complex structures ...

greetz

back2dos

Answer 18

A "function object", "function pointer", or "closure" can't be implemented in certain restrictive languages that have arrays, linked lists, etc. But perhaps they are closer to data types rather than data structures.

The "rope" implementation (as implemented in the "cord" library) is my favorite implementation of the "string" abstract data structure, but perhaps it's not really "fundamental".