双向链表的插入操作c++
时间: 2024-06-06 10:09:02 浏览: 10
好的,双向链表的插入操作可以分为三种情况:在链头插入、在链尾插入和在链中间插入。在插入之前,需要先找到插入位置的前一个节点和后一个节点,然后将新节点插入到两个节点之间即可。具体实现可以参考如下代码:
// 双向链表节点
struct Node {
int val;
Node* prev;
Node* next;
Node(int x) : val(x), prev(nullptr), next(nullptr) {}
};
// 双向链表插入操作
void insert(Node* head, int pos, int val) {
Node* cur = head;
for (int i = 0; i < pos && cur != nullptr; i++) {
cur = cur->next;
}
if (cur == nullptr) {
// 如果插入位置超出链表长度,直接在链尾插入
Node* tail = head;
while (tail->next != nullptr) {
tail = tail->next;
}
Node* newNode = new Node(val);
tail->next = newNode;
newNode->prev = tail;
} else {
Node* newNode = new Node(val);
if (cur->prev == nullptr) {
// 在链头插入
newNode->next = cur;
cur->prev = newNode;
head = newNode;
} else if (cur->next == nullptr) {
// 在链尾插入
cur->next = newNode;
newNode->prev = cur;
} else {
// 在链中间插入
newNode->prev = cur->prev;
newNode->next = cur;
cur->prev->next = newNode;
cur->prev = newNode;
}
}
}