Disjoint set implementation as linked list

I have just 'wrote' a linked list implementation of Disjoint Sets. This is the changed version of Bob Tian's implememnation. Can you take a look and tell me if there is something missing ? For instance memory leaks while destroying nodes. And please judge it also in performance matter.

I would like to change the long NodeAddress[9999] = {0}; to something better but:
this implementation is used for Connected-component labeling so every time I examine the pixel that needs to be added to labels array I add it. But in the end I do not know how many of them will be there and I need some way to access them (in case i would need to use them later on - for instance union it with another label)

```
#include

using namespace std;

long NodeAddress[9999] = {0};
int n=0;

class ListSet {
private:
struct Item;
struct node {
int val;
node *next;
Item *itemPtr;
};
struct Item {
node hd, tl;
};

public:
ListSet() { }
long makeset(int a);
long find (long a);
void Union (long s1, long s2);
};

long ListSet::makeset (int a) {
Item *newSet = new Item;
newSet->hd = new node;
newSet->tl = newSet->hd;
node *shd = newSet->hd;
NodeAddress[a] = (long) shd;
shd->val = a;
shd->itemPtr = newSet;
shd->next = 0;
return (long) newSet;
}

long ListSet::find (long a) {
node ptr = (node)a;
return (long)(ptr->itemPtr);
}

void ListSet::Union (long s1, long s2) {
node ptr1 = (node)s1;
node ptr2 = (node)s2;

Item *set2 = ptr1->itemPtr;
node *cur = set2->hd;

Item *set1 = ptr2->itemPtr;

while (cur != 0) {
cur->itemPtr = set1;
cur = cur->next;
}
//join the tail of the set to head of the input set
(set1->tl)->next = set2->hd;
set1->tl = set2->tl;
delete set2;
}

int main () {

ListSet a;
long s1, s2, s3, s4;
s1 = a.makeset(13);
s2 = a.makeset(25);
s3 = a.makeset(45);
s4 = a.makeset(65);
c

#include  // for assert
#include  // for memset

#include 

using namespace std;

// OMIT these as not very useful. Anyway, don't needlessly expose globals.

long NodeAddress[9999] = {0};
int n=0;

/* I've kept the class names for now, for the sake of recognition, but
they've each got different problems.

ListSet does a poor job of describing the class' purpose.
Since its purpose is to generate, find, and merge disjoint sets,
call it something like DisjointSetSource.

Item is too generic and not very descriptive of the class' function. It represents a disjoint set, but to reserve the name DisjointSet for its exported opaque equivalent, just call it Set, or since it's represented as a linked list of member nodes, maybe SetNodeList or SetMemberList.

node is also very generic, but it's a little more apt. Also, it's name should be capitalized by convention and for consistency. So, Node is OK, but better might be Member or since it's main features are to refer to its parent list and successor, call it ListMember.
*/

class ListSet {
private:
    typedef int ValueType;
    struct Item;

/ There's a non-trivial smattering of node and item processing cluttering up the ListMember methods. They really want to be full-fledged classes with a constructor, (possibly) destructor, and (possibly) mutators. Item needs write access to node::next and ListMember needs write access to itemPtr, so I'd keep the node members public. /

struct node {
        ValueType val;
        node *next;
        Item *itemPtr;

// So, add:

node (const ValueType& a);
        ~node ();
     };

    struct Item {

// So, add:

Item(node *shd) : hd(shd), tl(shd) {}
        void append(const Item*);
        // returns head node as "sign of life"
        node* remove(node* old);
    private:
        node *hd, *tl;
    };

/ Avoid exposing nodeAddress, especially as a global. It SHOULD use std::vec for dynamic growth or std::map if values are sparse. Wrap this in accessors to stay flexible, especially WRT ValueType, opening the door for (re)templatizing as in the originally posted code. /

private:
    node* nodeAddress[9999];

public:

    void setNodeAddress(const ValueType& a, node* shd) {
        nodeAddress[a] = shd;
    }

    node* getNodeAddress(const ValueType& a) {
        return nodeAddress[a];
    }

    // removeAll requires or maybe IS a third form of nodeAddress accessor

/* Why does a ListSet object ever need to be created?
When the original implementation used the global NodeAddress as its state,
all functions could be static and no ListSet instance ever created.
This would also be true if NodeAddress was a static member.

Yet, it was easy enough to improve on the design by making nodeAddress a normal data member. This provides a useful purpose for multiple ListSet instances.

Each managing its own disjoint sets, completely independently.
All the more reason to pull NodeAddress out of the API, where it is just noise. See main.
*/

ListSet() {
        // zero out nodeAddress in some type appropriate way
        memset(nodeAddress, 0, sizeof(nodeAddress));
    }

    ~ListSet() {
        removeAll();
    }

/* "long" is too general a type to use for "handles" like the return type, here. Better to make up a unique fictitious type:
*/

class DisjointSet;

    DisjointSet* exportSet(Item* result) { return (DisjointSet*) result; }
    Item* importSet(DisjointSet* input) { return (Item*) input; }

/ Use camelCase or under_scoring to makemultiwordnamesreadable. /

DisjointSet* makeSet(const ValueType& a);
    DisjointSet* find (const ValueType& a);
    void remove(const ValueType& a);
    void removeAll();

// Use suffix word rather than breaking lowercase convention to get around reserved words

void unionSets (const ValueType& a1, const ValueType& a2) {
        DisjointSet* s1 = find(a1);
        DisjointSet* s2 = find(a2);
        if (s1 && s2) {
            (void) unionSets(s1, s2);
        }
        // else error?
    }

    DisjointSet* unionSets (DisjointSet* s1, DisjointSet* s2);
};

ListSet::DisjointSet* ListSet::makeSet (const ValueType& a) {
    assert(!getNodeAddress(a));
    node *shd = new node(a);
    Item *newSet = new Item(shd);
    setNodeAddress(a, shd);
    shd->itemPtr = newSet;
    return exportSet(newSet);
}

ListSet::DisjointSet* ListSet::find (const ValueType& a) {
    node* ptr = getNodeAddress(a);
    if (ptr)
        return exportSet(ptr->itemPtr);
    // else error?
    return 0;
}

/* This used to be needlessly confusing with lines like:

Item *set2 = ptr1->itemPtr;
Item *set1 = ptr2->itemPtr;

I'm really still not sure the revision, below maintains the original intent, because of the set1/set2 naming confusion, but it does what the old code did.

Aside from avoiding such confused naming, use of an Item method
makes this code much easier to read. */

```
ListSet::DisjointSet* ListSet::unio

StackExchange Code Review Q#7905, answer score: 6