双向链表怎么插入程序

时间:2025-01-25 16:45:07 单机游戏

在双向链表中插入一个节点,需要遵循以下步骤:

找到插入位置:

确定新节点`s`应该插入到哪个节点`p`之前。

更新前驱节点的指针:

将新节点`s`的前驱指针`s->prior`指向节点`p`的前驱节点`p->prior`。

更新前驱节点的后继指针:

将节点`p`的前驱节点的后继指针`p->prior->next`指向新节点`s`。

更新后继节点的指针:

将新节点`s`的后继指针`s->next`指向节点`p`。

更新前驱节点的指针:

将节点`p`的前驱指针`p->prior`指向新节点`s`。

```c

include

include

// 定义双向链表节点结构体

typedef struct DuLNode {

int data; // 数据域

struct DuLNode *next; // 指向下一个节点的指针

struct DuLNode *prior; // 指向前一个节点的指针

} DuLNode;

// 在双向链表中插入节点

Status ListInsert_DuL(DuLinkList &L, int i, int e) {

if (!(p = GetElemP_DuL(L, i))) return ERROR; // 获取插入位置的节点

if (!(s = (DuLNode *)malloc(sizeof(DuLNode)))) return ERROR; // 分配新节点空间

s->data = e; // 设置新节点的数据

s->prior = p->prior; // 新节点的前驱指向原节点的前驱

p->prior->next = s; // 原节点的前驱指向新节点

s->next = p; // 新节点的后继指向原节点

p->prior = s; // 原节点的前驱指向新节点

return OK; // 插入成功

}

// 获取双向链表中第i个节点的指针

DuLNode* GetElemP_DuL(DuLinkList &L, int i) {

DuLNode *p = L.head;

for (int j = 0; j < i - 1 && p != NULL; j++) {

p = p->next;

}

return p;

}

// 初始化双向链表

void init_f(DuLinkList &L) {

L.head = L.tail = NULL;

L.len = 0;

}

// 打印双向链表

void print_list(DuLinkList &L) {

DuLNode *p = L.head;

while (p != NULL) {

printf("%d ", p->data);

p = p->next;

}

printf("\n");

}

int main() {

DuLinkList L;

init_f(L);

ListInsert_DuL(L, 1, 10);

ListInsert_DuL(L, 2, 20);

ListInsert_DuL(L, 3, 30);

print_list(L); // 输出: 10 20 30

return 0;

}

```

在这个示例中,我们定义了一个双向链表节点结构体`DuLNode`,并实现了在双向链表中插入节点的函数`ListInsert_DuL`。通过调用`ListInsert_DuL`函数,我们可以在双向链表的指定位置插入一个新节点。