C++ Help With Lists Take 2

Discussion in 'Technical Discussion' started by Travelsonic, Oct 31, 2016.

  1. Travelsonic

    Travelsonic

    Member
    787
    13
    18
    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.
    Code (Text):
    1.  
    2. #ifndef NODE_H
    3. #define NODE_H
    4. #include <stddef.h>                                                   // So NULL is not undeclared/undefined
    5. // TYPEDEFS:
    6. typedef int nodeInfo;
    7. // CLASS DEFINITION:
    8. // node class:
    9. class node{
    10.     public:
    11.         // CONSTRUCTOR(S) AND DESTRUCTOR:
    12.         // Constructor:
    13.         node(const nodeInfo inData = 0, node * inNext = NULL, node * inPrev = NULL); // Default parameters for data, next, prev
    14.         // Destructor:
    15.         ~node();
    16.         // ACCESSORS AND MUTATORS:
    17.         // Accessors:
    18.         nodeInfo getData() const;
    19.         node * getNext();
    20.         const node * getNext() const;
    21.         node * getPrev();
    22.         const node * getPrev() const;
    23.         // Mutators:
    24.         void setData(const nodeInfo & inData);
    25.         void setNext(node * inNext = NULL);
    26.         void setPrev(node * inPrev = NULL);
    27.         // OVERLOADED OPERATORS
    28.         operator=(const node * copyNode);
    29.         operator==(const node * compareNode);
    30.     private:
    31.         nodeInfo data;           // Node data value
    32.         node * next;             // In a linked list, the next node
    33.         node * prev;             // In a linked list, the previous node
    34. };
    35. #endif
    36.  
    node.cpp: Contains the function implementations for my node class.
    Code (Text):
    1.  
    2. #include "node.h"
    3. // NODE CLASS FUNCTION IMPLEMENTATIONS
    4. // CONSTRUCTOR(S) AND DESTRUCTOR:
    5. // Constructor(s):
    6. node::node(const nodeInfo inData, node * inNext, node * inPrev){ // Default parameters for data, next, prev
    7.     data = inData;
    8.     next = inNext;
    9.     prev = inPrev;
    10. }
    11. // Destructor:
    12. node::~node(){
    13.     //delete next;
    14.     //delete prev;
    15.     //next = NULL;
    16.     //prev = NULL;
    17. }
    18. // ACCESSORS AND MUTATORS:
    19. // Accessors:
    20. nodeInfo node::getData() const{
    21.     return data;
    22. }
    23. node * node::getNext(){
    24.     return next;
    25. }
    26. const node * node::getNext() const{
    27.     return next;
    28. }
    29. node * node::getPrev(){
    30.     return prev;
    31. }
    32. const node * node::getPrev() const{
    33.     return prev;
    34. }
    35. // Mutators:
    36. void node::setData(const nodeInfo & inData){
    37.     data = inData;
    38. }
    39. void node::setNext(node * inNext){
    40.     next = inNext;
    41. }
    42. void node::setPrev(node * inPrev){
    43.     prev = inPrev;
    44. }
    45. // OVERLOADED OPERATORS
    46. node::operator=(const node * copyNode){
    47.     data = copyNode->data;
    48.     next = copyNode->next;
    49.     prev = copyNode->prev;
    50. }
    51. node::operator==(const node * compareNode){
    52.     return ((data == compareNode->getData()) && (next == compareNode->getNext()) && (prev == compareNode->getPrev())) ? true : false;
    53. }
    54.  
    list.h: Contains the definition for my list class.
    Code (Text):
    1.  
    2. #ifndef LIST_H
    3. #define LIST_H
    4. #include <stddef.h>                                                   // So NULL is not undeclared/undefined
    5. #include "node.h"
    6. // TYPEDEFS
    7. typedef int listInfo;
    8. // CLASS DEFINITION:
    9. // list class:
    10. class list{
    11.     public:
    12.         // CONSTRUCTOR(S) AND DESTRUCTOR:
    13.         // Constructor(s):
    14.         list(list * inCopyList = NULL);                   // Default constructor -> can take a list to copy, but doesn't have to (param/arg value defaults to NULL)
    15.         // Destructor:
    16.         ~list();
    17.         // ACCESSORS AND MUTATORS:
    18.         // Accessors:
    19.         bool isEmpty();                                   // Return true if the only element on the list is the header, otherwise return false
    20.         bool findInList(const listInfo value);            // Return true if the value appears in the list, otherwise, return false
    21.         size_t getLength();                               // Return the length of the list
    22.         size_t getLength() const;                         // Return the length of the list - const version of the function
    23.         node * getHead();                                 // Return the head node of our list
    24.         const node * getHead() const;                     // Return the head node of our list - const version of the function
    25.         node * getTail();                                 // Return the tail node of our list
    26.         const node * getTail() const;                     // Return the tail node of our list - const version of the function
    27.         // Mutators:
    28.         void initializeList(const listInfo & inData = 0); // Initialize the list with the header pointing at itself
    29.         void pushFront(const listInfo & inData);          // Adds a value to the front of the list
    30.         void pushBack(const listInfo & inData);           // Adds a value to the back of the list
    31.         listInfo popFront();                              // Remove and return the value at the front of the list
    32.         listInfo popBack();                               // Remove and return the value at the back of the list
    33.         void copyList(list * inCopyList);                 // Copy the contents from one list into this list.
    34.         void clearList();                                 // Clear the list, setting the head (and tail) to NULL
    35.         // OVERLOADED OPERATORS:
    36.         void operator=(list * inCopyList);
    37.         bool operator==(list * inCompareList);
    38.     private:
    39.         node * head;                                      // The head of our list
    40.         node * tail;                                      // The tail of our list
    41. };
    42. #endif // LIST_H
    43.  
    list.cpp: Contains the function implementations for my list class.
    Code (Text):
    1.  
    2. #include "list.h"
    3. // list CLASS FUNCTION IMPLEMENTATIONS:
    4. // CONSTRUCTOR(S) AND DESTRUCTOR:
    5. // Constructor(s):
    6. // Default Constructor: Can take in a list as an argument, default argument is NULL as per function definition in list.h
    7. list::list(list * inCopyList){
    8.     // If inCopyList is NULL, or inCopyList is empty, just set head and tail to NULL
    9.     if((inCopyList == NULL) || inCopyList->isEmpty()){
    10.         head = NULL;
    11.         tail = NULL;
    12.     }
    13.     // Otherwise, fill this list by popping off from the rear of the copy list,
    14.     // and push them onto the front of this list, preserving order.
    15.     else{
    16.         // "copy" the list by pushing onto the front of THIS list values being
    17.         // popped off the back of the list passed to the function.
    18.         while(!inCopyList->getHead()){pushFront(inCopyList->popBack());}
    19.     }
    20. }
    21. // Destructor:
    22. list::~list(){
    23. }
    24. // ACCESSORS AND MUTATORS:
    25. // Accessors:
    26. // Return true if the only element on the list is the header, otherwise return false
    27. bool list::isEmpty(){
    28.     return ((head == NULL) || ((head->getNext()) == NULL) || ((head->getNext()) == head)) ? true : false;
    29. }
    30. // Return true if the value appears in the list, otherwise, return false
    31. bool list:: findInList(const listInfo value){
    32.         node * tmpNode;   // Create a temporary node for iterating through the nodes in the list
    33.         bool result = false;  // Create a second variable to hold our return value, initialized false so it only changes if we find our value,
    34.         // Iterate through the list checking each node's value
    35.         // Since the list can be circular, checks against the node being
    36.         // NULL, OR having a next node pointing back at the head.
    37.         for(tmpNode = head; ((tmpNode != NULL) && (tmpNode->getNext() != head)); tmpNode = tmpNode->getNext()){
    38.             if((tmpNode->getData()) == value){result = true;}
    39.         }
    40.         delete [] tmpNode;    // Free the memory allocated to tmpNode
    41.         tmpNode = NULL;
    42.         return result;
    43. }
    44. // Return the length of the list
    45. size_t list::getLength(){
    46.     const node * cursor;
    47.     size_t len = 0;
    48.     for (cursor = head; ((cursor != NULL) && (cursor->getNext() != head)); cursor = cursor->getNext()){
    49.         ++len;
    50.     }
    51.     return  len;
    52. }
    53. // Return the length of the list - const version of the function
    54. size_t list::getLength() const{
    55.     const node * cursor;
    56.     size_t len = 0;
    57.     for (cursor = head; ((cursor != NULL) && (cursor->getNext() != head)); cursor = cursor->getNext()){
    58.         ++len;
    59.     }
    60.     return  len;
    61. }
    62. // Return the head node of our list
    63. node * list::getHead(){
    64.     return head;
    65. }
    66. // Return the head node of our list - const version of the function
    67. const node * list::getHead() const{
    68.     return head;
    69. }
    70. // Return the tail node of our list
    71. node * list::getTail(){
    72.     return tail;
    73. }
    74. // Return the tail node of our list - const version of the function
    75. const node * list::getTail() const{
    76.     return tail;
    77. }
    78. // Mutators:
    79. // Initialize the list with the header pointing at itself
    80. void list::initializeList(const listInfo & inData){
    81.     head = new node(inData, head, head);
    82.     tail = head;
    83. }
    84. // Adds a value to the front of the list
    85. void list::pushFront(const listInfo & inData){
    86.     if(isEmpty() || (head == NULL) || (tail == head)){initializeList(inData);}
    87.     else{head = new node(inData, head, tail);}
    88. }
    89. // Adds a value to the back of the list
    90. void list::pushBack(const listInfo & inData){
    91.     if(isEmpty() || (tail == NULL) || (tail == head)){initializeList(inData);}
    92.     else{
    93.         node * newBack = new node(inData, head, tail);
    94.         tail->setNext(newBack);
    95.         tail = newBack;
    96.     }
    97. }
    98. // Remove and return the value at the front of the list
    99. listInfo list::popFront(){
    100.     if(isEmpty()){return -1;}                  // If our list is already empty, we needn't do anything more
    101.     listInfo nodeData = head->getData();       // Retrieve our head's node data
    102.     if(head == tail){head = NULL; tail = NULL;}// If this is the last node on the list, we can set both to null
    103.     else{                                      // Otherwise, we need to remove that node
    104.         node * removed = head;
    105.         head = head->getNext();
    106.         delete removed;
    107.     }
    108.     return nodeData;
    109. }
    110. // Remove and return the value at the back of the list
    111. listInfo list::popBack(){
    112.     if(isEmpty()){return -1;}                  // If our list is already empty, we needn't do anything more
    113.     listInfo nodeData = tail->getData();       // Retrieve our tail's node data
    114.     if(tail == head){head = NULL; tail = NULL;}// If this is the last node on the list, we can set both to null
    115.     else{                                      // Otherwise, we need to remove that node
    116.         node * removed = tail;
    117.         tail = removed->getPrev();
    118.         tail->setNext(head);
    119.         delete removed;
    120.     }
    121.     return nodeData;
    122. }
    123. // Copy the contents from one list into this list
    124. void list::copyList(list * inCopyList){
    125.     // If the list pointer is NULL, or the list is empty, just set head and tail to NULL
    126.     if((inCopyList == NULL) || inCopyList->isEmpty()){return;}
    127.     if(!isEmpty()){return;}
    128.     // "copy" the list by pushing onto the front of THIS list values being
    129.     // popped off the back of the list passed to the function.
    130.     while(!inCopyList->getHead()){pushFront(inCopyList->popBack());}
    131. }
    132. // Clear the list, setting the head (and tail) to NULL
    133. void list::clearList(){
    134.     if(head == NULL){return;}
    135.     while(head != tail){
    136.         popFront();
    137.     }
    138.     head = NULL;
    139.     tail = NULL;
    140. }
    141. // OVERLOADED OPERATORS:
    142. void list::operator=(list * inCopyList){
    143.     clearList();
    144.     copyList(inCopyList);
    145. }
    146. bool list::operator==(list * inCompareList){
    147.     bool isEqual = true;
    148.     if((inCompareList == NULL) || (isEmpty() != inCompareList->isEmpty()) || (getLength() != inCompareList->getLength())){
    149.         isEqual = false;
    150.     }
    151.     node * a = getHead();
    152.     node * b = inCompareList->getHead();
    153.     while((a->getNext() != head) || (a->getNext() != inCompareList->getHead())){
    154.         if (a->getData() != b->getData()){isEqual = false;}
    155.         a = a->getNext();
    156.         b = b->getNext();
    157.     }
    158.     return isEqual;
    159. }
    160.  
    main.cpp: The test program for my linked list.
    Code (Text):
    1.  
    2. #include <cstdlib>
    3. #include <iostream>
    4. #include <stdio.h>
    5. #include "list.h"
    6. int main(){
    7.     list * list1 = new list();
    8.  
    9.     std::cout << "New empty list created.  List length: " << list1->getLength() << " nodes.\n\n";
    10.  
    11.     for(int count = 0; count < 10; count++){
    12.         std::cout << "Putting value " << count << " into a node being inserted at the front of the list\n";
    13.         list1->pushFront(count);
    14.     }
    15.  
    16.     std::cout << "List length: " << list1->getLength() << " nodes.\n\n";
    17.  
    18.     std::cout << "Popping a node off the front of the list, with value of " << list1->popFront() << ".\n";
    19.     std::cout << "List length: " << list1->getLength() << " nodes.\nClearing list...\n";
    20.     list1->clearList();
    21.     std::cout << "List length: " << list1->getLength() << " nodes.\n\n";
    22.  
    23.     for(int count = 0; count < 10; count++){
    24.         std::cout << "Putting value " << count << " into a node being inserted at the back of the list\n";
    25.         list1->pushBack(count);
    26.     }
    27.  
    28.     std::cout << "List length: " << list1->getLength() << " nodes.\n\n";
    29.     listInfo inFindInfo;
    30.  
    31.     std::cout << "Enter a value to find in the list: ";
    32.     std::cin >> inFindInfo;
    33.     bool searchResult = list1->findInList(inFindInfo);
    34.     if(searchResult){std::cout << "\nValue was found in the list.\n";}
    35.     else{std::cout << "\nValue was NOT found in the list.\n";}
    36.  
    37.     //std::cout << "Popping a node off the back of the list, with value of " << list1->popBack() << ".\n";
    38.     //std::cout << "List length: " << list1->getLength() << " nodes.\n\n";
    39.  
    40.     std::cout << "Creating a second linked list, copying list 1 to it...\n";
    41.     list * list2 = new list(list1);
    42.     //list * list2 = new list();
    43.     //list2->copyList(list1);
    44.     std::cout << "The length of this new list is " << list1->getLength() << ".\n\n";
    45.  
    46.     std::cout << "Clearing the first list...\n";
    47.     list1->clearList();
    48.     std::cout << "First list new length: " << list1->getLength() << " nodes.\n\n";
    49.  
    50.     std::cout << "Clearing the second list...\n";
    51.     list2->clearList();
    52.     std::cout << "Second list new length: " << list2->getLength() << " nodes.\n\n";
    53.  
    54.     std::cout << "Both lists cleared.  Freeing memory allocated to the list objects...\n\n";
    55.     delete [] list1;
    56.     delete [] list2;
    57.     list1 = NULL;
    58.     list2 = NULL;
    59.     std::cout << "Memory of both list objects deallocated.  Program complete.\n";
    60.  
    61.     return 0;
    62. }
    63.  
     
  2. Black Squirrel

    Black Squirrel

    waiting for you on the beach Wiki Sysop
    5,271
    102
    43
    Northumberland, England
    it's a quipu
    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
    Code (Text):
    1. if((tmpNode->getData()) == value){result = true;}
    Code (Text):
    1. if(tmpNode->getData() == value) {
    2.     result = true;
    3. }
    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

    Code (Text):
    1. 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.


    Code (Text):
    1. return ((data == compareNode->getData())
    2.      && (next == compareNode->getNext())
    3.      && (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 :eng101:
     
  3. Travelsonic

    Travelsonic

    Member
    787
    13
    18
    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
     
  4. BigEvilCorporation

    BigEvilCorporation

    Member
    29
    0
    0
    UK
    Tanglewood
    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?
     
  5. Travelsonic

    Travelsonic

    Member
    787
    13
    18
    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.