In-Place Reordering of Doubly Linked List Nodes to Ensure Memory Contiguity

Question

I am addressing an optimization problem involving a doubly linked list, where nodes are allocated within a contiguous memory block of fixed size $N$. Initially, the spatial locality of nodes in memory is not preserved, meaning that the next pointers of nodes might refer to any other node within the block.

The objective is to reorder the nodes such that for each node $i$, its successor node $j$ in the list is also its immediate successor in memory (i.e., memory[i] directly precedes memory[i + 1].

A trivial solution would involve traversing the linked list, storing the nodes in an auxiliary ordered container, and then copying them back into the memory block in order.

However, the goal is to reorder the nodes directly within the memory block, potentially using an auxiliary structure but performing the reordering through in-place swaps. Is such in-place reordering even feasible?

Answer 1

If you know all pointers to nodes, and you have enough free space for a single node, then you iterate through the nodes. For the I-th node, you copy the node stored at address I to the free space, copy the I-th node to address I, remember that the old location of the I-th node is now unused, and update all the pointers to those two nodes. You also need to check whether by coincidence the I-th node is already stored at address I; in that case you must do nothing for this node.

This takes time O(n), so massively faster than any O(n log n) sorting.

Answer 2

Take any in-place sorting algorithm and simply sort the nodes based on their next pointers.

Answer 3

potentially using an auxiliary structure

The next and previous pointers of the double linked list can be used as the basis of the aux structure

Then after the reorder you update the pointers.

The most straightforward way would be selection sort where you don't need to search for the smallest (it's the next pointer of the last node) and on swap you update the pointers to the node you are moving out of the way:

int j = root - array[0];
array[0].prev->next = &array[j];
swap(array, 0, j);
for(int i = 1; i < array_len; i++) {
    int j = array[i-1].next - array[0];
    array[i].prev->next = &array[j];
    swap(array, i, j);
}
root = &array[0];
for(int i = 1; i < array_len; i++) {
    array[i-1].next = &array[i];
    array[i].prev = &array[i-1];
}

This is an O(n) operation.

Answer 4

O(n) but non-optimal:

You could just swap each node into the space it belongs as you traverse the list. Each swap will require 4 random accesses to the heap: Two read-writes for the nodes you're swapping, two writes to update the references on the prev and next nodes.

Better cache performance, with two passes:

Before you move anything, you know what the next/prev addresses will be as you traverse the list. So:

1: Traverse the nodes in list order, updating the next/prev of each node to its correct final address.

2: Traverse the space in memory order, with a pointer at the start of the block. Increment your pointer until you find another node in the wrong position (correct_address==prev+1==next-1). Otherwise, store a copy and mark the position in the list as deleted. Swap the stored copy with the one in its correct position, then swap the newly stored node with one in its correct position. Continue until you place a node in an empty position. Increment pointer and repeat.

Each node is updated once with its new address, then moved at most 1 time into its proper place. Each pass requires one random-access read-write per node. The second pass also includes a sequential read of the memory block as the pointer progresses, which could be significant if the list is much smaller than the block of memory it's in.

A further optimization to take advantage of existing sections of sequentially positioned nodes would be to store a small buffer - still small enough to keep in the stack - of multiple nodes instead of just one, and iterate through it, swapping contiguous chains of nodes, and replenishing any empty nodes that are swapped in from the pointer.

Answer 5

Inspired by @maybeWeCouldStealAVan, a one-pass algorithm. We're doing a forward pass through the list, so we don't try to keep node::prev up to date. We do need to keep node::next up to date as we swap values around

Let `Head` be the head of the list of unprocessed nodes (initially that's the whole list)
Let `N` be the number of nodes reordered so far (initially 0).
# This number is sufficient to define the list of processed nodes.
# The head of that list is memory[0], memory[x].next==x+nodesize,
# memory[x].prev==x-nodesize except for of course memory[0].prev==null.

To process one node, we 
* update memory[N].prev.next to Head
* swap memory[N].value and Head.value
* set memory[N].prev to N-nodesize and .next to N+nodesize 
* increment N
* set Head to Head.next

If it happens that Head=memory[N] at any given time, it means that that node is already in the right place. In that case, we could skip the value swap, but this is unlikely and the check is likely more expensive on average than the occasional unnecessary swap-with-self.

This involves O(N) read/writes in sequential order (cache-friendly) and O(N) random writes to move the remaining unordered values and keep their linked-list order. This will likely bottleneck on the random write speed, which is the fundamental architecture limit of this problem. To beat this, you have to be able to make assumptions about the list order.