List of fundamental data structures - what am I missing?

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


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


Also the Graph data structure is fundamental.