[Travelsonic]

After talking to my professor, I found out I can do the projects for my operating systems class in C++. What a relief, as now I can work with that which I am more familiar with.

My troubles in debugging my dequeue implementation have not gone away fully, however, and thus I still need help.

I can push and pop off the front no issue. My problem is, I'm not sure if everything is OK. Right now, my biggest problem seems to be an incorrect count - which is making me question if everything is ship shape with my push and pop functions.
(it currently shows a value one more than the number of values I try pushing in my test program). I would appreciate it greatly if someone could check my code, and help me if there are in fact any issues.

EDIT: I realized that in my push and pop functions I might be able to consolidate a few lines of condition checking, see comment in function for issue I face there.
Here is the code I have so far:
EDIT: 7:18PM: Replaced the copypaste of list.cpp with the current version of my code.
node.h: Contains the definition for my node class.

Spoiler

#ifndef NODE_H
#define NODE_H
#include <stddef.h>                                                   // So NULL is not undeclared/undefined
// TYPEDEFS:
typedef int nodeInfo;
// CLASS DEFINITION:
// node class:
class node{
    public:
        // CONSTRUCTOR(S) AND DESTRUCTOR:
        // Constructor:
        node(const nodeInfo inData = 0, node * inNext = NULL, node * inPrev = NULL); // Default parameters for data, next, prev
        // Destructor:
        ~node();
        // ACCESSORS AND MUTATORS:
        // Accessors:
        nodeInfo getData() const;
        node * getNext();
        const node * getNext() const;
        node * getPrev();
        const node * getPrev() const;
        // Mutators:
        void setData(const nodeInfo & inData);
        void setNext(node * inNext = NULL);
        void setPrev(node * inPrev = NULL);
        // OVERLOADED OPERATORS
        operator=(const node * copyNode);
        operator==(const node * compareNode);
    private:
        nodeInfo data;           // Node data value
        node * next;             // In a linked list, the next node
        node * prev;             // In a linked list, the previous node
};
#endif 

node.cpp: Contains the function implementations for my node class.

Spoiler

#include "node.h"
// NODE CLASS FUNCTION IMPLEMENTATIONS
// CONSTRUCTOR(S) AND DESTRUCTOR:
// Constructor(s):
node::node(const nodeInfo inData, node * inNext, node * inPrev){ // Default parameters for data, next, prev
    data = inData;
    next = inNext;
    prev = inPrev;
}
// Destructor:
node::~node(){
    //delete next;
    //delete prev;
    //next = NULL;
    //prev = NULL;
}
// ACCESSORS AND MUTATORS:
// Accessors:
nodeInfo node::getData() const{
    return data;
}
node * node::getNext(){
    return next;
}
const node * node::getNext() const{
    return next;
}
node * node::getPrev(){
    return prev;
}
const node * node::getPrev() const{
    return prev;
}
// Mutators:
void node::setData(const nodeInfo & inData){
    data = inData;
}
void node::setNext(node * inNext){
    next = inNext;
}
void node::setPrev(node * inPrev){
    prev = inPrev;
}
// OVERLOADED OPERATORS
node::operator=(const node * copyNode){
    data = copyNode->data;
    next = copyNode->next;
    prev = copyNode->prev;
}
node::operator==(const node * compareNode){
    return ((data == compareNode->getData()) && (next == compareNode->getNext()) && (prev == compareNode->getPrev())) ? true : false;
}

list.h: Contains the definition for my list class.

Spoiler

