Disjoint-set Linked Lists
A simple approach to creating a disjoint-set data structure is to create a linked list for each set. The element at the head of each list is chosen as its representative.
MakeSet creates a list of one element. Union appends the two lists, a constant-time operation. The drawback of this implementation is that Find requires Ω(n) or linear time to traverse the list backwards from a given element to the head of the list.
This can be avoided by including in each linked list node a pointer to the head of the list; then Find takes constant time, since this pointer refers directly to the set representative. However, Union now has to update each element of the list being appended to make it point to the head of the new combined list, requiring Ω(n) time.
When the length of each list is tracked, the required time can be improved by always appending the smaller list to the longer. Using this weighted-union heuristic, a sequence of m MakeSet, Union, and Find operations on n elements requires O(m + nlog n) time. For asymptotically faster operations, a different data structure is needed.
Read more about this topic: Disjoint-set Data Structure
Famous quotes containing the words linked and/or lists:
“In the dominant Western religious system, the love of God is essentially the same as the belief in God, in God’s existence, God’s justice, God’s love. The love of God is essentially a thought experience. In the Eastern religions and in mysticism, the love of God is an intense feeling experience of oneness, inseparably linked with the expression of this love in every act of living.”
—Erich Fromm (1900–1980)
“Behold then Septimus Dodge returning to Dodge-town victorious. Not crowned with laurel, it is true, but wreathed in lists of things he has seen and sucked dry. Seen and sucked dry, you know: Venus de Milo, the Rhine or the Coloseum: swallowed like so many clams, and left the shells.”
—D.H. (David Herbert)