CODEWITHSUNDEEP
c++doubly-linked-list
Dave
Dave

Reputation: 1

double linked list head dereferenced is null

my head pointer is supposed to be null, because I don't want it to have any value when I make my linked list.

I know that you can't dereference something that is null, but I just want to point it's next node to something new. can someone explain how I could point the head node pointer?

void dlist::push_front(int value) {
    node *p = new node();
    node *tempH = head();
    tempH->next = p; //break
    /***********************************************************
    my head pointer is suposed to be null, because I don't want
    it to have any value when I make my linked list.

    I know that you can't dereference something that is null,
    but I just want to point it's next node to something new.
    can someone explane how I could point the head node pointer?
    ************************************************************/
    p->value = value;
    p->next = tempH->next;
    p->prev = tempH;
    p->next->prev = p;
    p->prev->next = p;
}

#pragma once
#include <ostream>

class dlist {
public:
    dlist() {}

    // Implement the destructor, to delete all the nodes
    //~dlist();

    struct node {
        int value;
        node* next;
        node* prev;
    };

    node* head() const { return _head; }
    node* tail() const { return _tail; }
    void push_front(int value);
private:
    node* _head = nullptr;
    node* _tail = nullptr;
};

Upvotes: 0

Views: 675

Answers (2)

Daniel Eisener
Daniel Eisener

Reputation: 333

The most practical solution here is to just use sentinel nodes for your head and tail. Or, just one sentinel node, that stands in for both. The sentinel nodes' elements can just be left uninitialised, you only need those nodes for the next and prev pointers they contain. To test if you've reached the end of the list, instead of testing for a null pointer, you test whether the pointer points to the sentinel node.

You can just use normal nodes as your sentinels if you expect your list elements to be small, or your lists to be very large. You waste a bit of memory on space for elements that won't be used, but it's probably not a big deal. If you really care about memory efficiency (say, you're writing a library), you can have something like this:

template<typename T> class dlist {

    struct node_header {
        node_header* next;
        node_header* prev;
    };

    struct node : public node_header {
        T element;
    };

    // Convert a node_header pointer to a node pointer
    node* node_from_header(node_header* p) {
        return static_cast<node*>(p);
    }
};

With this approach, your sentinel node is a node_header and all your actual, element-containing nodes are nodes. Your internal algorithms all work on node_headers, until you need to actually retrieve the element of a node, at which point you use node_from_header() to retrieve the full, element-containing node.

If you absolutely want to not use sentinel nodes, you'll have to rewrite your code to directly use the head pointer, rather than retrieving it through a function, and add special-case code for handling a null head pointer. It's not a pretty option.

Upvotes: 0

JGroven
JGroven

Reputation: 613

in your list constructor, simply set the head pointer to null.

dlist::dlist() {
  _head = nullptr;
}

Further, if you end up removing the LAST item in your list, you will need to also make _head = nullptr;

Be sure to check if the head is null before dereferencing.

 if(_head == nullptr){
     _head = new node(...);
 }

Your insert function will be responsible for assigning the first node to the head, in the event that you're adding to an uninitialized list.

If your list needs to be sorted, you will need to account for the head changing in the event that the new node should precede the head node.

Upvotes: 0

Related Questions