循環鏈表

循環鏈表是鏈接的列表,其中第一個元素指向最後一個元素和最後一個元素指向第一個元素的鏈接變型。單向鏈表和雙向鏈表都可以做成作爲循環鏈表。

單鏈表循環

Singly

雙向鏈表循環

Doubly

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

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

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

基本操作

下面是一個循環列表支持的重要操作。

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

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

  • 顯示 − 顯示列表。

長度操作

下面的代碼演示了插入操作在基於單鏈表循環鏈表。

//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語言編程實現,請點擊 。