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)?
Best Answer
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.