Lately I have been looking around for a formal definition of a what a data structure is. I cannot find neither a paper, nor a book with such a definition. Even the famous "The Art of Computer Programming" is missing one. Even for just a linked data structure, e.g., binary search tree, I couldn't find one.

So, is there one? Perhaps a paper that is talking about it?

By formal definition I'm thinking of something like "A data structure is a tuple (Op, El, ..) where ...".


closed as off-topic by Kaveh, R B, Sasho Nikolov, Kristoffer Arnsfelt Hansen, Mohammad Al-Turkistany May 27 '15 at 18:40

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, R B, Sasho Nikolov, Kristoffer Arnsfelt Hansen, Mohammad Al-Turkistany
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Abstract Data Type? $\endgroup$ – Kaveh May 22 '15 at 2:31
  • 1
    $\begingroup$ I think this survey might be relevant: "Cell probe complexity" cs.umd.edu/~gasarch/BLOGPAPERS/cellprobesurvey.pdf $\endgroup$ – Thatchaphol May 22 '15 at 3:07
  • $\begingroup$ @Kaveh I'm interested in the concrete implementations of abstract data types. ("This contrasts with data structures, which are concrete representations of data, ..."). $\endgroup$ – foobar May 22 '15 at 9:08
  • $\begingroup$ It is not clear what you are really looking for. ADT is exactly the kind of the thing you describe in the last paragraph. A data structure is just an implementation of an ADT, not what you describe in the post. I don't see why this doesn't answer your question. $\endgroup$ – Kaveh May 22 '15 at 16:04
  • $\begingroup$ An abstract data type is a problem statement. Saying that a data structure is "just" an implementation of an ADT is like saying that randomized quicksort is "just" an implementation of sorting. True, but completely missing the point. $\endgroup$ – Jeffε May 26 '15 at 3:11

Data structures is nothing but the ways how data of different kinds can be structured in a systematic way. The actual definition may be somewhat lengthy and descriptive which can be found on different sources. But it is all about defining structures of your data that will satisfy your need to solve any particular problem.


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