#ifndef LIST_H
#define LIST_H
#include <stddef.h>                                                   // So NULL is not undeclared/undefined
#include "node.h"
// TYPEDEFS
typedef int listInfo;
// CLASS DEFINITION:
// list class:
class list{
    public:
        // CONSTRUCTOR(S) AND DESTRUCTOR:
        // Constructor(s):
        list(list * inCopyList = NULL);                   // Default constructor -> can take a list to copy, but doesn't have to (param/arg value defaults to NULL)
        // Destructor:
        ~list();
        // ACCESSORS AND MUTATORS:
        // Accessors:
        bool isEmpty();                                   // Return true if the only element on the list is the header, otherwise return false
        bool findInList(const listInfo value);            // Return true if the value appears in the list, otherwise, return false
        size_t getLength();                               // Return the length of the list
        size_t getLength() const;                         // Return the length of the list - const version of the function
        node * getHead();                                 // Return the head node of our list
        const node * getHead() const;                     // Return the head node of our list - const version of the function
        node * getTail();                                 // Return the tail node of our list
        const node * getTail() const;                     // Return the tail node of our list - const version of the function
        // Mutators:
        void initializeList(const listInfo & inData = 0); // Initialize the list with the header pointing at itself
        void pushFront(const listInfo & inData);          // Adds a value to the front of the list
        void pushBack(const listInfo & inData);           // Adds a value to the back of the list
        listInfo popFront();                              // Remove and return the value at the front of the list
        listInfo popBack();                               // Remove and return the value at the back of the list
        void copyList(list * inCopyList);                 // Copy the contents from one list into this list.
        void clearList();                                 // Clear the list, setting the head (and tail) to NULL
        // OVERLOADED OPERATORS:
        void operator=(list * inCopyList);
        bool operator==(list * inCompareList);
    private:
        node * head;                                      // The head of our list
        node * tail;                                      // The tail of our list
};
#endif // LIST_H

list.cpp: Contains the function implementations for my list class.

Spoiler

#include "list.h"
// list CLASS FUNCTION IMPLEMENTATIONS:
// CONSTRUCTOR(S) AND DESTRUCTOR:
// Constructor(s):
// Default Constructor: Can take in a list as an argument, default argument is NULL as per function definition in list.h
list::list(list * inCopyList){
    // If inCopyList is NULL, or inCopyList is empty, just set head and tail to NULL
    if((inCopyList == NULL) || inCopyList->isEmpty()){
        head = NULL;
        tail = NULL;
    }
    // Otherwise, fill this list by popping off from the rear of the copy list,
    // and push them onto the front of this list, preserving order.
    else{
        // "copy" the list by pushing onto the front of THIS list values being
        // popped off the back of the list passed to the function.
        while(!inCopyList->getHead()){pushFront(inCopyList->popBack());}
    }
}
// Destructor:
list::~list(){
}
// ACCESSORS AND MUTATORS:
// Accessors:
// Return true if the only element on the list is the header, otherwise return false
bool list::isEmpty(){
    return ((head == NULL) || ((head->getNext()) == NULL) || ((head->getNext()) == head)) ? true : false;
}
// Return true if the value appears in the list, otherwise, return false
bool list:: findInList(const listInfo value){
        node * tmpNode;   // Create a temporary node for iterating through the nodes in the list
        bool result = false;  // Create a second variable to hold our return value, initialized false so it only changes if we find our value,
        // Iterate through the list checking each node's value
        // Since the list can be circular, checks against the node being
        // NULL, OR having a next node pointing back at the head.
        for(tmpNode = head; ((tmpNode != NULL) && (tmpNode->getNext() != head)); tmpNode = tmpNode->getNext()){
            if((tmpNode->getData()) == value){result = true;}
        }
        delete [] tmpNode;    // Free the memory allocated to tmpNode
        tmpNode = NULL;
        return result;
}
// Return the length of the list
size_t list::getLength(){
    const node * cursor;
	size_t len = 0;
	for (cursor = head; ((cursor != NULL) && (cursor->getNext() != head)); cursor = cursor->getNext()){
	    ++len;
	}
	return  len;
}
// Return the length of the list - const version of the function
size_t list::getLength() const{
    const node * cursor;
	size_t len = 0;
	for (cursor = head; ((cursor != NULL) && (cursor->getNext() != head)); cursor = cursor->getNext()){
	    ++len;
	}
	return  len;
}
// Return the head node of our list
node * list::getHead(){
    return head;
}
// Return the head node of our list - const version of the function
const node * list::getHead() const{
    return head;
}
// Return the tail node of our list
node * list::getTail(){
    return tail;
}
// Return the tail node of our list - const version of the function
const node * list::getTail() const{
    return tail;
}
// Mutators:
// Initialize the list with the header pointing at itself
void list::initializeList(const listInfo & inData){
    head = new node(inData, head, head);
    tail = head;
}
// Adds a value to the front of the list
void list::pushFront(const listInfo & inData){
    if(isEmpty() || (head == NULL) || (tail == head)){initializeList(inData);}
    else{head = new node(inData, head, tail);}
}
// Adds a value to the back of the list
void list::pushBack(const listInfo & inData){
    if(isEmpty() || (tail == NULL) || (tail == head)){initializeList(inData);}
    else{
        node * newBack = new node(inData, head, tail);
        tail->setNext(newBack);
        tail = newBack;
    }
}
// Remove and return the value at the front of the list
listInfo list::popFront(){
    if(isEmpty()){return -1;}                  // If our list is already empty, we needn't do anything more
    listInfo nodeData = head->getData();       // Retrieve our head's node data
    if(head == tail){head = NULL; tail = NULL;}// If this is the last node on the list, we can set both to null
    else{                                      // Otherwise, we need to remove that node
	    node * removed = head;
	    head = head->getNext();
	    delete removed;
	}
	return nodeData;
}
// Remove and return the value at the back of the list
listInfo list::popBack(){
    if(isEmpty()){return -1;}                  // If our list is already empty, we needn't do anything more
    listInfo nodeData = tail->getData();       // Retrieve our tail's node data
    if(tail == head){head = NULL; tail = NULL;}// If this is the last node on the list, we can set both to null
    else{                                      // Otherwise, we need to remove that node
	    node * removed = tail;
	    tail = removed->getPrev();
        tail->setNext(head);
	    delete removed;
    }
    return nodeData;
}
// Copy the contents from one list into this list
void list::copyList(list * inCopyList){
    // If the list pointer is NULL, or the list is empty, just set head and tail to NULL
    if((inCopyList == NULL) || inCopyList->isEmpty()){return;}
    if(!isEmpty()){return;}
    // "copy" the list by pushing onto the front of THIS list values being
    // popped off the back of the list passed to the function.
    while(!inCopyList->getHead()){pushFront(inCopyList->popBack());}
}
// Clear the list, setting the head (and tail) to NULL
void list::clearList(){
    if(head == NULL){return;}
    while(head != tail){
        popFront();
    }
    head = NULL;
    tail = NULL;
}
// OVERLOADED OPERATORS:
void list::operator=(list * inCopyList){
    clearList();
    copyList(inCopyList);
}
bool list::operator==(list * inCompareList){
    bool isEqual = true;
    if((inCompareList == NULL) || (isEmpty() != inCompareList->isEmpty()) || (getLength() != inCompareList->getLength())){
        isEqual = false;
    }
    node * a = getHead();
    node * b = inCompareList->getHead();
    while((a->getNext() != head) || (a->getNext() != inCompareList->getHead())){
        if (a->getData() != b->getData()){isEqual = false;}
        a = a->getNext();
        b = b->getNext();
    }
    return isEqual;
}

