以下是一个用C语言实现的双向链表（Doubly Linked List）插入操作的代码。该代码从尾部遍历找到第一个值为x的节点，并在其前插入新节点p，或者在未找到时将其插入链表末尾。
#include <stdio.h>
#include <stdlib.h>// 定义双向链表节点结构
typedef struct DoublyListNode {int val;struct DoublyListNode *prev;struct DoublyListNode *next;
} DoublyListNode;// 创建新节点
DoublyListNode* createNode(int val) {DoublyListNode *newNode = (DoublyListNode*)malloc(sizeof(DoublyListNode));newNode->val = val;newNode->prev = NULL;newNode->next = NULL;return newNode;
}// 在双向链表中插入新节点
DoublyListNode* insertBeforeXOrAppend(DoublyListNode *head, int x, int pVal) {if (head == NULL) {// 如果链表为空，直接创建新节点并返回return createNode(pVal);}DoublyListNode *curr = head;// 从头部开始遍历直到尾部while (curr->next != NULL) {curr = curr->next;}// 从尾部开始向前遍历找到第一个值为x的节点while (curr != NULL && curr->val != x) {curr = curr->prev;}// 如果找到了值为x的节点if (curr != NULL) {DoublyListNode *newNode = createNode(pVal);newNode->next = curr->next;newNode->prev = curr;if (curr->next != NULL) {curr->next->prev = newNode;}curr->next = newNode;} else {// 如果没有找到值为x的节点，则插入到末尾DoublyListNode *newNode = createNode(pVal);newNode->prev = curr; // curr此时为链表的最后一个节点或NULL（当链表为空时，但这种情况已在开头处理）if (curr != NULL) {curr->next = newNode;}// 如果链表原本为空，则newNode既是头节点也是尾节点，无需额外设置head// 否则，head不变，因为新节点是插入到末尾的，不影响头节点}// 注意：此函数不改变头节点的地址，因此无需返回新的头节点（除非链表原本为空）// 但为了保持接口的一致性，这里仍然返回头节点（尽管它可能没变）return head; // 在这个特定实现中，头节点要么不变，要么在函数外部已经处理（如链表为空时）
}// 打印双向链表
void printList(DoublyListNode *head) {DoublyListNode *curr = head;while (curr != NULL) {printf("%d ", curr->val);curr = curr->next;}printf("\n");
}// 释放双向链表内存
void freeList(DoublyListNode *head) {DoublyListNode *curr = head;while (curr != NULL) {DoublyListNode *next = curr->next;free(curr);curr = next;}
}int main() {// 创建双向链表 1 <-> 2 <-> 3 <-> 4DoublyListNode *head = createNode(1);head->next = createNode(2);head->next->prev = head;head->next->next = createNode(3);head->next->next->prev = head->next;head->next->next->next = createNode(4);head->next->next->next->prev = head->next->next;int x = 3;int pVal = 99;// 插入新节点insertBeforeXOrAppend(head, x, pVal);// 打印双向链表printList(head);// 释放双向链表内存freeList(head);return 0;
}
注意：
-
上述代码中的insertBeforeXOrAppend函数实际上不需要返回新的头节点地址，因为插入操作要么在链表末尾进行（不改变头节点），要么在链表中间进行（同样不改变头节点）。但是，为了保持函数接口的一致性（比如，如果以后需要修改这个函数以处理链表为空时的特殊情况，并返回新的头节点），这里仍然返回了头节点。在实际应用中，如果确定头节点不会改变，可以省略返回值。
-
在main函数中，我们创建了一个简单的双向链表，并调用了insertBeforeXOrAppend函数来插入新节点。然后，我们打印链表并释放其内存。
带头链表：在链表的首部增加一个不存储有效数据的头节点。头节点的作用主要是简化链表的操作，特别是在处理空表时，无论表是否为空，头指针都指向头节点，从而使得空表和非空表的操作一致。
带头单向非循环链表：结构简单，但一般不会单独用来存储数据，而是作为其他数据结构的子结构，如哈希桶、图的邻接表等。
带头双向循环链表：结构最复杂，但一般用在单独存储数据的场景。实际中使用的链表数据结构，很多都是带头双向循环链表。虽然结构复杂，但使用代码实现后会发现，这种结构能带来很多优势。
