Are you familiar with Donald Knuth's "Dancing Links" ??
Its a covering-problem solver (NP-complete) that uses linked lists highly-efficiently. All nodes are "statically allocated" (at least, with respect to the algorithm), because the covering-problem takes up a constant amount of space.
The linked-list "Dances", pointing at other nodes to represent which combination of covers are attempted. So any link could potentially point to any other link later in its list. However, the number of nodes themselves is constant and set before the algorithm runs.
As such, the linked-list is fully X1->X2->X3->X4... at the start of the algorithm. (where X1, X2, X3 are contiguously allocated in memory). If X3 is proven to "not be a good guess" for our covering problem, then it is cut out of the linked list (X1->X2->X4).
All links remain in order, and are ordered on a 2-dimensions (So not only X1->X2->X3... but also X1->Y1->Z1...). Where X, Y and Z are the compound-elements trying to cover locations 1, 2, 3, ...
------------
Most simple malloc implementations also have the free-list as a simple linked-list that is in fact, ordered in memory. (The first node in the free-list is the lowest numbered RAM spot, while the final node in the free-list is in the highest-numbered RAM spot).
The FAT32 linked-list across a hard drive is also nicely ordered (and when it isn't, the user will perform "defragmentation" to reorder the list and optimize the hard drive).
-----------
IMO, the "nicely ordered Linked List" is uncommon, but... common enough that its worth discussion. And sure, maybe we don't use FAT32 filesystems today very often, but that's the technology I used growing up lol. I know the methodology works!!
I think you need to be aware of why such an implementation (fat32) had to exist. As I believe (I also grew up with fat32) that it basically vanished when HDDs with caches in the MB started to show up. Journaling became a thing; actual caches became a thing so the HDD could actually lay things out well by utilizing said cache.
NTFS still needed to occasionally be defragmented but it allocated more of a buffer to prevent having to do so at all.
I think; in general; You're very spot on about utilizing continuous arrays of memory for linked lists as they will almost always result in better performance characteristic (unless you really need insertion/removal in order and it's very write heavy).
Comments
Are you familiar with Donald Knuth's "Dancing Links" ??
Its a covering-problem solver (NP-complete) that uses linked lists highly-efficiently. All nodes are "statically allocated" (at least, with respect to the algorithm), because the covering-problem takes up a constant amount of space.
The linked-list "Dances", pointing at other nodes to represent which combination of covers are attempted. So any link could potentially point to any other link later in its list. However, the number of nodes themselves is constant and set before the algorithm runs.
As such, the linked-list is fully X1->X2->X3->X4... at the start of the algorithm. (where X1, X2, X3 are contiguously allocated in memory). If X3 is proven to "not be a good guess" for our covering problem, then it is cut out of the linked list (X1->X2->X4).
All links remain in order, and are ordered on a 2-dimensions (So not only X1->X2->X3... but also X1->Y1->Z1...). Where X, Y and Z are the compound-elements trying to cover locations 1, 2, 3, ...
------------
Most simple malloc implementations also have the free-list as a simple linked-list that is in fact, ordered in memory. (The first node in the free-list is the lowest numbered RAM spot, while the final node in the free-list is in the highest-numbered RAM spot).
The FAT32 linked-list across a hard drive is also nicely ordered (and when it isn't, the user will perform "defragmentation" to reorder the list and optimize the hard drive).
-----------
IMO, the "nicely ordered Linked List" is uncommon, but... common enough that its worth discussion. And sure, maybe we don't use FAT32 filesystems today very often, but that's the technology I used growing up lol. I know the methodology works!!
I think you need to be aware of why such an implementation (fat32) had to exist. As I believe (I also grew up with fat32) that it basically vanished when HDDs with caches in the MB started to show up. Journaling became a thing; actual caches became a thing so the HDD could actually lay things out well by utilizing said cache.
NTFS still needed to occasionally be defragmented but it allocated more of a buffer to prevent having to do so at all.
I think; in general; You're very spot on about utilizing continuous arrays of memory for linked lists as they will almost always result in better performance characteristic (unless you really need insertion/removal in order and it's very write heavy).