迴圈連結串列

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

單連結串列迴圈

雙向連結串列迴圈

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

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

• 在雙向連結串列中，第一個連結的前一個指向最後列表的最後一個連結。

基本操作

下面是一個迴圈列表支援的重要操作。

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

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

• 顯示 ? 顯示列表。

長度操作

下面的程式碼演示了插入操作在基於單連結串列迴圈連結串列。

//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語言程式設計實現，請點選 。