main.cpp: The test program for my linked list.

Spoiler

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include "list.h"
int main(){
    list * list1 = new list();

    std::cout << "New empty list created.  List length: " << list1->getLength() << " nodes.\n\n";

    for(int count = 0; count < 10; count++){
        std::cout << "Putting value " << count << " into a node being inserted at the front of the list\n";
        list1->pushFront(count);
    }

    std::cout << "List length: " << list1->getLength() << " nodes.\n\n";

    std::cout << "Popping a node off the front of the list, with value of " << list1->popFront() << ".\n";
    std::cout << "List length: " << list1->getLength() << " nodes.\nClearing list...\n";
    list1->clearList();
    std::cout << "List length: " << list1->getLength() << " nodes.\n\n";

    for(int count = 0; count < 10; count++){
        std::cout << "Putting value " << count << " into a node being inserted at the back of the list\n";
        list1->pushBack(count);
    }

    std::cout << "List length: " << list1->getLength() << " nodes.\n\n";
    listInfo inFindInfo;

    std::cout << "Enter a value to find in the list: ";
    std::cin >> inFindInfo;
    bool searchResult = list1->findInList(inFindInfo);
    if(searchResult){std::cout << "\nValue was found in the list.\n";}
    else{std::cout << "\nValue was NOT found in the list.\n";}

    //std::cout << "Popping a node off the back of the list, with value of " << list1->popBack() << ".\n";
    //std::cout << "List length: " << list1->getLength() << " nodes.\n\n";

    std::cout << "Creating a second linked list, copying list 1 to it...\n";
    list * list2 = new list(list1);
    //list * list2 = new list();
    //list2->copyList(list1);
    std::cout << "The length of this new list is " << list1->getLength() << ".\n\n";

    std::cout << "Clearing the first list...\n";
    list1->clearList();
    std::cout << "First list new length: " << list1->getLength() << " nodes.\n\n";

    std::cout << "Clearing the second list...\n";
    list2->clearList();
    std::cout << "Second list new length: " << list2->getLength() << " nodes.\n\n";

    std::cout << "Both lists cleared.  Freeing memory allocated to the list objects...\n\n";
    delete [] list1;
    delete [] list2;
    list1 = NULL;
    list2 = NULL;
    std::cout << "Memory of both list objects deallocated.  Program complete.\n";

    return 0;
}

