CODEWITHSUNDEEP
c++linked-listdoubly-linked-listcircular-list
Tyler Pfaff
Tyler Pfaff

Reputation: 5032

Doubly-Circular Linked list. New node not inserting. C++

So this new node is supposed to be inserted after the last node. I can't figure out why that is not happening. Note: The list has multiple elements before this function is called (approx 5) so as of now it only has to work for that case. The last node should point to the top node and the top->prev pointer should point to the last node. Where have I gone wrong? I'm assuming that its wrong by the way because the last node never prints when the print function is called

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;

}

Upvotes: 1

Views: 1692

Answers (1)

Chiara Coetzee
Chiara Coetzee

Reputation: 4429

This code has a few issues. First, if you're going to do "insertAfterLast" frequently, you should use "top->prev" to get a pointer to the last element in constant time; otherwise building a list will require quadratic (O(n^2)) time. Second, in any real project implementing a circular linked list from scratch is almost certainly a bad idea - instead you want to stick with a mature STL-compliant container like std::deque or Boost's circular_buffer.

Assuming you really do want to do this, and you're not concerned about empty lists, your function above appears to already be completely correct. Most likely the problem is either that your initial list before you begin is malformed, or more likely, that when you iterate over the list to print it out at the end, you're skipping the last element. The right way to iterate over a circularly linked list is like this (adapted from Wikipedia):

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

Upvotes: 3

Related Questions