Editing Unrolled linked list (section)

==Overview==
A typical unrolled linked list node looks like this:

  '''[[record (computer science)|record]]''' node {
      ''node'' next       ''// reference to next node in list''
      ''int'' numElements ''// number of elements in this node, up to maxElements''
      ''array'' elements  ''// an array of numElements elements,''
                      ''//   with space allocated for maxElements elements''
  }

Each node holds up to a certain maximum number of elements, typically just large enough so that the node fills a single [[cache line]] or a small multiple thereof. A position in the list is indicated by both a reference to the node and a position in the elements array. It is also possible to include a ''previous'' pointer for an unrolled [[doubly linked list]].

To insert a new element, we find the node the element should be in and insert the element into the <code>elements</code> array, incrementing <code>numElements</code>. If the array is already full, we first insert a new node either preceding or following the current one and move half of the elements in the current node into it.

To remove an element, we find the node it is in and delete it from the <code>elements</code> array, decrementing <code>numElements</code>. If this reduces the node to less than half-full, then we move elements from the next node to fill it back up above half. If this leaves the next node less than half full, then we move all its remaining elements into the current node, then bypass and delete it.