迴圈連結列表

Harshit Jindal 2023年1月30日 2021年3月21日
  1. 為什麼是迴圈
  2. 迴圈連結串列的基本操作
迴圈連結列表

迴圈連結串列是比連結串列稍微複雜的資料結構。它是一個連結串列,其中所有節點都迴圈連線並形成鏈。最後一個節點沒有 NULL。而是儲存連結列表的 head 地址。本質上它是動態的,因為我們可以在任何地方插入元素。我們可以從連結串列上的任何點開始遍歷連結串列。我們可以從單鏈和雙鏈列表中建立一個迴圈連結串列。

在雙向連結列表中,tail 的下一個指標指向 head,而 head 的上一個指標指向 tail,並形成一個雙向迴圈連結列表。

為什麼是迴圈

  1. 對於實現多個資料結構(例如佇列,斐波那契堆)很有用。可以建立一個高效的佇列,而無需為 frontrear 使用兩個單獨的指標,並且僅插入一個指向 tail 的指標就足以插入或刪除,因為前導只是 tail 中的下一個指標。
  2. 它用於 CPU 排程中,以維護佇列中的作業,並分配其中一個時間執行,其餘時間均等待。它有助於快速迴圈所有作業,並公平分配每個作業的資源,直到所有作業都結束為止。
  3. 在多人遊戲中使用它來儲存下一個要玩的玩家。
  4. 我們可以在迴圈連結串列中的任何位置插入元素。我們可以從任何點開始遍歷。

迴圈連結串列的基本操作

我們可以在迴圈連結串列上執行以下操作。

  • 插入:在圓形連結串列中插入一個元素。
  • 刪除:刪除迴圈連結列表中存在的元素。
  • 遍歷:遍歷迴圈連結列表的內容。
  • 搜尋:檢查連結列表中是否存在元素。

我們將在後續文章中詳細介紹所有這些操作。

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Data Structure