双循环链表.新节点未插入.c++

Question

所以这个新节点应该插入到最后一个节点之后。我不明白为什么没有发生。注意:在调用这个函数之前，列表有多个元素(大约5个)，所以到目前为止，它只需要在这种情况下工作。最后一个节点应该指向顶部节点，top->prev指针应该指向最后一个节点。我哪里做错了?顺便说一下，我假设这是错误的，因为当调用print函数

时，最后一个节点永远不会打印

void CircularDLL::insertAfterLast (int id, string name, string email, int age)
{
 Node* N=new Node;
 N->stId=id;
 N->stName=name;
 N->stEmail=email;
 N->stAge=age;
 Node* Q=top;
 while(Q->next!=top)//get to the last node
 {
  Q=Q->next;
 }
 cout<<"Q next is top now"<<endl;
 Q->next=N;
 N->prev=Q;
 N->next=top;
 top->prev=N;
}

Answer 1

这段代码有几个问题。首先，如果你要经常做"insertAfterLast"，你应该使用"top->prev"在常量时间内获得指向最后一个元素的指针;否则，构建一个列表将需要二次(O(n^2))时间。其次，在任何实际项目中，从头开始实现循环链表几乎肯定是一个坏主意——相反，您希望坚持使用成熟的兼容stl的容器，如std::deque或Boost的circular_buffer。

假设您确实想这样做，并且您不关心空列表，那么上面的函数似乎已经完全正确。最有可能的问题是，在开始之前的初始列表是不正确的，或者更有可能的是，当您遍历列表以在最后打印它时，您跳过了最后一个元素。遍历循环链表的正确方法是这样的(改编自维基百科):

Node* Q = top;
do {
    cout << Q->stId << endl;
    Q = Q->next;
} while (Q != top);