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.

Probably anything beyond arrays and linked lists could be classified as fancy :P — jakeboxer, Dec 07 '09 at 16:25
'fancyness' is almost certainly an analogue scale rather than a binary choice, if it can even be well defined. — jk., Dec 07 '09 at 16:32

score 10 · Accepted Answer · answered Dec 07 '09 at 16:16

10

Sets

As a principle I never say try [anySearhEngine] on it, but you can checkout this list : http://en.wikipedia.org/wiki/List_of_data_structures

answered Dec 07 '09 at 16:16

Peter

47,963
46
132
181

1

A Set is more a modelling construct than a fundamental data structure. – Hassan Syed Dec 07 '09 at 16:20
4

IMHO it is a very fundamental data structure – Peter Dec 07 '09 at 16:21
Oh wow. I did search for stuff like this (both on Wikipedia and Google), but somehow I didn't bump into this list. Thanks so much. – jakeboxer Dec 07 '09 at 16:22
A set it totally a fundamental data structure. It's not a list because elements cannot be repeated. It's not a mapping, it's only the keys of a mapping. It's very fundamental. – S.Lott Dec 07 '09 at 16:23
A set defines what it contains. I think as these definitions can be quite complex and because depend on arbitrary functions to define them, they should be considered too high level to be considered a fundamental data structure. – Hassan Syed Dec 07 '09 at 16:25
They do have implementations in lot of languages however – Peter Dec 07 '09 at 16:27
Yes, but data structures should be syntactic-sugar agnostic. – Hassan Syed Dec 07 '09 at 16:30
1

It is a mathematical concept, as syntactic agnostic as they come – Peter Dec 07 '09 at 16:34
often implemented as an iterface over a tree or hash table, but then you can argue that almost any structure is just some abstraction over arrays – jk. Dec 07 '09 at 16:35
@Vainstah : btw even boolean algebra is dependend on it, a set might very well be one of the most fundamental data structures around – Peter Dec 07 '09 at 16:40
2

I think a set is a datastructure in much the same way as queues and stacks are. They're sort of "non-terminal" data structures. They can be represented in many different ways, but they should all provide a consistent interface. – Jason Baker Dec 07 '09 at 16:42

score 10 · Answer 2 · answered Dec 07 '09 at 16:19

10

Also the Graph data structure is fundamental.

answered Dec 07 '09 at 16:19

Nick Dandoulakis

42,588
16
104
136

Graphs are a mondelling construct and a data structure. +1 – Hassan Syed Dec 07 '09 at 16:22
Awesome. I've been studying various graph algorithms, but I should refresh on the data structure itself. – jakeboxer Dec 07 '09 at 16:24

score 6 · Answer 3 · edited Mar 10 '19 at 13:53

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 ...

I understand what you're saying, but they are still distinct data structures; you can be well-versed in linked lists, arrays, and other ways to implement stacks without understanding stacks themselves, and you can be well-versed in stacks without understanding their implementations. I'm attempting to list the fundamental data structures, whether they're implementations or interfaces. — jakeboxer, Dec 07 '09 at 18:47

score 4 · Answer 4 · answered Dec 07 '09 at 16:16

4

B-Trees and other multi-trees

answered Dec 07 '09 at 16:16

tloach

8,009
1
33
44

B-Trees are covered, are you implying fancy ones ? – Hassan Syed Dec 07 '09 at 16:18
Vainstah: B-Trees are different from Binary Search Trees. Good call tloach, it's been awhile since I've refreshed myself on those. – jakeboxer Dec 07 '09 at 16:19
In that case they should be fancy according to his definition. – Hassan Syed Dec 07 '09 at 16:21
1

I think "fancy" and "fundamental" is a false dichtomy; B-Trees are both, since they are an absolutely essential component of pretty much any large database. – Michael Borgwardt Dec 07 '09 at 16:26
Also, they're interesting as an example for how a data structure can be optimized for performance under specific hardware constraints. – Michael Borgwardt Dec 07 '09 at 16:32

score 4 · Answer 5 · answered Dec 07 '09 at 16:22

4

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.

answered Dec 07 '09 at 16:22

catchmeifyoutry

7,179
1
29
26

Variadic data types, lots of implementation cruft to be considered a fundamental data type.... but +1 as they are too important to ignore. – Hassan Syed Dec 07 '09 at 16:27
Fair enough. I'm a little on-the-fence about whether strings deserve separate consideration from arrays, but it can't hurt, especially since they're so important. – jakeboxer Dec 07 '09 at 16:31

score 2 · Answer 6 · answered Dec 07 '09 at 16:21

2

Matrices

Graphs

answered Dec 07 '09 at 16:21

aJ.

34,624
22
86
128

score 2 · Answer 7 · answered Dec 07 '09 at 16:29

