I think any graph node can use the same technique, but here I present a simple yet interesting use case — a linked list with each node allocated from an array. https://github.com/tiger40490/repo1/blob/cpp1/cpp/lang_66mem/slistFromArray.cpp shows three home-made implementations:
- backing array of dummy link nodes, pre-allocated at compile time
- backing array of dummy link nodes, pre-allocated from free store aka DMA
- backing array is a byte array on heap or data section. Each link node is constructed via placement-new.
Here are a few Advantages that I consider minor because linked list is seldom needed in low-latency
- d-cache efficiency
- eliminates runtime load on heap allocator, since memory is pre-allocated. See malloc=long considered costly
Advantage #3: For c++ algo questions, this set-up has an interesting advantage — The node address is now an index into the backing array. This index is a natural auto-increment ID , based on creation order.
Now, the biggest advantage of linked list over vector is mid-stream insert/delete. One of the biggest disadvantages is lack of random-access. If nothing happens mid-stream (as in coding questions), then we can achieve random-access-by-id using array as backing store.
If nothing happens mid-stream, then this linked list is physically similar to an array with extra capacity.
This technique won’t work in java because java array of Node is array-of-pointers.