資料結構 環狀單向鏈結串列

資料結構的環狀鏈結串列筆記。

環狀單向鏈結串列(Circular singly linked list)是把單向鏈結串列最後節點的指標欄位指到首節點而形成一個環，如此可從任一節點開始訪問到其他節點。

Circular Linked List

    ┌────┐
    │head│
    └─┬──┘
      │
      ▼
    ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
┌──►│ A  │next├───►│ B  │next├───►│ C  │next├───┐
│   └────┴────┘    └────┴────┘    └────┴────┘   │
│      node1          node2          node3      │
│                                               │
└───────────────────────────────────────────────┘

而空的環狀鏈結串列則首節點的指標欄位指向自己。

    ┌────┐
    │head│
    └─┬──┘
      │
      ▼
    ┌────┬────┐
┌──►│null│next├───┐
│   └────┴────┘   │
│      node1      │
│                 │
└─────────────────┘

而從首節點開始走訪節點的迴圈中，若目前節點的下一個節點等於首節點時走訪結束。

• 大話資料結構-程杰(ISBN 978-986-6072-11-6)