在给定节点之后在双向链表中插入一个节点
问题描述:
我有一个函数在双链表中的一个节点之后插入一个整数。它编译得很好。然而,当我用一个测试用例使用一个称为DLL的双向链表(它由2 4 6 8填充)并尝试调用该函数在4之后插入5时,没有任何事情发生在链表上,所以这是错误的。我只是不知道为什么。在给定节点之后在双向链表中插入一个节点
void DoublyLinkedList::insertAfter(const DListNode &p, int newobj) {
DListNode *newNode = new DListNode(newobj);
DListNode *node = header.next;
while(node != &p) {
node = node->next;
}
node = node->next;
node->next->prev = newNode;
}
答
您需要更新涉及的所有DListNode中的两个指针(next和prev)。
void DoublyLinkedList::insertAfter(const DListNode &p, int newobj) {
DListNode *newNode = new DListNode(newobj);
DListNode *node = header.next;
while(node != &p) {
node = node->next;
}
newNode->next = node->next;
newNode->prev = node;
// test to know if the insertion is in the middle or in the end.
if (node->next != NULL) // insert in the middle.
node->next->prev = newNode;
else // insert in the end.
lastNode = newNode;
node->next = newNode;
}
欲了解更多信息,请参阅https://en.wikipedia.org/wiki/Doubly_linked_list#Inserting_a_node。
答
2---> 4---> 6--->8
^ |^ |^ |
|____||____||____|
您分配一个newnode
NULL 5--->NULL
^ |
|______|
//Don't know how you are populating a newnodes next and prev but they should be NULL.
你的函数结束后,
2---> 4---> 6--->8
^ | |^ |
|____| ||____|
|
NULL<---5---->NULL
你的名单被打破。 您必须更新所有相关指针才能保持结构完整。
while()
{..
}
newNode->next = node->next;
newNode->prev = node;
node->next=newNode;
if(newNode->next!=NULL)
newNode->next->prev=newNode;
什么是“什么都没有发生”?你需要想出一些预期行为的测试用例,并检查你的逻辑是否正在对付它。 – Nim