在给定节点之后插入双向链表中的节点

Question

我有一个函数可以在双向链表的节点后插入一个整数。它编译得很好。但是，当我运行它与一个测试用例一起使用一个名为 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;   
}

Answer 1

您需要更新所有涉及的 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。

Answer 2

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;

在给定节点之后插入双向链表中的节点

Insert a node in a doubly linked list after a given node

c++

doubly-linked-list