Implementacja listowa
Oto prosta implementacja struktury danych dla zbiorów rozłącznych: Każdy zbiór jest reprezentowany jako lista swoich elementów. Reprezentantem zbioru jest pierwszy element na liście. Każdy element ma dodatkowo bezpośredni wskaźnik do reprezentanta, dzięki czemu koszt operacji Find to O(1). Operacja MakeSet jest również bardzo prosta i polega na utworzeniu jednoelementowej listy.
Bardziej kłopotliwa jest operacja Union: wprawdzie koszt połączenia dwóch list jest stały, ale trzeba jeszcze we wszystkich elementach listy, która jest dołączana na koniec drugiej, uaktualnić wskaźnik do reprezentanta, co zajmuje czas liniowy względem jej długości. Prosta sztuczka zwana heurystyką łączenia z wyważaniem pozwala zmniejszyć koszt operacji Union (w sensie zamortyzowanym). Polega ona na tym, że podczas operacji Union zawsze dołączamy krótszą listę na koniec dłuższej (wymaga to przechowywania wraz z listą dodatkowego atrybutu "rozmiar"). Jako ćwiczenie pozostawiamy dowód faktu, że teraz koszt wykonania m operacji MakeSet, Find i Union, spośród których n to MakeSet, wynosi \( O(m+n\log n) \).