【数据结构与算法】双向链表中指定值前后插入新元素的算法 C++实现（双向链表+循环）

分别在带头结点的双链表中的第一个值为x的结点之前、之后插入元素值为y的结点，分别编写各自的算法。

---

思路

insertBefore函数用于在双链表中指定值的结点之前插入新的元素值。它通过遍历双链表找到对应的结点，然后调用listInsert函数完成插入操作。首先获取双链表的第一个结点，然后使用循环遍历整个双链表，直到找到值为x的结点或遍历结束。如果找到了值为x的结点，就调用listInsert函数，在该位置插入新的元素值y。如果未找到值为x的结点，则返回错误。

insertAfter函数的操作类似，不同之处在于在指定值的结点之后插入新的元素值。它也是通过遍历双链表找到对应的结点，然后调用listInsert函数完成插入操作。与insertBefore函数类似，它首先获取双链表的第一个结点，然后使用循环遍历整个双链表，直到找到值为x的结点或遍历结束。如果找到了值为x的结点，就调用listInsert函数，在该位置的后面插入新的元素值y。如果未找到值为x的结点，则返回错误。

时间复杂度都为O(n)，因为在最坏情况下，需要遍历整个双链表来找到指定的结点。空间复杂度取决于双链表的长度，为O(n)。

---

代码

#include <algorithm>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using Status = int;
using ElemType = int;const int N = 1e6 + 7;
const int TRUE = 1;
const int FALSE = 0;
const int OK = 1;
const int ERROR = 0;
const int INFEASIBLE = -1;
const int OVERFLOW = -2;int n;
ElemType a[N];struct ListNode {ElemType data;ListNode *prior, *next;
};
using LinkList = ListNode *;Status initList(LinkList &L) {L = (ListNode *)malloc(sizeof(ListNode));if (!L) {return ERROR;}L->prior = NULL;L->next = NULL;return OK;
}Status listInsert(LinkList &L, int pos, ElemType e) {ListNode *p = L;for (int i = 0; p && i < pos; i++) {p = p->next;}if (!p) {return ERROR;}ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));if (!newNode) {return ERROR;}newNode->data = e;newNode->prior = p;newNode->next = p->next;p->next = newNode;if (newNode->next) {newNode->next->prior = newNode;}return OK;
}ElemType getElem(LinkList L, int pos) {ListNode *p = L->next;for (int i = 0; p && i < pos; i++) {p = p->next;}if (!p) {return NULL;}return p->data;
}Status insertBefore(LinkList &L, int x, int y) {ListNode *p = L->next;int i = 0;while (p && p->data != x) {p = p->next;i++;}if (!p) {return ERROR;}return listInsert(L, i, y);
}Status insertAfter(LinkList &L, int x, int y) {ListNode *p = L->next;int i = 0;while (p && p->data != x) {p = p->next;i++;}if (!p) {return ERROR;}return listInsert(L, i + 1, y);
}int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}LinkList L;initList(L);for (int i = 0; i < n; i++) {listInsert(L, i, a[i]);}for (int i = 0; i < n; i++) {cout << getElem(L, i) << " ";}cout << "\n";n += insertBefore(L, 1, 2);n += insertBefore(L, 3, 4);for (int i = 0; i < n; i++) {cout << getElem(L, i) << " ";}cout << "\n";n += insertAfter(L, 7, 6);n += insertAfter(L, 9, 8);for (int i = 0; i < n; i++) {cout << getElem(L, i) << " ";}cout << "\n";return 0;
}