迴圈鏈表

迴圈鏈表是鏈接的列表，其中第一個元素指向最後一個元素和最後一個元素指向第一個元素的鏈接變型。單向鏈表和雙向鏈表都可以做成作為迴圈鏈表。

單鏈表迴圈

雙向鏈表迴圈

按照如上所示的插圖，下麵是要考慮的重要問題。

• 最後一個鏈接的下一個點到列表的第一個鏈接單獨使用，在單/雙向鏈表兩種情況都可以使用。

• 在雙向鏈表中，第一個鏈接的前一個指向最後列表的最後一個鏈接。

基本操作

下麵是一個迴圈列表支持的重要操作。

• 插入 − 在列表的開頭插入的元素。

• 刪除 − 在列表的開頭刪除元素。

• 顯示 − 顯示列表。

長度操作

下麵的代碼演示了插入操作在基於單鏈表迴圈鏈表。

//insert link at the first location
void insertFirst(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data= data;

   if (isEmpty()) {
      head  = link;
      head->next = head;
   }
   else{
      //point it to old first node
      link->next = head;
      //point first to new first node
      head = link;
   }
}

刪除操作

下麵的代碼演示了在基於單鏈表迴圈鏈表的刪除操作。

//delete first item
struct node * deleteFirst(){
   //save reference to first link
   struct node *tempLink = head;

   if(head->next == head){
      head = NULL;
      return tempLink;
   }

   //mark next to first link as first
   head = head->next;

   //return the deleted link
   return tempLink;
}

顯示列表操作

下麵的代碼演示顯示迴圈鏈表列表操作。

//display the list
void printList(){
   struct node *ptr = head;
   printf("\n[ ");

   //start from the beginning
   if(head != NULL){
      while(ptr->next != ptr){
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
   printf(" ]");
}

要看到它在 C語言編程實現，請點擊 。