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.

1
2
3
4
5
6
        -----    -----    -----
null <> | A | <> | B | <> | C | <> null
        -----    -----    -----
          ^                 ^
          |                 |
         Head              Tail

Cluster A doesn't know that C exists and vice-versa, since they are not touching.

Possibilities:

  1. Cluster B gets destroyed:
1
2
3
4
5
6
        -----            -----
null <> | A | <> poof <> | C | <> null
        -----            -----
          ^                ^
          |                |
         Head             Tail

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:

1
2
3
4
5
6
        -----    -----
null <> | A | <> | C | <> null
        -----    -----
          ^        ^
          |        |
         Head     Tail
  1. Cluster A is destroyed
1
2
3
4
5
6
                -----    -----
null <> poof <> | B | <> | C | <> null
                -----    -----
          ^                ^
          |                |
         Head             Tail

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:

1
2
3
4
5
6
        -----    -----
null <> | B | <> | C | <> null
        -----    -----
          ^        ^
          |        |
         Head     Tail
  1. Cluster C is destroyed
1
2
3
4
5
6
        -----    -----         
null <> | A | <> | B | <> poof <> null
        -----    -----         
          ^                 ^
          |                 |
         Head              Tail

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

1
2
3
4
5
6
        -----    -----
null <> | A | <> | B | <> null
        -----    -----
          ^        ^
          |        |
         Head     Tail
  1. 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:

1
2
3
4
5
6
        -----    -----    -----    -----
null <> | A | <> | B | <> | C | <> | D | <> null
        -----    -----    -----    -----
          ^                          ^
          |                          |
         Head                       Tail

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.

Edit
Pub: 17 Jun 2020 23:38 UTC
Edit: 17 Jun 2020 23:43 UTC
Views: 293