   Data Structures: Common functionality?
  Hi, I'm currently reading up on data structures and wanted to get some other people's opinions before I charged forward with a blindfold still wrapped around my eyes. I've observed that there are multiple levels of data structures. The first of these I would call the "core" structures. These core structures are the basis on which less "core" structures are based. Examples of core structures would be:- Arrays- Linked Lists- Trees- Etc.Then there are other data structures that build upon the core structures. Examples of these structures would be:- Stacks- Queues- Hash Tables- Etc.Which essentially use the core structures and manipulate them in different ways.What I am currently doing is analyzing the core structures and trying to find out functionality that is relevant to all of them. So far I have come up with the following operations:**For definition's sake, data is what the client is storing a container of and a Node is a object that holds the data and its orientation within the container.- Insert/Remove/Replace/Find Data.- Insert/Remove/Replace/Find Nodes.- Retrieve the size[in Nodes] the container is. My question is, are there any other operations that all "core" structures have in common that I might have missed?Thanks for your time.Jonathan   
Quote:Original post by Trandafira- Arrays- Linked Lists- Hash Tables- TreesThese are examples of data structures. A data structure, as the name implies, is defined by the structuring of the information it contains. You can talk about a hash table in terms of linked lists and arrays, sure. I'd disagree with your "core" argument, because I think any such ordering is arbitrary: What is a linked list, but a tree where each element has 0 or 1 child? What is a tree, but a directed acyclic adjacency-list graph with one root? What is an adjacency-list graph, but a set of nodes, each one with a linked list of pointers?Quote:- Stacks- QueuesThese are abstract data types. They are defined not by how they are implemented (I can think of several ways to implement them offhand) but by what operations they support and what the meaning of those operations are.BTW, you're missing one of the most important ADTs, the graph.   ;Quote:Original post by SneftelQuote:Original post by Trandafira- Arrays- Linked Lists- Hash Tables- TreesThese are examples of data structures. A data structure, as the name implies, is defined by the structuring of the information it contains. You can talk about a hash table in terms of linked lists and arrays, sure. I'd disagree with your "core" argument, because I think any such ordering is arbitrary: What is a linked list, but a tree where each element has 0 or 1 child? What is a tree, but a directed acyclic adjacency-list graph with one root? What is an adjacency-list graph, but a set of nodes, each one with a linked list of pointers?Quote:- Stacks- QueuesThese are abstract data types. They are defined not by how they are implemented (I can think of several ways to implement them offhand) but by what operations they support and what the meaning of those operations are.BTW, you're missing one of the most important ADTs, the graph.Yeah I thought everything came from graphs or could be described in terms of graphs?Must be some math or theory behind that?Anyways, I would think looking at the STL should give you an idea of what you are missing or operations you have missed since I'm sure they've had years and hundreds of people think of all this stuff already.In fact I suggest you save yourself some time and grief by learning about the STL and how to use it unless you are reinventing the wheel for a specific purpose you didn't mention?;Quote:Original post by daviangelIn fact I suggest you save yourself some time and grief by learning about the STL and how to use it unless you are reinventing the wheel for a specific purpose you didn't mention?ADT is the first real CS curriculum topic. That is the only place to start. STL is a hack of too many abstractions that C++ offers. It has fair interface, but far from perfect.Just about every university today publishes their courses. Start there, search for ADT (Abstract Data Types). It should be 101 course.Quote:- Insert/Remove/Replace/Find Data.- Insert/Remove/Replace/Find Nodes.- Retrieve the size[in Nodes] the container is. ADTs generally do not have size parameter. They work on Turing machine which has infinite tape.Replace/find are limited to a small number of ADTs. Stack/queue don't have them, for example, they have only push/pop/top/empty.It's incredibly important to understand the ADTs as they are defined. Their canonical definition allows any and all other operations to be performed in optimal manner characteristic to that structure.While some hardware/software exhibits different performance characteristics, from algorithmic perspective these aren't relevant and are merely a matter of implementation.   