双向链表：insert_before函数C++

Question

我正在创建一个双向链表。大部分代码都提供了完成insert_before和insert_after函数的说明。

struct Node { 
int data; // each node holds an integer data 
Node* previous; // pointer to the previous node 
Node* next; // pointer to the next node 
Node(int d=0, Node* prv=NULL, Node* nxt=NULL) : data(d), previous(prv), next(nxt) {} 
Node* get_previous() const { return previous; } 
Node* get_next() const { return next; } 
Node* insert_before(int d); // insert the int before this node 
          // return a pointer to the inserted node 
Node* insert_after(int d); // insert the int after this node 
          // return a pointer to the inserted node 
void delete_before(); // delete the node before this node 
void delete_after(); // delete the node after this node 
}; 

Node* Node::insert_before(int d) { 
    Node *newNode = new Node(d); 
    newNode->previous = this->previous; 
    newNode->next = this; 
    this->previous = newNode; 
    return newNode; 
} 
Node* Node::insert_after(int d) { 
Node *newNode = new Node(d); 
newNode->previous = this; 
newNode->next = this->next; 
this->next = newNode; 
return newNode; 
} 
void display_list(Node* header, Node* trailer) { 
    Node* p=header->get_next(); 
    while (p!=trailer) { 
    cout << p->data << ", "; 
    p=p->get_next(); 
    } 
    cout << endl; 
} 
int main() { 
cout << "Create a new list" << endl; 
Node *header = new Node(-1); 
Node *trailer = new Node(-2); 
trailer->previous = header; 
header->next = trailer; 
cout << "list: "; 
display_list(header,trailer); 
cout << endl; 

// Insert 10 nodes at back with value 10,20,30,..,100 
cout << "Insert 10 nodes at back with value 10,20,30,..,100" << endl; 
    for (int i=10;i<=100;i+=10) { 
    trailer->insert_before(i); 
    } 
cout << "list: "; 
display_list(header,trailer); 
cout << endl; 
return 0; 
} 

insert_after函数可以很好地工作，但由于某些原因，insert_before函数根本不起作用。

关于如何解决这个问题的任何想法？

Answer 1

我相信你可能忘记更改this->previous->nextinsert_before和this->next->previous的insert_after。

这导致您的列表在向前和向后遍历时跳过添加的节点。

例如：

Node node1 = Node(1); 
Node node2 = Node(2); 
node1.next = &node2; 
node2.previous = &head; 

// NULL <- node1 <-> node2 -> NULL 

node1.insert_after(3); 
// NULL <- node1 <-> node3 -> node2 -> NULL 
//    <---------- 
// node2 is pointing back to node1 instead of 3 

node2.insert_before(4); 
// NULL <- node1 <-> node3 node4 <-> node2 -> NULL 
//    <---------- 
//       ----------> 
// node 4 point back to node 1, while node3 points forward to node2 

Answer 2

是你的确保它不工作？我试过你的节点类，它工作得很好。 Insert_after将每个新元素引用添加到下一个元素，Insert_before做相反的事情，将每个新元素引用添加到前一个元素引用。