Listy cykliczne powiązane pojedyńczo mają łącze ostatniego elementu skierowane na pierwszy element. Wydaje się, że ta lista nie powinna pozostawać pusta.
[Sedgewick s. 85] Załóżmy, że N osób postanowiło wybrać spośród siebie przywódcę w następujący sposób: wszyscy stają w kole, a następnie za pomocą m-sylabowej wyliczanki eliminują za każdym razem m-tą osobę z koła. Problem polega na tym, by wyznaczyć z góry, która osoba pozostanie jako jedyna w kole.
Implementacja korzysta z listy cyklicznej i argumentów wiersza poleceń. W problemie Josephusa lista umożliwia szybkie usuwanie elementów z sekwencji. W sicie Eratostenesa wydajność algorytmu zależy od użycia tablic, ponieważ tablice zapewniają szybkie odnajdywanie elementów o znanym numerze.
import sys
class Node:
"""Klasa reprezentująca węzeł listy jednokierunkowej."""
def __init__(self, data=None, next=None):
self.data = data
self.next = next
def __str__(self):
return str(self.data) # bardzo ogólnie
N = int(sys.argv[1])
m = int(sys.argv[2])
# Pierwszy węzeł na liście.
head = Node(1)
head.next = head # lista cykliczna
# Wstawiamy następne liczby za head.
node = head
for i in range(2, N+1):
node.next = Node(i, head)
node = node.next
# Wyrzucamy co m-ty element.
while node != node.next:
for i in range(m-1):
node = node.next
node.next = node.next.next # wyrzucam node.next
print("zostaje {}".format(node))
| head | head | head | | | | | | | | | o | o | o | | +---+-+ | +---+-+ +---+-+ | +---+-+ +---+-+ +---+-+ | | | 1 | +--+ | | 1 | +--o| 2 | +--+ | | 1 | +--o| 2 | +--o| 3 | +--+ | | +---+-+ | | +---+-+ +---+-+ | | +---+-+ +---+-+ +---+-+ | | | o | | o | | o | | | | | | | | | | | | | +------+ | +----------------+ | +--------------------------+ |
Podczas budowania listy program używa dwa razy więcej przypisań niż potrzeba, ponieważ po wstawieniu każdego węzła zapewnia utrzymanie listy cyklicznej. Można zmodyfikować program tak, aby budował listę cykliczną bez dodatkowej pracy.