Doubly linked list confusion

Question

I created doubly linked list and 2 functions. The first function prints the list from start to end and the second function prints the list from back to start. In the second function I set the first node->prev to NULL but

I do not understand why the first function actually works because I have never set the last node's next pointer to NULL so in my opinion it should create an infinite loop.

Here is the code :

#include <iostream>

using namespace std;

class LinkedList
{
    struct Node 
    {
        int data;
        Node * next;
        Node * prev;
    };

    public:
           LinkedList    ( void );
      void AddToList     ( int val );
      void FrontToBack   ( void ) const;
      void BackToFront   ( void ) const; 

    private:
        Node * head;
        Node * n;
        Node * tail;
};

LinkedList::LinkedList ( void )
{
    head = NULL;
    n = NULL;
    tail = NULL;
}

void LinkedList::AddToList ( int val )
{
    n = new Node ( );
    n -> data = val;
    if ( head == NULL )
    {
        n -> prev = NULL;
        head = n;
        tail = n;
    }
    else
    {
        n -> prev = tail;
        tail -> next = n;
        tail = n;
    }
}

void LinkedList::FrontToBack ( void ) const
{
    Node * tmp = head;
    int size = 0;

    cout << "Printing list from head to tail:" << endl; 

    while ( tmp != NULL )
    {
        if ( ! size )
        {
            cout << tmp -> data;
            tmp = tmp -> next;
        }
        else
        {
            cout << " " << tmp -> data;
            tmp = tmp -> next;
        }
        ++ size;
    }

    cout << endl;
}

void LinkedList::BackToFront ( void ) const
{
    Node * tmp = tail;
    int size = 0;

    cout << "Printing list from tail to head:" << endl;

    while ( tmp != NULL )
    {
        if ( ! size )
        {
            cout << tmp -> data;
            tmp = tmp -> prev;
        }
        else
        {
            cout << " " << tmp -> data;
            tmp = tmp -> prev;
        }
        ++ size;
    }

    cout << endl;
}



int main ( void )
{

    LinkedList list;

    list.AddToList( 1 );
    list.AddToList( 2 );
    list.AddToList( 3 );
    list.AddToList( 4 );
    list.AddToList( 5 );
    list.AddToList( 6 );

    list.FrontToBack( );
    list.BackToFront( );

    return 0;

}

You simply have undefined behavior with accessing uninitialized member variables of Node, anything can happen including seemingly correct behavior. — πάντα ῥεῖ
@πάνταῥεῖ so i do not need to even set n -> prev = NULL; in the first node? — kvway
@kvway No, you are always responsible to initialize all the member variables correctly. I said anything can happen, there's no guarantee that it will behave as you observe. — πάντα ῥεῖ

πάντα ῥεῖ πάντα ῥεῖ · Accepted Answer · 2016-03-13T12:13:02

I do not understand why the first function actually works because I have never set the last node's next pointer to NULL so in my opinion it should create an infinite loop.

The next and prev pointers of struct Node are never initialized, thus accessing and dereferencing them is undefined behavior. This means you cannot expect any specific behavior like looping infinitely.

To ensure defined behavior just default initialize the pointers in your Node struct:

struct Node 
{
    int data;
    Node * next;
    Node * prev;

    Node() : next(nullptr), prev(nullptr) {} // <<<<<<<<<<<<<<<<<<<
};

Doubly linked list confusion

1 Answers