Linked List Seg Fault when Returning Component

Question

I am working on a program for my c++ class that is basically a small book store application. The book store is to have a linked list of Members(ListMemberType) and a linked list of Books(ListBookType). Each node of the linked list is made up of a link to the next component and a component. The component is of type BookType.

Here is the header file for ListBookType

#include "bookType.h"

typedef BookType ItemType;    // Type of each component
struct NodeType;              // Forward declaration

class ListBookType {
public:
    const ListBookType& operator=(const ListBookType& rightObject);
    //overload assignment operator
    //will set the left side equal to right side
    void Replace(ItemType theNewItem, ItemType theOldItem);
    //Pre:These are the same book(ISBN is the same)
    //Post: old component will be replaced with the new component
    ListBookType();
    // Constructor
    // Post: Empty list has been created
    ~ListBookType();
    // Destructor
    // Post: All nodes are returned to the heap
    ListBookType(const ListBookType& otherList);
    // Copy constructor
    // Post:  A deep copy of otherList is created and dataPtr is the
    //        external pointer to this copy

    // Action respnsibilities
    void Insert(ItemType item);
    // Pre:  List is not full and item is not in the list
    // Post: item is in the list and length has been incremented
    void Delete(ItemType item);
    // Post: item is not in the list
    void ResetList();
    // The current position is reset to access the first item in the list
    ItemType GetNextItem();
    // Assumptions:  No transformers are called during the iteration.
    // There is an item to be returned; that is, HasNext is true when
    // this method is invoked
    // Pre:  ResetList has been called if this is not the first iteration
    // Post: Returns item at the current position.

    // Knowledge responsibility
    int GetLength() const;
    // Post: Returns the length of the list
    bool IsEmpty() const;
    // Post: Returns true if list is empty; false otherwise
    bool IsFull() const;
    // Post: Returns true if list if full; false otherwise
    bool IsThere  (ItemType item ) const;
    // Post: Returns true if item is in the list and false otherwise
    bool HasNext() const;
    // Returns true if there is another item to be returned; false
    // otherwise
    ItemType GetBook(ItemType bookToGet)const;
    //Pre: Book is in list
    //Post: the book is returned
    //Pre: Book is in the list
    //Post: Book with matching ISBn will be returned
    private:
    NodeType* dataPtr;     // Pointer to the first node in the list
    int length;
    NodeType* currentPos;   // Pointer to the current position in a traversal
    NodeType* lastPtr;
};

And here is the part of the Specification file that I know contains my error, along the parts that I believe may be causing the error.

#include "listBookType.h"
#include "bookType.h"
#include <iostream>
#include <cstddef>           // For NULL

using namespace std;

typedef NodeType* NodePtr;
struct NodeType {
   ItemType component;
   NodePtr link;
};

const ListBookType& ListBookType::operator=(const ListBookType& rightObject) {
   cout<<"Assignment operator bookList"<<endl;

   NodePtr fromPtr;    // Pointer into list being copied from
   NodePtr toPtr;      // Pointer into new list being built
   if(this != &rightObject) {
      if (rightObject.dataPtr == NULL) {
         dataPtr = NULL;
         return *this;
      }
      // Copy first node
      fromPtr = rightObject.dataPtr;
      dataPtr = new NodeType;
      dataPtr->component = fromPtr->component;
      // Copy remaining nodes
      toPtr = dataPtr;
      fromPtr = fromPtr->link;
      while (fromPtr != NULL)
      // Copying nodes from original to duplicate
      {
         toPtr->link = new NodeType;        // Store new node in link of last
                                                // node added to new list
         toPtr = toPtr->link;           // toPtr points to new node
         toPtr->component = fromPtr->component; // Copy component to new node
         fromPtr = fromPtr->link;       // fromPtr points to next node
                        // of original list
      }
      toPtr->link = NULL;
      lastPtr = toPtr;      // Set last pointer
   }
   return *this;
}


ItemType ListBookType::GetBook(ItemType bookToGet)const {
   NodePtr currPtr = dataPtr;      // Loop control pointer
   NodePtr tempPtr = NULL;

   while (currPtr != NULL && currPtr->component != bookToGet
       && currPtr->component < bookToGet) {
     tempPtr = currPtr;
     currPtr = currPtr->link;
   }

   cout<<"right before return of getBook"<< endl;

   return tempPtr->component;
}

ListBookType::ListBookType(const ListBookType& otherList) {
   cout<<"copy construct book list"<< endl;
   NodePtr fromPtr;    // Pointer into list being copied from
   NodePtr toPtr;      // Pointer into new list being built

   if (otherList.dataPtr == NULL) {
      dataPtr = NULL;
      return;
   }
   // Copy first node
   fromPtr = otherList.dataPtr;
   dataPtr = new NodeType;
   dataPtr->component = fromPtr->component;
   // Copy remaining nodes
   toPtr = dataPtr;
   fromPtr = fromPtr->link;
   while (fromPtr != NULL) { // Copying nodes from original to duplicate
      toPtr->link = new NodeType;       // Store new node in link of last
                        // node added to new list
      toPtr = toPtr->link;          // toPtr points to new node
      toPtr->component = fromPtr->component; // Copy component to new node
      fromPtr = fromPtr->link;      // fromPtr points to next node
                        // of original list
   }
   toPtr->link = NULL;
   lastPtr = toPtr;     // Set last pointer
}



ListBookType::~ListBookType() {
   cout<< "destructor book list"<< endl;
   NodePtr tempPtr;
   NodePtr currPtr = dataPtr;
   while (currPtr != NULL) {
      tempPtr = currPtr;
      currPtr = currPtr->link;
      delete tempPtr;
   }
}

The issue I am having is in GetBook(ItemType bookToGet). I tracked the problem down and I am seg faulting when I return tempPtr->component. I am having this same issue in a few other places in the code and I don't know why I am seg faulting here or what the underlying issue may be. (Note: BookType class does NOT contain any dynamic data that would need an the assignment operator overloaded or a copy constructor)

I would really appreciate any help at all. I feel like I am just missing something important that I don't know about.

Answer 1

In your GetBook routine consider the case when dataPtr is already NULL.

You would be accessing return tempPtr->component; //causing a segfault.

You should handle the case when dataPtr is NULL separately.

while (currPtr != NULL && currPtr->component != bookToGet // dataPtr = currPtr is NULL 
       && currPtr->component < bookToGet){
  tempPtr = currPtr;
  currPtr = currPtr->link;
}
cout<<"right before return of getBook"<< endl;
return tempPtr->component; // SEGFAULT!

Answer 2

If the condition in the while statement is false the first time it is evaluated, then tempPtr will never be set to anything other than NULL, and the tempPtr->component in the return statement tries to dereference a null pointer and crashes.

Think about what would be a reasonable default for your function to return if the while condition is false the first time, and then if tempPtr is NULL just before the return statement, return that default instead.