6

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)?

4 Answers 4

6

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.

2
  • I am not completely sure of what you mean, but thanks for chiming in. Aug 15, 2011 at 20:02
  • So could we say that we have more basic types of data structures (like the array and the linked list) that might be used to implement other, more complex types of data structures? Aug 15, 2011 at 20:58
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)

2
  • Gotcha for Stacks, Queues, Heaps and Hash Tables. What about linked lists and arrays, though, what are they? Aug 15, 2011 at 20:53
  • Linked Lists and Arrays are just data structures. They can also be the building blocks of other structures (the abstract data structures) as well.
    – Jetti
    Aug 15, 2011 at 21:03
0

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.

2
  • That "primitives" explanation makes sense. And yeah I know that a linked list is only one of the options of what you might have underneath other data structures. Thanks. Aug 15, 2011 at 20:55
  • @Daniel: My point was that underneath is not necessarily a linked list, but linked list-like. That is, it stores data (via references or values) in a way that's not guaranteed to have 0(1) lookup.
    – Jeremy
    Aug 15, 2011 at 21:43
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.