But what if they were pointing to adjacent memory positions in the common case? What if the problem you're suggesting doesn't exist in some circumstances?
Like in Knuth's Dancing Links. The neighbors of links are laid out in memory next to each other. If the list upon program startup is "1 -> 2 -> 3", we know that 1, 2, and 3 are neighbors in memory.
And what if it is demonstrated that this weird "linked list with nodes laid out next to each other" is shown to be sufficient to solve NP-complete problems like the exact-cover problem with great efficiency in practice?
-----------------
What if, when creating 100 nodes at a time, we lay out all 100-nodes in a row.
chunk = malloc(sizeof(Node) * 100).
for(int i=99; i>=0; i--){
chunk[i].next = head;
chunk[i].data = foobar();
head = chunk[i];
}
Now we have the spatial locality you so desire, while still retaining the ability to rearrange the list. In fact, add/remove is still possible (though the malloc/free is harder to keep track of: if you're in a Dancing-links scenario, you may not ever need to call free)