If Linked List and Array are fundamental data structures what type of data structure are tree, hash table, heap etc?

I was going through data structure online class and it was mentioned that linked list and array are fundamental data-structures and so my question is about Hash table, Heap, tree and graph are those not fundamental data structures and 开发者_运维百科if not are they derived from any other data structure ?

Thanks.

List and array could be considered fundamental because almost every single data structure is composed by pieces of these original data structures.

Graphs for instance, can be array backed or list backed (usually for sparse graphs).

But AFIAK as is many things in computer science it is not formalized what a "fundamental data structure" might mean mathematically.

You could consider arrays and linked lists fundamental in that there's essentially a single way to implement them (a sequence of contiguous objects for an array, a linear chain (singly or doubly linked) of objects for a linked list).

The more advanced data structures could be considered "derivative" in that they can be implemented multiple ways, and essentially come back to arrays and linked lists at the lowest level. Examples:

---An n-ary tree is generally implemented as a series of linked nodes (like a list) but with each node containing an array of child links. For a binary tree, you don't usually see the array overtly because the children are usually given the names left and right.

---Hash tables can be implemented in multiple ways. For a chained hash table, it's implemented as a (sparse) array of linked lists. For a probed or open addressed hash table, it's just a big array with collision logic.

---Sets are usually trees or hash tables, and thus transitively defined in terms of arrays and lists

---Stacks, queues, vectors, etc. are just arrays with special semantics imposed.

I agree with the other posters that CS doesn't really have a "textbook" definition of fundamental data structures, but you can easily see it to be "de facto" true.

Interesting question, by the way...

I'm not aware of an accepted definition in computer science of "fundamental data structure", or even that it is a conventionally used term at all.

But it's an interesting question, as I can think of useful definitions. After all, the data structures we build in an HLL are built out of something. (Simply reducing all data structures to "is the language and platform Turing-complete" seems silly.)

So I can think of two reasonable uses for the term:

• It could describe the data structures with which all those others are built, or could be built, or "will be built in this class", or some other sort of axiomatic starting point.

• It could describe the data structures that are built in to a given language

In Lisp (well Scheme anyway), the only fundamental data structure is a pair. Everything else is constructed from this type.

You'll have to specify your language to find out what the fundamental data structures for that language are.

Edit: Ok, Java and C++. I'd imagine that all C++ library containers like Vector and Queue would be based on the humble array, but in Java more types may be built-in. I guess it depends on how you define "fundamental".

I'd disagree. The fundamental data type is the array of words. That's what all modern RAM chips provide. Everything else is an abstraction created by programs. Linked list? That uses one word per node for a "next pointer", possibly one word for a "previous pointer", and then some words for the node data. Hashtables are another abstraction on top of that array of words.

Even arrays of bytes are an abstraction; they are implemented by sub-addressing each byte. This abtraction is ofen provided by the CPU, though.