This list variation is concerned mainly with memory efficiency. It was
mentioned earlier that pointers consume space. If we have several
pointers in each node then the space needed for the pointers may be a
significant portion of the total space we require. For example, if you
implemented the type string as a list of characters, then
in each node you would have one character and one, or perhaps two,
pointers. This is extremely poor memory efficiency: 2 pointers
typically require the space of 8 characters so to store a string of
length N you would need 9N bytes! You'd probably be much better off
with a big array!
One solution to this problem is to store more than one value in each node. A node contains space for some fixed number of elements, typically this would be an array; and, in addition, you now need to keep track of how many values are actually stored in the node. When you insert a new value, you first check to see if there is room for the value in the nodes that have already been allocated. If there is, you put the value there; only if there is no room in the existing nodes do you allocate a new node. Now we still have the same number of pointers per node, but the ratio of pointers to elements is much smaller (better).
For example, suppose we had a collection of 10 values, {0,1,2,3,4,5,6,7,8,9}, and were allowed 6 values per node. Then this collection could be stored with just two nodes:
Assuming a pointer is 4 units of storage and all other values are 1 unit, the total space required for these two nodes is 2*(1+6+4) = 22 units. To store each value in a node by itself requires 10*(1+4) = 50 units.
This strategy can backfire if we are not careful to keep the nodes as full as possible. As mentioned above, ideally you would not allocate a new node unless there was no space available in any of the existing nodes. However, when you have operations like DELETE, that can create free up space in any node, there is no obvious way to find available space in constant time. But there is a non-obvious way to do it (for collections)! I leave that as a challenge to you.
