title: Linked-list representation of disjoint sets - omission in Intro to Algorithms text?
body: <p>Having had success with <a href="https://stackoverflow.com/questions/3078157/is-a-node-in-a-tree-considered-its-own-ancestor">my last CLRS question,</a> here's another:</p>
  
  <p>In <a href="http://en.wikipedia.org/wiki/Introduction_to_Algorithms" rel="nofollow noreferrer">Introduction to Algorithms</a>, Second Edition, p. 501-502, a linked-list representation of disjoint sets is described, wherein each list member the following <strong>three</strong> fields are maintained:</p>
  
  <ul>
  <li>set member</li>
  <li>pointer to <code>next</code> object</li>
  <li>pointer back to first object (the set <code>representative</code>).</li>
  </ul>
  
  <p>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 <code>Union(x, y)</code> operation, so that one need not traverse all of the links in a larger set <code>x</code> in order to start appending the links of the smaller set <code>y</code> to it.</p>
  
  <p>However, to obtain a reference to the tail link, it would seem that each link object needs to maintain a <strong>fourth</strong> 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?</p>
  
  <p>Would you consider this an omission in the text?</p>