Understanding the Macro Aspects of Data Structures

Question

I am studying data structures right now, but I still need to find a teacher/site/book with a clear explanation of the macro aspects of this topic.

What I mean is: most lessons/text books mix everything together, with no logical structure. They start with linked lists, then talk about stacks, queues, heap priorities and so on. But as far as I can tell, a linked list and a stack are not really in the same category. After all you can use the linked list to implement different types of data strcutures (e.g., a stack, a queue, etc).

So would it be right to say that the types of data structures are: the stack, the queue, the hash-table, the heap, and the tree; while arrays (static) and linked lists (dynamic) are tools you are going to use to implement those data structures?

If the above statement is not completely correct, maybe a linked list is indeed a data structure in itself, and therefore we would be using one data structure (e.g., the linked list) to build other data structures on top of it (e.g., a stack)?

Answer 1

I would define them as the interface they provide, including complexity of the operations.

One could after all implement a linked list with an array and vice versa (and recursivly), but it would be impossible to keep the complexity.

Update: To clarify: A stack is defined as a datastructure with constant-time add to top, and constant-time remove at top. It doesn't say how we implement it. One could implement it using an array, or a linked list, but also a double linked list, but that is irrelevant.

The atomic we have on a computer is (binary) memmory, and the most basic form of memmory is an array, thus one can create every kind of datastructure using an array.

One could imagine we had another atomic (maybe a qubit). Then a stack would still be a stack, but maybe we couldn't implement it with that atomic.

Answer 2

Stacks, Queues, Heaps, Hash table are what are considered abstract data structures. The implementation is up to you to implement. You can use a linked list to do it, or you may need to used another abstract data type to create it. For example, a priority queue can be created using a min-heap which can be created using a binary tree. The implementation is up to you as long as you follow the "rules" (e.g min-heap having a running time for findMin being constant or the lookup of a value in a hash-table being constant, there are a few ways to do that)

Answer 3

Yes, the emergent properties of arrays and linked lists allow them to be treated as a data structure "primitives", however that does not mean the linked list is exactly what other structures use underneath.

The important thing to take away from linked lists is that you point to arbitrary spots in memory, rather than holding onto a sequential grouping of memory slots. If random access improves the performance of a more abstract structure, then it's worth the optimizations an array provides. Whereas, using arbitrary pointers gives you slightly more freedom of how you use your memory.

For example, in Clojure a map is implemented as an array underneath until it becomes more beneficial to use a high level of abstraction, for which it switches out the implementation.

Answer 4

I would say you always need to switch between macro (system level) and micro views (let's say function level) if you are to ever understand something out of programming the middle or big systems.

For switching between views, books like:

The Art of Computer Programming by Donald E. Knuth (algorithm to micro level)

Algorithms by Rober Sedgewick (versions in Java, C++, C) (both macro to algorithm and algorithm to micro level)

Algorith Design Manual by Steven Skienna (macro to algorithm level)

The Pragmatic Programmer by Dave Thomas, Andy Hunt

By far, the last part from Algorithms in Java 4th Edition by Robert Sedgewick is the one that will help change these micro and macro glasses often, but without loosing sight of the big prize.