Linked-list representation of disjoint sets - omission in Intro to Algorithms text?

Having had success with my last CLRS question, here's another:

In Introduction to Algorithms, Se开发者_开发知识库cond Edition, p. 501-502, a linked-list representation of disjoint sets is described, wherein each list member the following three fields are maintained:

• set member
• pointer to next object
• pointer back to first object (the set representative).

Although linked lists could be implemented by using only a single "Link" object type, the textbook shows an auxiliary "Linked List" object that contains a pointer to the "head" link and the "tail" link. Having a pointer to the "tail" facilitates the Union(x, y) operation, so that one need not traverse all of the links in a larger set x in order to start appending the links of the smaller set y to it.

However, to obtain a reference to the tail link, it would seem that each link object needs to maintain a fourth field: a reference to the Linked List auxiliary object itself. In that case, why not drop the Linked List object entirely and use that fourth field to point directly to the tail?

Would you consider this an omission in the text?

I just opened the text and the textbook description seems fine to me.

From what I understand the data-structure is something like:

struct Set {
    LinkedListObject * head;
    LinkedListObject * tail;
};

struct LinkedListObject {
    Value set_member;
    Set *representative;
    LinkedListObject * next;
};

The textbook does not talk of any "auxillary" linked list structure in the book I have (second edition). Can you post the relevant paragraph?

Doing a Union would be something like:

// No error checks.
Set * Union(Set *x, Set *y) {

    x->tail->next = y->head;    
    x->tail = y->tail;

    LinkedListObject *tmp = y->head;

    while (tmp) {

        tmp->representative = x;
        tmp = tmp->next;

    }
    return x;
}

why not drop the Linked List object entirely and use that fourth field to point directly to the tail?

An insight can be taken from path compression. There all the elements are supposed to point to head of list. If it doesn't happen then the find-set operation does that (by changing p[x] and returning that). You talk similarly of tail. So if such function is implemented only then can we use that.