Can any data structure be represented by one-dimensional arrays?

I believe so. For example,

  • Each node of a binary tree would use 4 array cells: one for a pointer to the father node, two pointers to the two sons, and one for the value.
  • Each element of a hash table would use 4 or 5 array cells: the index, possibly a random key that efficiently encode the index, the value, a pointer to the previous index, and a pointer to the next index. This would make finding, updating, deleting or inserting an element a bit slow, but performance can be boosted by storing, at the beginning of the array, a list of pointers to 1,000 indices evenly spaced in the index universe. 

A similar arguments can be used for graphs (as in graph theory), non-binary trees, heaps, stacks, linked lists etc.

Indeed, before programming languages offered advanced data structures, sophisticated objects and types, recursion (and  much more) -- all the data -- had to be stored in (organized) arrays. Trees, hash tables etc. were simulated by using arrays and pointers. Even recursion.

Are there exceptions? In some ways, we are getting back to the old times, with unstructured data, such as member postings on social networks. Although structuring unstructured data (by putting it into clusters and taxonomies) allow it to be manipulated much more easily.

Views: 3585

Reply to This

Replies to This Discussion

The answer is yes since 1936. Any program with any data can be represented as binary array. First Turing and then Post published their article in that year. We call these things Turing and Post-Turing machines.


© 2021   TechTarget, Inc.   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service