Node *new = create_node(elem);
Node *head_node = *p_head; //头结点
Node *tail = head_node; //tail指针指向头结点
while (tail->next != head_node) { //tail遍历至链表尾
tail = tail->next;
}
//尾插
new->next = tail->next;
tail->next = new;
}
1.5. 删除操作
删除的本质是“跳过”待删除的结点，所以我们要找到待删除结点的直接前驱结点，然后让其直接前驱结点的 next 指针指向其直接后继结点，以此来“跳过”待删除结点，最后保存其数据域，释放结点，即完成删除。
这里只演示头删法。
因为删除的是头结点的直接后继结点，所以我们不必再费力寻找待删除结点的直接前驱结点了。
void delete_from_head(Node **p_head, int *elem)
{
Node *head_node = *p_head; //头结点
if (head_node->next == head_node) {
printf(“空链表，无元素可删。n”);
return;
}
Node *first_node = head_node->next; //首结点：头结点的下一个结点
*elem = first_node->data; //保存被删除结点的数据
head_node->next = first_node->next; //删除结点
free(first_node); //释放
}
1.6. 遍历操作
我们可以一圈又一圈地循环遍历链表，下面是循环打印 20 次结点地代码：
void output_20(Node *head)
{
if (head->next == head) {
printf(“空链表。n”);
return;
}
Node *p = head->next;
for (int i = 0; i <= 20; i++) {
if (p != head) { //不打印头结点
printf("%d ", p->data);
}
p = p->next;
}
printf(“n”);
}
2. 双向链表
========
2.1. 结构
顾名思义，双向链表，就是有两个方向，一个指向前，一个指向后。这样我们就弥补了单链表的某个结点只能找到其直接后继的缺陷。如图所示：
2.2. 实现思路
为了实现能指前和指后的效果，只靠 next 指针肯定是不够的，所以我们需要再添加一个指针 —— prev，该指针指向某结点的直接前驱结点。
/双向链表的结点结构体/
typedef struct _Node {
int data; //数据域
struct _Node *prev; //指向直接前驱结点的指针
struct _Node *next; //指向直接后继结点的指针
} Node;
2.3. 空链表及初始化
双向链表的空链表如图所示：
要初始化一个这样的空链表，需要创造出头结点，然后将两个指针域置空即可：
Node *create_node(int elem)
{
Node *new = (Node *)malloc(sizeof(Node));
new->data = elem;
new->prev = NULL;
new->next = NULL;
return new;
}
void init(Node **p_head)
{
//创建头结点
Node *head_node = create_node(0);
//头指针指向头结点
*p_head = head_node;
}
2.4. 插入操作
这里只演示头插法，过程如下：
代码如下：
void insert_at_head(Node **p_head, int elem)
{
Node *new = create_node(elem);
Node *head_node = *p_head; //头结点
if (head_node->next != NULL) { //不为空链表
Node *first_node = head_node->next; //首结点：头结点的下一个结点
//首结点的prev指针指向new结点
first_node->prev = new;
//new结点的next指针指向首结点
ne 《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 w->next = first_node;
}
//new结点的prev指针指向头结点
new->prev = head_node;
//头结点的next指针指向new结点
head_node->next = new;
}
2.5. 删除操作
这里只演示头删法。下图是将一个有两个元素结点的双向链表头删为空链表的过程：
代码如下：
void delete_from_head(Node **p_head, int *elem)
{
Node *head_node = *p_head; //头结点
Node *first_node = head_node->next; //待删除的首结点：头结点的下一个结点
if (head_node->next == NULL) { //判空
printf(“空链表，无元素可删。n”);
return;
}
*elem = first_node->data; //保存数据
if (first_node->next != NULL) {
first_node->next->prev = first_node->prev;
}
first_node->prev->next = first_node->next;
free(first_node);
}
2.6. 遍历操作
