FIND-SET operation:

• It is a data structure.

• It stores a set of elements which are partitioned into the number of non-overlapping subset.

Linked list representation:

• It stores data in sequence manner.

• It is group of nodes.

• The linked list is of three types.

• Singly linked list

• Its each node has one data and one address part.

• The address part holds the address of next node.

• Doubly linked list

• Its each node has one data and two address part.

• The first address part holds the address of previous node.

• The second address part holds the address of next node.

• Circular linked list

• The address of last node holds the address of first node.

Weighted-union heuristic:

• It stores the length of each list.

• The shorter list appended to longer list.

At the end of execution:

• There is a single set that contains all the elements.

• These elements are {x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16}

• xi is linked to xi+1 for each i.

• x1 is the representative of set.

• The pointer to x1 is returned by the both of two FIND-SET operations.

In the linked list representation of a set it is possible to keep just one pointer in each set object rather than two, while keeping the number of pointers in each list element to two only in cases when there is no constraint on the representative. It means that there is no condition as the representative must be the smallest or the largest element in the set.

Refer figure 21.2 in the textbook for the linked list representation of sets.

In this case, a representation of linked list with the difference that instead of two pointers in the set object, only one pointer used which references to the tail of the linked list.

The reference variable will be the representative of our linked list and all list elements will have two pointers. One of them is pointing to the upcoming element in the list and the other to the set object.

All the operations that are MAKE-SET, FIND-SET and UNION will take the same time as they take when there are two pointers in a set.

The proof for the fact is as:

MAKE-SET( x ):

This operation of set creates a new linked list containing the only object x in it and this will be done intime.

FIND-SET( x ):

This operation just returns the pointer from x back to its set object and return the object where set object points to that pointer to the tail of the list.

This operation also takestime.

UNION( x, y ):

Suppose x is contained in list A and y in B and the representative of is the representative of A.

Now, rather than appending B to the end of A, instead splice B into A right at the end of A. The list B is traversed to update pointers to the set object anyway, so we can just make the last element of B point to the tail of A.

The weighted union heuristic will apply here in the same manner. We will make the tail of smaller list point to the tail of longer list so that minimum updates need to be done to the internal nodes.

So, a list with n nodes and m MAKE-SET, UNION and FIND-SET operations will take no more thanwhich is similar as in case of two pointes one for head and other for tail of linked list.

Here time comes in UNION operation in which each objects pointer is updated at most times over all the UNION operations.

Hence professor Gomper’s doubt is true that is it is possible to implement a set in the form of linked list with only one pointer in every set object. And this will be possible in the same time as it takes when two pointers are implemented in a set.