C++ Read access violation in doubly linked list in Visual Studio

Question

I am able to compile my code on a Linux box using g++ and run the driver just fine. When compiling and running the driver on my Windows machine I encounter a read access violation error with the ptr->next statement, in the size() method. (Assuming there is only one node) While debugging I can step through the while statements once as intended and on the second pass it continues through the ptr != nullptr even if there is no node.

This error occurs when adding nodes and the list size == 1.

I have been looking through all the statements and cant seem to find where I went wrong. Any information on this is appreciated!

Header

#ifndef DEQUE_H
#define DEQUE_H
#include <iostream>

using namespace std;

template <class Object>
class Deque {
 public:
  Deque( );                                   // the constructor
  Deque( const Deque &rhs );                  // the copy constructor
  ~Deque( );                                  // the destructor

  bool isEmpty( ) const;                      // checks if a deque is empty.
  int size( ) const;                          // retrieves # deque nodes
  const Object &getFront( ) const;            // retrieve the front node
  const Object &getBack( ) const;             // retrieve the tail node

  void clear( );                              // clean up all deque entries.
  void addFront( const Object &obj );         // add a new node to the front
  void addBack( const Object &obj );          // add a new node to the tail
  Object removeFront( );                      // remove the front node
  Object removeBack( );                       // remove the tail node

  const Deque &operator=( const Deque &rhs ); // assignment

 private:
  struct DequeNode {                          // a deque node
    Object item;
    DequeNode *next;
    DequeNode *prev;
  };
  DequeNode *front;
  DequeNode *back;
};

#include "deque.cpp.h"
#endif

CPP

template <class Object>
Deque<Object>::Deque( ) {                          // the constructor
  front = back = NULL;
}

template <class Object>
Deque<Object>::Deque( const Deque &rhs ) {         // the copy constructor
  front = back = NULL;
  *this = rhs;
}

template <class Object>
Deque<Object>::~Deque( ) {                         // the destructor
  clear( );
}

template <class Object>
bool Deque<Object>::isEmpty( ) const {             // check if a deque is empty
  return front == NULL;
}

template <class Object>
int Deque<Object>::size( ) const {                 // retrieves # deque nodes
    int length = 0;
    DequeNode* ptr = front;

    while (ptr != nullptr) {
        length++;
        ptr = ptr->next;
    }
    return length;
}

template <class Object>
const Object &Deque<Object>::getFront( ) const {   // retrieve the front node
  if ( isEmpty( ) )
    throw "empty queue";
  return front->item;
}

template <class Object>
const Object &Deque<Object>::getBack( ) const {    // retrieve the tail node
  if ( isEmpty( ) )
    throw "empty queue";
  return back->item;
}

template <class Object>
void Deque<Object>::clear( ) {          // clean up all entries.
  while ( !isEmpty( ) )                 // dequeue till the queue gets empty.
    removeFront( );
}

template <class Object>
void Deque<Object>::addFront( const Object &obj ) {// add a new node to  front
  // Implement the function body.
  DequeNode* newNode = new DequeNode;
  newNode->item = obj;

  // if no nodes, new node is front and back
  if (isEmpty()){
    front = back = newNode;
  }

  // if one node, new front and back are established

  else if (size() == 1){
    back->prev = newNode;
    front = newNode;
    front->next = back;
  }

  // add to front and shift right
  else {
    DequeNode* oldFront = front;
    front->prev = newNode;
    front = newNode;
    front->next = oldFront;
    }
}

template <class Object>
void Deque<Object>::addBack( const Object &obj ) { // add a new node to tail
  // Implement the function body.
  DequeNode* newNode = new DequeNode;
  newNode->item = obj;

  // if no nodes, new node is front and back
  if (isEmpty()){
    front = back = newNode;
  }

  // if one node, new front and back are established
  else if (size() == 1){
    front->next = newNode;
    back = newNode;
    back->prev = front;
  }

  // add to back and shift left
  else {
    DequeNode* oldBack = back;
    back->next = newNode;
    back = newNode;
    back->prev = oldBack;
  }
}

template <class Object>
Object Deque<Object>::removeFront( ) {  // remove the front node
  // Implement the function body.

  if (isEmpty())
    throw "empty queue"; 

  // if only one node, return item, Deque is now NULL.
  else if (size() == 1){
    DequeNode* remove = front;
    Object result = remove->item; 
    front = back = NULL;

    delete remove;
    remove = NULL;

    return result;
    }

  // remove front node, shift right
  else {
    Object result = front->item;
    DequeNode* remove = front;
    front = front->next;
    front->prev = NULL;

    delete remove;
    remove = NULL;

    return result;
    }
}

template <class Object>
Object Deque<Object>::removeBack( ) {   // remove the tail node
  // Implement the function body.

  if (isEmpty())
     throw "empty queue";

  // if only one node, return item, Deque is now NULL.
  else if (size() == 1){
      DequeNode* remove = back;
      Object result = remove->item;
      front = back = NULL;

      delete remove;
      remove = NULL;

      return result;
    }

  // remove back node, shift left
  else {
    Object result = back->item; 
    DequeNode* remove = back;
    back = back->prev;
    back->next = NULL;

    delete remove;
    remove = NULL;

    return result;
    }
}

template <class Object>
const Deque<Object> &Deque<Object>::operator=( const Deque &rhs ) { // assign
  if ( this != &rhs ) { // avoid self assignment
    clear( );
    for ( DequeNode *rptr = rhs.front; rptr != NULL; rptr = rptr->next )
      addBack( rptr->item );
  }
  return *this;
}

Driver

#include <iostream>
#include "deque.h"

using namespace std;

int main( ) {
  Deque<int> deque1;
  int item;

  for ( int j = 0; j < 5; j++ )
    deque1.addBack( j );
  for ( int j = 5; j < 10; j++ )
    deque1.addFront( j );

  Deque<int> deque2 = deque1;
  deque2.addBack( 10 );

  cout << "deque1: " << endl;
  while ( !deque1.isEmpty( ) )
    cout << deque1.removeFront( ) << endl;

  cout << "deque2: " << endl;
  while ( !deque2.isEmpty( ) )
    cout << deque2.removeBack( ) << endl;
}

Answer 1

You are reading uninitialized memory.

DequeNode* newNode = new DequeNode; allocates a new DequeNode, but it doesn't initialize the new node's members (next and prev).

You should declare DequeNode like this:

struct DequeNode {                          // a deque node
  Object item;
  DequeNode *next = nullptr;
  DequeNode *prev = nullptr;
};

in order to ensure that the next and prev pointers are initialized to nullptr.

You should learn how to debug these simple bugs using your debugger.

If it worked under Linux, it is pure chance. Probably the memory allocation under Linux initializes newly allocated memory with 0, whereas on Windows newly allocated memory is filled with a special value 0xCDCDCDCD if the program was compiled in debug mode.

The debugger shows you this value:

Se this SO article for more information about which special values are used for uninitialized memory in Visual Studio.

Answer 2

Make sure you set the prev and next pointers correctly when you insert an element.

template <class Object>
void Deque<Object>::addFront( const Object &obj ) {// add a new node to  front
  // Implement the function body.
  DequeNode* newNode = new DequeNode;
  newNode->item = obj;

  //Set these pointers to proper values depending on the state of the queue.
  newNode->next = nullptr;
  newNode->prev = nullptr;

For example, when your queue is empty and you are inserting an item into it,

 // if no nodes, new node is front and back
 if (isEmpty()){
   front = back = newNode;
 }

would not initialize next or prev pointers. So when you reach this node in your iteration, these pointers will not be equal to nullptr and you will be trying to access invalid memory.