Assigning doubly linked-list pointers in constructor

Question

I'm trying to create a few nodes for a doubly linked-list and print them out. So I create my dnode class:

template <typename T>
class dnode
{
    public:
        T nodeValue;
        dnode<T> *prev;
        dnode<T> *next;

        dnode() : prev(this), next(this) {}

        dnode(const T& item, dnode<T> *prevNode = NULL, dnode<T> *nextNode = NULL) :
            nodeValue(item), prev(prevNode), next(nextNode) {}

};

Then I have my writeList function:

template <typename T>
void writeDLinkedList(dnode<T>* header, const string& seperator = " ")
{
    dnode<T> *p = header->next;

    while (p != header)
    {
        cout << p->nodeValue << seperator;
        p = p->next;
    }

    cout << endl << endl;
}

In main, I create a header pointer and two nodes, using the constuctor to assign the previous and next nodes in the circular list:

dnode<int> *header, *one, *two;

header = new dnode<int>(0, two, one);
one = new dnode<int> (10, header, two);
two = new dnode<int> (25, one, header);

writeDLinkedList(header);

When I call writeDLinkedList, I get a segmentation fault. I was confused by this, so I eventually tried to output each node value individually to see if the pointers were working correctly. It turns out they weren't. Instead, I have to do this to get the print function working correctly:

header = new dnode<int>;

one = new dnode<int> (10);
two = new dnode<int> (25);
header->next = one;
one->next = two;
two->next = header;

writeDLinkedList(header);

I want to know why my constructor isn't working the way it should. Is it the initialization list?

prev and next should be initialized to NULL, not to this. Checks for valid nodes should then be updated to look for NULL while looping. — Remy Lebeau
– Remy Lebeau, Commented Apr 23, 2013 at 21:46

john · Accepted Answer · 2013-04-23 21:44:50Z

1

Your constructor is working. The problem is that you are using variables before they have been given values.

dnode<int> *header, *one, *two; 
// one and two have undefined values at this point

header = new dnode<int>(0, two, one);
// so undefined values get put into header->next and header->prev

In a doubly linked list you have pointer cycles, node A points to node B which points back to node A. By definition pointer cycles cannot be created in constructors only. Because either node A or node B must be created first. Which ever is created first cannot be created pointing at the other node since that other node doesn't exist yet.

Doubly linked lists are a little more complicated than you realised I think.

edited Apr 23, 2013 at 21:44

answered Apr 23, 2013 at 21:36

john

88.3k5 gold badges61 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Taylor Over a year ago

Yeah, I think I've underestimated them. Thanks for the concise answer.

Remy Lebeau · Accepted Answer · 2013-04-23 21:57:43Z

You are not managing the nodes correctly. Try this instead:

template <typename T>
class dnode
{
    public:
        T nodeValue;
        dnode<T> *prev;
        dnode<T> *next;

        dnode() : prev(NULL), next(NULL) {}

        dnode(const T& item, dnode<T> *prevNode = NULL) :
            nodeValue(item), prev(prevNode), next(NULL)
        {
            if (prev)
            {
                if (prev->next)
                    prev->next->prev = this;
                prev->next = this;
            }
        }

        ~dnode()
        {
            if (prev)
                prev->next = next;

            if (next)
                next->prev = prev;
        }
};

.

template <typename T>
void writeDLinkedList(dnode<T>* header, const string& seperator = " ")
{
    dnode<T> *p = header;

    while (p != NULL)
    {
        cout << p->nodeValue << seperator;
        p = p->next;
    }

    cout << endl << endl;
}

.

dnode<int> *header, *one, *two;

header = new dnode<int>(0);
one = new dnode<int> (10, header);
two = new dnode<int> (25, one);

writeDLinkedList(header);

praks411 · Accepted Answer · 2013-04-23 22:27:46Z

I think you are trying to create doubly circular list. You can first create individual nodes and then connect them. In doubly circular list after connecting two nodes, you have to connect the last node to the first to close circle. You may want to try something like. I've done it for int, but it can be easily put into a template.

#include<iostream>

class dnode
{

public:

    dnode(int a):prev(this), next(this), nodeValue(a)
     {}
    void connectNode(dnode *newNode)
     {
        if(newNode != NULL)
        {
            dnode*head = this->next;
            this->next = newNode;
            newNode->prev = this;
            newNode->next = head;
            head->prev = newNode;
        }
     }

    void writeDNode()
     {
     dnode *p = this->next;
        while(p != this)
         {
            std::cout<<"Element "<<p->nodeValue<<std::endl;
            p = p->next;
         }
     }
private:
    int nodeValue;
    dnode *prev;
    dnode *next;

 };


int main(int argc, char*argv[])
 {
    dnode* header = new dnode(-1);
    dnode *one = new dnode(23);
    dnode *two = new dnode(45);
    dnode *three = new dnode(67);
    header->connectNode(one);
    one->connectNode(two);
    two->connectNode(three);
    header->writeDNode();
    std::getchar();



 }

Collectives™ on Stack Overflow

Assigning doubly linked-list pointers in constructor

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related