|
> If you remove a node in the list now you have to rewrite all the values in the links array. You actually don't. You can just keep two lists within the same structure, one for occupied nodes and one for free nodes, and just move deletions to the head of the free nodes list. Example List: Data: [ a, 0, c, d, e ]
Links: [ 2, -1, 3, 4, -1 ]
Head of occupied nodes: 0
Head of free nodes: 1
Link shape: Occupied Nodes: 0 -> 2 -> 3 -> 4 -> []
Free Nodes: 1 -> []
To Delete C: data[2] = empty // free data
links[2] = 1 // Repoint 2 -> 1
links[0] = 3 // Repoint 0 -> 3
firstFreeNode = 1
This changes the data such: Data: [ a, 0, 0, d, e ]
Links: [ 3, 2, -1, 4, -1 ]
Head of occupied nodes: 0
Head of free nodes: 2
New shape: Occupied Nodes: 0 -> 3 -> 4 -> []
Free Nodes: 2 -> 1 -> []
|