head->next is not null

Question

I can't figure out why my one item list "_head->next" is not being set to null (nullptr). Could I be confusing my tail and head pointers? This is for a doubly linked list. Most other pointers work, but this error/bug throws a seg fault when walking through the list.

#pragma once
class dlist {
  public:
    dlist() { }

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


  node* head() const { return _head; }
  node* tail() const { return _tail; }


void insert(node* prev, int value){
     //if empty
     if(prev == nullptr)
       {
       //create node/prepare to insert into head ptr
        _head = new node{value, _head, nullptr};

        if(_tail == nullptr)
        {
         _tail = _head;
         _tail->next = nullptr;
        }
        //set head
        if(_head->next != nullptr)
          {
           _head->prev = _head;

           _head->next = nullptr;
           //_head->next->next = nullptr;
           //above doesn't work  
          }
       }
 //if not empty
     else
       {
       //create and set new node
        node* node1 = new node{value, prev->next, nullptr};
        prev->next = node1;

        //check if null, to make sure inserting after a filled "space"
         if(node1->next != nullptr)
           {
            node1->next->prev = node1;

            //set to end or tail
            if(prev == _tail)
              {
               _tail = node1;
               _tail->next = nullptr;
              }
           }
       }
  }


 private:
   node* _head = nullptr;
   node* _tail = nullptr;

};

Answer 1

I stronlgy recommend not using C-style pointers in C++ anymore. C++ has smart pointers that do all the memory management for you.

Change your node to this:

class node {
    node(int value) : value{value} {}
    int value;
    std::shared_ptr<node> next;
    std::weak_ptr<node> prev;
};

The shared_ptr will delete the object it holds as soon as no copy/instance of itself exist anymore (it uses a simple counter). The weak_ptr makes sure that you don't have circular references, which would mean your nodes never get deleted.

Also in your dlist class change the members accordingly:

std::shared_ptr<node> _head;
std::weak_ptr<node> _tail;

Then change your getters to this:

std::shared_ptr<node> head() const { return _head; }
std::shared_ptr<node> tail() const { return _tail.lock(); }

weak_ptr::lock() will increase the shared_ptr counter it belongs to and return a new shared_ptr, that then can be accessed without risk of losing the object. If the object was deleted already, it will return en empty shared_ptr.

Then change your insert method like this:

void insert (int value)
{
    std::shared_ptr<node> newnode = std::make_shared<node>(value);

    if (_tail) {
        newnode->prev = _tail;
        _tail->next = newnode;
        _tail = newnode;
    }
    else {
        _head = newnode;
        _tail = newnode;
    }
}

This will set _head and _tail to the newnode if the list is empty, or add it to the end of your list otherwise.

Read more about shared_ptr and weak_ptr here.

//Edit: If you ever want to clear your list, you can simply do _head = nullptr;. This will cause the shared_ptr to decrease it's reference counter and delete the node it is holding (if the counter goes to 0), thus deleting the shared_ptr<node> next; in that node and so on. _tail will automatically be empty as soon as the shared_ptr it belongs to is deconstructed. To be absolutely sure that your dlist class is in a clean empty state, you should still call _tail = nullptr;, because some other part of your code can hold a shared_ptr to any of the nodes, thus keeping _tail alive in your list class unless you explicitly clear it.

Answer 2

This is kind of a hard one to get your head around given the initial code you posted and the ambiguity in your use of prev as a parameter to insert.

To begin, insert is a member function of dlist and has direct access to both _head and _tail. You do not need a node* parameter for insert because your only concern with the linked list will be checking whether _head is nullptr and allocating/assigning value for _head, or you will iterate until your iter->next is nullptr and add the allocated node as iter->next setting _tail to the newly allocated node.

Most of your existing code, frankly, just left me scratching my head. Also, the default for class is private, so generally you only need to designate public members.

Putting the logic together, you could do something like the following:

class dlist {

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

    node* _head = nullptr;
    node* _tail = nullptr;

  public:
    dlist() { }

    node* head() const { return _head; }
    node* tail() const { return _tail; }

    void insert (int value)
    {
        node *newnode = new node {value, nullptr, nullptr};

        if (_head == nullptr)
            _head = newnode;
        else {
            node* iter = _head;
            for (; iter->next; iter = iter->next) {}
            newnode->prev = iter;
            _tail = iter->next = newnode;
        }
    }
};

When you allocate memory in a class, in order to prevent leaking memory like a sieve, you need to also declare a destructor that will free the memory you have allocated when an instance of the class goes out of scope. Nothing fancy is needed, just iterate from _head to the end of the list and delete nodes as you go.

(note: you must not delete your reference to the current node until you have saved a reference to the next node, so use a separate, aptly named victim node to perform the delete)

You could do something like:

    ~dlist() {
        node* iter = _head;
        while (iter) {
            node* victim = iter;
            iter = iter->next;
            delete victim;
        }
    }

Putting it altogether and adding a couple of functions to print and reverse or rprint the list, you could do something like the following:

#include <iostream>

using namespace std;

class dlist {

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

    node* _head = nullptr;
    node* _tail = nullptr;

  public:
    dlist() { }
    ~dlist() {
        node* iter = _head;
        while (iter) {
            node* victim = iter;
            iter = iter->next;
            delete victim;
        }
    }

    node* head() const { return _head; }
    node* tail() const { return _tail; }

    void insert (int value)
    {
        node *newnode = new node {value, nullptr, nullptr};

        if (_head == nullptr)
            _head = newnode;
        else {
            node* iter = _head;
            for (; iter->next; iter = iter->next) {}
            newnode->prev = iter;
            _tail = iter->next = newnode;
        }
    }

    void print () {
        for (node* iter = _head; iter; iter = iter->next)
            cout << " " << iter->value;
        cout << "\n";
    }

    void rprint() {
        for (node* iter = _tail; iter; iter = iter->prev)
        cout << " " << iter->value;
        cout << "\n";
    }
};

int main (void) {

    dlist list;
    int tmp;

    while (cin >> tmp)
        list.insert(tmp);

    list.print();
    list.rprint();
}

Example Use/Output

$ echo "2 3 4 6 8 10" | ./bin/dlist
 2 3 4 6 8 10
 10 8 6 4 3 2

Memory Use/Error Check

In any code you write that dynamically allocates memory, you have 2 responsibilities regarding any block of memory allocated: (1) always preserve a pointer or reference to the starting address for the block of memory so, (2) it can be freed when it is no longer needed.

It is imperative that you use a memory error checking program to insure you properly use the memory you allocate, and to confirm that you free all the memory you have allocated.

For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.

$ echo "2 3 4 6 8 10" | valgrind ./bin/dlist
==18878== Memcheck, a memory error detector
==18878== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==18878== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==18878== Command: ./bin/dlist
==18878==
 2 3 4 6 8 10
 10 8 6 4 3 2
==18878==
==18878== HEAP SUMMARY:
==18878==     in use at exit: 0 bytes in 0 blocks
==18878==   total heap usage: 9 allocs, 9 frees, 77,968 bytes allocated
==18878==
==18878== All heap blocks were freed -- no leaks are possible
==18878==
==18878== For counts of detected and suppressed errors, rerun with: -v
==18878== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Always confirm that you have freed all memory you have allocated and that there are no memory errors.