2

Quadtrees, as the most simple kind of spatial index.

answered Dec 07 '09 at 16:29

Michael Borgwardt

342,105
78
482
720

interesting and complex, but imo as it applies closely to 2-d space it is fundamental. – Hassan Syed Dec 07 '09 at 16:33
might I also suggest R-trees or QR-trees? they're an interesting extension of quadtrees. http://en.wikipedia.org/wiki/R-tree – rmeador Dec 07 '09 at 16:41
ok, to clarify, the R-tree is more like an extension of a B-tree, and the QR-tree is a fusion of a quadtree and an R-tree – rmeador Dec 07 '09 at 16:42
Those are very specific to GIS. – wheaties Dec 07 '09 at 16:58
1

Not at all specific to GIS, useful anywhere you have 2-d data – jk. Dec 08 '09 at 16:37

score 2 · Answer 8 · answered Dec 07 '09 at 17:25

2

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

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

answered Dec 07 '09 at 17:25

Mark Bolusmjak

23,606
10
74
129

jk. · Answer 9 · 2009-12-07T16:51:28.993

1

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

edited Dec 07 '09 at 16:51

answered Dec 07 '09 at 16:26

jk.

13,817
5
37
50

score 1 · Answer 10 · answered Dec 07 '09 at 16:35

1

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

answered Dec 07 '09 at 16:35

dfa

114,442
31
189
228

+1 use them everyday- very easy and fast! – Dec 07 '09 at 17:17

score 1 · Answer 11 · answered Dec 07 '09 at 16:42

1

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

answered Dec 07 '09 at 16:42

Matt Dotson

5,887
1
23
23

score 1 · Answer 12 · edited Jun 20 '20 at 09:12

1

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.

edited Jun 20 '20 at 09:12

Community

1
1

answered Dec 07 '09 at 16:42

Jörg W Mittag

363,080
75
446
653

score 0 · Answer 13 · answered Dec 07 '09 at 16:16

0

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

answered Dec 07 '09 at 16:16

Thomas Jung

32,428
9
84
114

These constructs are language specific and may be serialized ontop of fundamental types. – Hassan Syed Dec 07 '09 at 16:19
I consider these to be data types, not data structures. I imagine there are great arguments on both sides, but I also know these cold, so it's irrelevant for my purposes. Good call though :) – jakeboxer Dec 07 '09 at 16:21
Structures are a kind of mapping from name to value. While the C-language `struct` is language-specific. The "record" (in COBOL or Pascal parlance) does exist in multiple languages. This is the basis for "class" definitions. So I would argue that it is not language specific, but exists almost everywhere. – S.Lott Dec 07 '09 at 16:22
I'm interested to hear about a programming language that does not support a struct-like construct! – Thomas Jung Dec 07 '09 at 16:25

score 0 · Answer 14 · answered Dec 07 '09 at 16:18

0

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

answered Dec 07 '09 at 16:18

Glenn

1,169
1
14
23

dfa · Answer 15 · 2009-12-07T16:25:43.490

0

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

Graphs
Affine transformations
Solving linear systems
Markov chains
etc

edited Dec 07 '09 at 16:25

answered Dec 07 '09 at 16:19

dfa

114,442
31
189
228

Not fundamental imo as they can be emulated using arrays. – Hassan Syed Dec 07 '09 at 16:22
what can't be emulated using arrays? – jk. Dec 07 '09 at 16:27
@jk everything can be, perhaps you should change the answer to be "sparse" matrices. These should not be emulated using arrays and I would think are fundamental. – Hassan Syed Dec 07 '09 at 16:29

score 0 · Answer 16 · answered Dec 07 '09 at 16:20

0

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.

answered Dec 07 '09 at 16:20

S.Lott

384,516
81
508
779

offtopic post, he is not asking about the names of programming manuals. – Hassan Syed Dec 07 '09 at 16:23
Sorry, but the reference material in these language references will answer the question. – S.Lott Dec 07 '09 at 16:29
Well most of those types exist to provide complexity guarantees, and as such are not fundamental. I doubt the manuals are going to be discussing the containers in a language neutral way either. – Hassan Syed Dec 07 '09 at 16:36
The "reading" part of the answer is central. Read the descriptions. Learn what other people thing fundamental data structures are. – S.Lott Dec 07 '09 at 16:52
@S. Lott --I agree, hardly off-topic. It's not like you're shilling for the publishers. – Klay Dec 07 '09 at 17:02

score 0 · Answer 17 · answered Dec 07 '09 at 16:37

0

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

answered Dec 07 '09 at 16:37

Jason Baker

192,085
135
376
510

score 0 · Answer 18 · answered May 21 '10 at 22:47

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".

List of fundamental data structures - what am I missing?

18 Answers18