This post has been edited by Travelsonic: 31 October 2016 - 06:18 PM

[Black Squirrel]

C++ is very loose with coding standards - you tend to develop your own or are brought into line with an employer's, BUT


Top tip - don't ever write pointer notation like

"gooble * name"

because you will read this as the multiplication operator. I guarantee it.

"gooble* name"


A "gooble pointer" or "pointer to gooble".


Also

if((tmpNode->getData()) == value){result = true;}

if(tmpNode->getData() == value) {
    result = true;
}

The compiler doesn't give two damns about carriage returns or newlines, but the human eye does, and C++ code tends to be read by humans. This is a fairly simple statement so arguably you're not causing too many future problems but

return ((data == compareNode->getData()) && (next == compareNode->getNext()) && (prev == compareNode->getPrev())) ? true : false;

this is not.

I'm personally not a fan of ternary operators in C++ (opinions vary), but here you don't even need it - you're working with boolean logic.

return ((data == compareNode->getData())
     && (next == compareNode->getNext())
     && (prev == compareNode->getPrev()));

Also as it's a learning environment you're not obliged to care about this one right now, but it's very easy to overdose on comments, to the point where they start having a detrimental effect on workflow. Good code should be self documenting - descriptive variable names and functions will make it easy for othe programmers to understand - you don't need to tell them what a class destructor is.


There are other things, but you'll find that the more readable your code is, the easier it will be to discover where the problems are. a.k.a. I don't have the time to compile and run this so I'm avoiding your question and answering my own

[Travelsonic]

Black Squirrel, on 31 October 2016 - 05:10 PM, said:

C++ is very loose with coding standards - you tend to develop your own or are brought into line with an employer's, BUT


Top tip - don't ever write pointer notation like

"gooble * name"

because you will read this as the multiplication operator. I guarantee it.

I haven't yet, but not saying never is a good call - besides, changing it to the way you suggest keeps things clearer for others who need to read my code. :D

Sometimes when my program code is unfinished, and I need another's opinion / help, it's just I feel like someone will inevitably wonder "what the FUCK were you thinking," and suggest something that completely misses the intent of what I am doing, hence my tendency to sometimes overdo it

[BigEvilCorporation]

Your bug is in getLength() - you are checking if cursor's next value is the head, you need to check if cursor is the tail. The last element in the list always points back to the head, so it will never be counted.

A few tips:

- 'nullptr' is now built into the language (C++11 and beyond) so you won't need to explicitly #include the file containing the NULL definition
- Why do you have a non-const getLength()? It serves no purpose, it never modifies anything
- The == operator continues searching even after it's determined that the lists are not equal - you can bail out at that point
- Why is -1 a special number? What if you wanted to actually push a -1 to the list?

This post has been edited by BigEvilCorporation: 01 December 2016 - 11:57 AM

[Travelsonic]

BigEvilCorporation, on 01 December 2016 - 11:56 AM, said:

Your bug is in getLength() - you are checking if cursor's next value is the head, you need to check if cursor is the tail.

But what if it is a circular list, where the tail links back to the head? Surely, if you are getting the length of a circular list, you would check for if you are about to go back to the head, to avoid infinitely looping (hence what I attempted to do)?

Made the tweak to the equality check, thanks for catching that. Missing stuff like that... that's what happens when I try to rush to catch up on a project with very little sleep. XD

I had one of those "I don't know what I did, but it works now" moments - and my dequeue started ALMOST working. (way before I remembered that I had this thread, checked to see if I had further replies... XD) - only problem is my counting function is now not working right. 0_0 After popping a node off the list, counting doesn't work - keeps returning 0.

EDIT: Also realized I didn't even need that boolean variable in my overloaded equality operator. Returns false if it catches inequality in list size, and when comparing the nodes,, allowing for the function to simply return true if it gets to the end.

This post has been edited by Travelsonic: 11 December 2016 - 01:33 PM