数据结构教程5：循环单链接列表，并附带C语言中的实现说明

在“链表”的第一章中，我们了解了“单链表”。在本章中，我们将学习循环单链表。

唯一的增加是，最后一个节点的下一个指针将指向头节点，因此使其成为循环链表。

下面是它的表示：

对于单个节点

对于多个节点

1.最后插入

要在最后插入节点，我们执行以下步骤：

1.取一个新节点并复制数据。
2.如果没有元素，则此节点将是头节点，并使下一个指针指向同一节点
3.否则，遍历到节点的末尾，然后将最后一个节点的下一个指针链接到新节点，并将新节点的下一个指针链接到头节点。

2.最后删除

要最后删除节点，我们执行以下步骤：
1.如果只有1个节点，则删除该节点。
2.否则遍历列表的末尾，使上一个节点的“下一个”指针指向头节点。
3.释放临时节点。

3.显示

要显示所有元素，请使用临时指针，以免松动头节点。
然后遍历列表，直到列表末尾。

循环单链表在C中的实现

#include<stdio.h>
#include<stdlib.h>


struct Node
{
	int data;
	struct Node *next;
	
};

struct Node *head=NULL;


void insert_end(int data)
{
	//create a temp node, allocate memory and copy the data.
   struct Node *temp;
   temp = (struct Node*)malloc(sizeof(struct Node));
   temp -> data = data;

   //if this is the first node,
   if(head == NULL)
   {
   	//then assign the temp node as head and
   	// point the 
      head = temp;
      temp -> next = head;
   }
   else
   {
   	  //take a current node, traverse till the end of the list
      struct Node *current = head;
      while(current -> next != head)
         current = current -> next;

     //assign the next of current node to temp node
     //assign the next of temp node to head
     //thus making circular linked list
      current -> next = temp;
      temp -> next = head;
   }
}


// delete TAIL node of a circular singly linked list
void delete_tail()
{
   if(head == NULL)
      printf("List is empty \n");
   else
   {
      struct Node *temp1 = head;
      struct Node *temp2 = head;
      if(temp1 -> next == head)
      {
         head = NULL;
         free(temp1);
      }
      else
      {
        //as this is a circular list,
        // hence we check if the next pointer points to the head node
         while(temp1 -> next != head)
         {
            temp2 = temp1;
            temp1 = temp1 -> next;
         }
         temp2 -> next = head;
         free(temp1);
      }
      printf("\nElement deleted");
   }
}

void display()
{
   if(head == NULL)
      printf("\n Empty List");
   else
   {
   	 	struct Node *temp = head;
   	 	printf("Printing values\n");
       	while(temp -> next != head)  
        {  
          
            printf("%d\n", temp -> data);  
            temp = temp -> next;  
        }  
        printf("%d\n", temp -> data);  
    }  
}

int main()
{
	int value;
	int logout = 0;
	while(logout == 0)
	{
		printf("Choose any option:\n\n");
		printf("1)Insert end\n");
		printf("2)Delete tail\n");
		printf("3)Display List\n");
		printf("4)Exit\n");

		int choice;
		scanf("%d",&choice);
		switch(choice)
		{
			case 1:
				printf("Enter value:\n");
				scanf("%d",&value);
				insert_end(value);
			break;

			case 2:
				delete_tail();
			break;	

			case 3:
				display();
			break;

			case 4:
				logout = 1;
			break;
		}
	}
}

输出：

Choose any option:

1)Insert end
2)Delete tail
3)Display List
4)Exit
1
Enter value:
1
Choose any option:

1)Insert end
2)Delete tail
3)Display List
4)Exit
1
Enter value:
2
Choose any option:

1)Insert end
2)Delete tail
3)Display List
4)Exit
1
Enter value:
3
Choose any option:

1)Insert end
2)Delete tail
3)Display List
4)Exit
1
Enter value:
4
Choose any option:

1)Insert end
2)Delete tail
3)Display List
4)Exit
3
Printing values
1
2
3
4
Choose any option:

1)Insert end
2)Delete tail
3)Display List
4)Exit
2

Element deletedChoose any option:

1)Insert end
2)Delete tail
3)Display List
4)Exit
3
Printing values
1
2
3
Choose any option:

1)Insert end
2)Delete tail
3)Display List
4)Exit
4

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：