Doubly linked list class

Question

I am trying to make a double linked list. Function push(int x) should add a node to the list and make the correct link. I use:

class Node {
public:
    int value;
    Node* next;
    Node* prev;

public:
    Node() {}
    void set_value(int x) { value = x; }
    void set_next(Node* x) { next = x; }
    void set_prev(Node* x) { prev = x; }

    Node* get_next() { return next; }
    Node* get_prev() { return prev; }        
};

class deque {
    public:
        Node* head;
        Node* tail;
    public:
        deque() { head = NULL; tail = NULL; }
        void push(int x) {
             Node* n = new Node();
             n->set_value(x);
             n->set_next(NULL);
             n->set_prev(NULL);

             Node* t = head; //link to the next node           
             if (t == NULL) {
                 head = n; 
             } else {
                 while (t->get_next() != NULL) {
                       t = t->get_next();
                 }
                 t->set_next(n);
             }
        }     
};

As I have tested the part that connects a node to the next one works fine but I am having some troubles connecting the node to the previous one. One that comes in mind is a variation of the first one:

Node* t = tail;             
if (t == NULL) {
    tail = n; 
} else {
    while (t->get_prev() != NULL) {
          t = t->get_prev();
    }
    t->set_prev(n);
}

But by using this, the tail node is always the current n node if only the node n is the one and only node in the queue... What should I do? thanks a lot

Why not simply using something like n->set_prev(tail); tail->set_next(n); tail = n; with proper NULL-pointer verification? — Angivare
– Angivare, Commented Jan 25, 2015 at 12:03

BartoszKP · Accepted Answer · 2015-01-25 12:18:18Z

4

Drawing always helps with such data structures. What you have currently:

enter image description here

You correctly set t's next with: t->set_next(n);. What is missing is the arrow underneath it, and it's: n->set_prev(t).

In general, when dealing with doubly-linked lists, a call to set_next should always (most of the time) be accompanied by a call to set_prev on set_next's argument. It's because of the doubly-linked list's property:

x->next == y implies y->prev == x, and y->prev == x implies x->next == y.

answered Jan 25, 2015 at 12:18

BartoszKP

36k15 gold badges109 silver badges135 bronze badges

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

Collectives™ on Stack Overflow

Doubly linked list class

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related