Are there any known "adaptive data structures", for example, which can change on-fly from array to linked-list, or from the latter to binary tree depending on access patterns to it? For example: small number of elements: stay as array. 5-10 elements: convert itself to linked list. More elements: convert to binary tree.

  • 5
    $\begingroup$ What do you mean by "are there"? You've described it, ergo it exists; writing out pseudo-code seems to be an easy exercise. The question is, does it gain you anything? What goal are you pursueing? Google "self-adjusting data structure" for starters; they don't do what you describe, but do restructure themselves in reaction to access patterns. $\endgroup$ – Raphael Jul 25 '16 at 8:33
  • $\begingroup$ There are probably popular solutions, so I would love to hear about them... $\endgroup$ – Xenia Galinskaya Jul 25 '16 at 13:55
  • 1
    $\begingroup$ Something like splay tree? With change between linked-list and array something more is needed - the VM or own function maintaining such conversions would be needed (data structure not matter how sophisticated does not care / have insight into memory used), but splay tree adapts on every search. Taking linked-list - it can be implemented using array (flat 2n elements, two dimensional 2 x n) but where and how elements are stored is not part of structure. $\endgroup$ – Evil Jul 25 '16 at 17:15
  • $\begingroup$ I think a B tree of order 7, say, can be thought of as an array for the first 6 elements being inserted. Does that qualify? $\endgroup$ – 500 - Internal Server Error Jul 25 '16 at 17:36
  • $\begingroup$ Not sure what the purpose of the question is, do you want to use it or is it more academic interest? There is, for example, the k-dimensional PH-Tree, which has 3 different 'modes' in which an internal node can be represented. Roughly speaking: for small nodes it uses a list of key-value pairs, for medium nodes it uses an array of values (size=2^k; keys are implicit in the array position), for large nodes it splits nodes into a sub-tree. This minimizes memory usage while facilitating dynamic updates. See www.phtree.org. $\endgroup$ – TilmannZ Jul 26 '16 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.