Disjoint set implementation as linked list
#include &lt;assert.h&gt; // for assert
#include &lt;string.h&gt; // for memset

#include &lt;iostream&gt;

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&amp; 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&amp; a, node* shd) {
        nodeAddress[a] = shd;
    }

    node* getNodeAddress(const ValueType&amp; 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&amp; a);
    DisjointSet* find (const ValueType&amp; a);
    void remove(const ValueType&amp; a);
    void removeAll();


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

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

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

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

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


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

Item *set2 = ptr1-&gt;itemPtr;
Item *set1 = ptr2-&gt;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::unionSets (DisjointSet* s1, DisjointSet* s2) {
    Item *set1 = importSet(s1);
    Item *set2 = importSet(s2);

    set2-&gt;append(set1);
    delete set1;
}

void ListSet::Item::append (const Item* other) {
    //join the tail of the set to head of the other set
    tl-&gt;next = other-&gt;hd;
    tl = other-&gt;tl;
    for (node* cur = other-&gt;hd; cur; cur = cur-&gt;next) {
        cur-&gt;itemPtr = this;
    }
}

ListSet::node::node (const ValueType&amp; a) : val(a), next(0), itemPtr(0) 
{ }


/* Here's mutator code that allows values to be incrementally dropped as operations continue. 
Note that after "union(1,2); union(2,3); remove(2);", 
1 and 3 are still considered to be in the same set. 
*/

// Returns hd as a sign of life -- null if empty/dead.
ListSet::node* ListSet::Item::remove(node* old) {
    if (old == hd) {
        if (old == tl) {
            assert(! old-&gt;next);
            return 0;
        }
        assert(old-&gt;next);
        hd = old-&gt;next;
    } else {
        node* prev;
        for (prev = hd; prev-&gt;next != old; prev = prev-&gt;next) {
            assert(prev-&gt;next);
            ;
        }
        if (old == tl) {
            assert(! old-&gt;next);
            //
            tl = prev;
            prev-&gt;next = 0;
        } else {
            assert(old-&gt;next);
            prev-&gt;next = old-&gt;next;
        }
    }
    return hd;
}

ListSet::node::~node() {
    if (itemPtr) {
        if (! itemPtr-&gt;remove(this)) {
            // Don't leak an empty set.
            delete itemPtr;
        }
    }
}

void ListSet::remove(const ValueType&amp; a) {
    node* ptr = getNodeAddress(a);
    if (ptr) {
        setNodeAddress(a, 0);
        delete ptr;
    }
    // else error?
}

void ListSet::removeAll() {
    assert( 0 ); // TBD
    // This just needs to iterate over nodeAddress
    // and call delete on each remaining node*.
}


/* There's no reason to expose anything other than the original elements
   (raw numbers), the ListSet and the DisjointSets it returned. 
   So don't clutter the interface with Item*s disguised as longs, 
   node*s disguised (indistinguishably) as longs, or NodeAddress.
   A cleaner, safer API results:

int main () {

    ListSet a;
    ListSet::DisjointSet *s1, *s2, *s3, *s4;
    s1 = a.makeSet(13); 
    s2 = a.makeSet(25); 
    s3 = a.makeSet(45); 
    s4 = a.makeSet(65);

    /* If this really needs to work, either define a stream io operator 
       for our DisjointSet type or let it get dumped as a hex value. */
    cout&lt;&lt;s1&lt;&lt;' '&lt;&lt;s2&lt;&lt;' '&lt;&lt;s3&lt;&lt;' '&lt;&lt;s4 &lt;&lt;endl;

    cout&lt;&lt;"a.find(65): "&lt;&lt;a.find(65) &lt;&lt;endl;
    cout&lt;&lt;"a.find(45): "&lt;&lt;a.find(45) &lt;&lt;endl;
    cout&lt;&lt;"a.Union(65, 45) "&lt;&lt;endl;

    // The next line is a safer way to express a.unionSets(s3, s4);
    // which may crash if s3 or s4 had been previously merged/deleted, 
    // but it's also a little slower.
    a.unionSets(65, 45); 

    cout&lt;&lt;"a.find(65): "&lt;&lt;a.find(65) &lt;&lt;endl;
    cout&lt;&lt;"a.find(45): "&lt;&lt;a.find(45) &lt;&lt;endl;
}