Databases
StackOverflow2013
Postsdbo
POData structure name: combination array/linked list
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POData structure name: combination array/linked list
    primarykey
    data
    text
    <p>I have come up with a data structure that combines some of the advantages of linked lists with some of the advantages of fixed-size arrays. It seems very obvious to me, and so I'd expect someone to have thought of it and named it already. Does anyone know what this is called:</p> <p>Take a small fixed-size array. If the number of elements you want to put in your array is greater than the size of the array, add a new array and whatever pointers you like between the old and the new.</p> <p>Thus you have:</p> <pre><code>Static array ————————————————————————— |1|2|3|4|5|6|7|8|9|a|b|c| ————————————————————————— Linked list ———— ———— ———— ———— ———— |1|*-&gt;|2|*-&gt;|3|*-&gt;|4|*-&gt;|5|*-&gt;NULL ———— ———— ———— ———— ———— My thing: ———————————— ———————————— |1|2|3|4|5|*-&gt;|6|7|8|9|a|*-&gt;NULL ———————————— ———————————— </code></pre> <p><strong>Edit</strong>: For reference, this algorithm provides pretty poor worst-case addition/deletion performance, and not much better average-case. The big advantage for my scenario is the improved cache performance for read operations.</p> <p><strong>Edit re bounty</strong>: Antal S-Z's answer was so complete and well-researched that I wanted to provide em with a bounty for it. Apparently Stack Overflow doesn't let me accept an answer as soon as I've offered a bounty, so I'll have to wait (admittedly I am abusing the intention bounty system somewhat, although it's in the name of rewarding someone for an excellent answer). Of course, if someone <em>does</em> manage to provide a better answer, more power to them, and they can most certainly have the bounty instead!</p> <p><strong>Edit re names</strong>: I'm not interested in what <em>you'd</em> call it, unless you'd call it that because that's what authorities on the subject would call it. If it's a name you just came up with, I'm not interested. What I want is a name that I can look up in text books and with Google. (Also, here's a tip: Antal's answer is what I was looking for. If your answer isn't "unrolled linked list" without a <em>very</em> good reason, it's just plain wrong.)</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USme_and
    1. USme_and
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POData structure name: combination array/linked list
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POData structure name: combination array/linked list
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POData structure name: combination array/linked list
      1. This table or related slice is empty.
      1. VTUpMod
    1. COInteresting from an algorithmic complexity perspective - technically you are O(n) for nearly all basic operations (which is pretty bad) but you get a very low constant scale factor (which is good, all else being equal!). Good for you if that works for your application but I'd still suggest some careful benchmarking :-)
      singulars
      1. POData structure name: combination array/linked list
      1. USmikera
    2. COCorrect me if I am wrong. I have used C, C++ and Java, all of which allows you to store only one type of data. In the above case, some array elements are int, some are char and some are pointers. How will your array actually be declared? Are you using some kind of struct to represent this?
      singulars
      1. POData structure name: combination array/linked list
      1. USsrikfreak
    3. COsrikfreak: The idea is that while in a linked list, you have (in C++) `template <typename T> struct ll_node { T value; ll_node<T>* next; }`, here you would have something like `template <typename T> struct ull_node { T value[MAX]; size_t n_elements; ull_node<T>* next; }`. I don't think the array elements in the "static array" case are supposed to represent literal values, but if you want, I bet you could just think of them as hexadecimal numbers instead of characters.
      singulars
      1. POData structure name: combination array/linked list
      1. USAntal Spector-Zabusky
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload