資料結構 (C#)：循環鏈結串列實作與約瑟夫問題應用

循環鏈結串列

繼承雙向鏈結串列，尾節點後繼指向頭節點。維護游標 m_CurrentNode 與索引 m_CurrentIndex，提供 GetNext()、GetPrevious()、GetCurrent() 循環遍歷。

程式碼

public class CircularlyLinkedList<T> : DoubleLinkedList<T> {
    private DoubleLinkedListNode<T> m_CurrentNode;
    private int m_CurrentIndex;
    public int CurrentIndex { get { return m_CurrentIndex; } }
    public CircularlyLinkedList() : base() { m_CurrentNode = m_Head.Next; m_CurrentIndex = 0; }
    public CircularlyLinkedList(T t) : base(t) { m_CurrentNode = m_Head.Next; m_CurrentIndex = 0; }
    public T GetCurrent() { /* 檢查空、回傳當前值 */ }
    public T GetNext() { /* 移動游標至下一節點，若為 null 則繞回頭節點 */ }
    public T GetPrevious() { /* 移動游標至前一節點，若為 null 或頭節點則繞回尾節點 */ }
}

應用：約瑟夫問題

N 人圍圈，從 1 報數到 M 出列，繼續報數至剩 1 人。

const int M = 9, N = 7;
CircularlyLinkedList<int> list = new CircularlyLinkedList<int>();
for (int i = 1; i < M; i++) list.Add(i);

int tempCounter = 0;
while (list.Count > 1) {
    tempCounter++;
    list.GetPrevious(); // 或 GetNext() 改變方向
    if (tempCounter == N) {
        tempCounter = 0;
        Console.WriteLine(list.GetCurrent() + " 出列！");
        list.RemoveAt(list.CurrentIndex);
    }
}
Console.WriteLine(list.GetNext() + " 為剩者");

執行結果 (GetPrevious)

2 出列！ 3 出列！ 1 出列！ 7 出列！ 4 出列！ 8 出列！ 6 出列！ 5 為剩者

執行結果 (GetNext)

7 出列！ 6 出列！ 8 出列！ 2 出列！ 5 出列！ 1 出列！ 3 出列！ 4 為剩者

方向不同導致出列順序與剩者不同。