为什么是圆形？ 在单向链表中，为了访问链表的任何节点，我们从第一个节点开始遍历。如果我们位于列表中间的任何节点，则无法访问给定节点之前的节点。这个问题可以通过稍微改变单链表的结构来解决。在单向链表中，下一部分（指向下一个节点的指针）为 NULL。如果我们利用这个链接指向第一个节点，那么我们就可以到达前面的节点。
在我们这篇文章中，解释了使用单向链表在循环链表中实现和插入节点。
实现
为了实现一个循环单向链表，我们使用一个指向链表最后一个节点的外部指针。如果我们有一个指针 last 指向最后一个节点，那么 last -> next 将指向第一个节点。
指针last指向节点 Z 并且 last -> next 指向节点 P。
为什么我们采用指向最后一个节点而不是第一个节点的指针？ *
为了在开头插入一个节点，我们需要遍历整个链表。此外，为了在最后插入，必须遍历整个列表。如果我们使用指向最后一个节点的指针而不是开始*指针，那么在这两种情况下都不需要遍历整个列表。因此，无论列表的长度如何，在开头或结尾插入都需要恒定的时间。
插入
节点可以通过三种方式添加：
- 插入空列表
- 在列表开头插入
- 在列表末尾插入
- 在节点之间插入
在空列表中插入
最初，当列表为空时，最后一个指针将为 NULL。
插入后，T是最后一个节点，所以指针last指向节点T。而节点T是第一个也是最后一个节点，所以T指向自己。
将节点插入空列表的函数，
struct Node *addToEmpty(struct Node *last, int data) { if (last != NULL) return last; struct Node *temp = (struct Node*)malloc(sizeof(struct Node)); temp -> data = data; last = temp; temp -> next = last; return last; }
在列表的开头插入
要在列表的开头插入一个节点，请执行以下步骤： \
- 创建一个节点，例如 T。 \
- 使 T -> next = last -> next。 \
- 上一个 -> 下一个 = T。
在列表的开头插入节点的函数，
struct Node *addBegin(struct Node *last, int data) { if (last == NULL) return addToEmpty(last, data); struct Node *temp = (struct Node *)malloc(sizeof(struct Node)); temp -> data = data; temp -> next = last -> next; last -> next = temp; return last; }
在列表末尾插入
要在列表末尾插入一个节点，请执行以下步骤：
- 创建一个节点，例如 T。
- 使 T -> next = last -> next;
- last -> next = T。
- last = T。
在列表末尾插入节点的函数
struct Node *addEnd(struct Node *last, int data) { if (last == NULL) return addToEmpty(last, data); struct Node *temp = (struct Node *)malloc(sizeof(struct Node)); temp -> data = data; temp -> next = last -> next; last -> next = temp; last = temp; return last; }
在节点之间插入要在两个节点之间插入一个节点，请执行以下步骤：
- 创建一个节点，例如 T。
- 搜索需要在其后插入 T 的节点，例如该节点是 P。
- 使 T -> next = P -> next;
- P -> next = T. 假设需要在节点值为10后插入12，
在List末尾插入节点的函数，
struct Node *addAfter(struct Node *last, int data, int item) { if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; do { if (p ->data == item) { temp = (struct Node *)malloc(sizeof(struct Node)); temp -> data = data; temp -> next = p -> next; p -> next = temp; if (p == last) last = temp; return last; } p = p -> next; } while (p != last -> next); cout << item << " not present in the list." << endl; return last; }
下面是一个完整的程序，它使用上述所有方法来创建一个循环单向链表。
#include<bits/stdc++.h> using namespace std; struct Node { int data; struct Node *next; }; struct Node *addToEmpty(struct Node *last, int data) { if (last != NULL) return last; struct Node *temp = (struct Node*)malloc(sizeof(struct Node)); temp -> data = data; last = temp; last -> next = last; return last; } struct Node *addBegin(struct Node *last, int data) { if (last == NULL) return addToEmpty(last, data); struct Node *temp = (struct Node *)malloc(sizeof(struct Node)); temp -> data = data; temp -> next = last -> next; last -> next = temp; return last; } struct Node *addEnd(struct Node *last, int data) { if (last == NULL) return addToEmpty(last, data); struct Node *temp = (struct Node *)malloc(sizeof(struct Node)); temp -> data = data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } struct Node *addAfter(struct Node *last, int data, int item) { if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; do { if (p ->data == item) { temp = (struct Node *)malloc(sizeof(struct Node)); temp -> data = data; temp -> next = p -> next; p -> next = temp; if (p == last) last = temp; return last; } p = p -> next; } while(p != last -> next); cout << item << " not present in the list." << endl; return last; } void traverse(struct Node *last) { struct Node *p; if (last == NULL) { cout << "List is empty." << endl; return; } p = last -> next; do { cout << p -> data << " "; p = p -> next; } while(p != last->next); } int main() { struct Node *last = NULL; last = addToEmpty(last, 6); last = addBegin(last, 4); last = addBegin(last, 2); last = addEnd(last, 8); last = addEnd(last, 12); last = addAfter(last, 10, 8); traverse(last); return 0; }
输出：
2 4 6 8 10 12
