Say we have a chain of 3 clusters to be updated. Each one has a reference to the cluster that is updating right before it, and to the one right after it.
The first cluster has a null
value as its previous cluster, the last cluster has a null
value as its next cluster.
There are also two additional references that are always pointing to the start and the end of the chain.
Cluster A doesn't know that C exists and vice-versa, since they are not touching.
Possibilities:
- Cluster B gets destroyed:
Since it wasn't the first or last cluster we only have to fix A's next cluster and C's previous cluster references, joining them together:
- Cluster A is destroyed
Since A was the first in the chain we need to move the head reference to B, which is now the first cluster. We also must set B's previous reference to null, as there are no clusters before it:
- Cluster C is destroyed
Since C was the last in the chain we need to move the tail reference to B, which is now the last cluster. We also must set B's next reference to null, as there are no clusters after it
- Cluster D is added to the end
We have to set C's next reference to D, and also set the tail reference to D:
We are only ever going to add clusters to the end of the chain, however you can think of adding a cluster in the middle as a reversed case 1.