Evening,

Trying to iterate through a single linked list and check if it is in order, after doing a few runs of the code it seems that its only checking the first 2 items in the list and not going further. the code to check is in the function string ordered(). just wondered if anyone could help as to why it might be doing this.

I've added the output clearly not in order, if i was to change the 1 to a 10 it would return "not in order".

cpp file.

CustomList a;

int main(int argc, char* argv[]) {
  srand(time(NULL));

  a.push_front(10);
  a.push_front(9);
  a.push_front(20);
  a.push_front(7);
  a.push_front(1);

  a.print();

  std::cout << a.ordered();

  return 0;
}

header file

#include <iostream>
#include <string>

/** One node in a linked list of strings. */

struct CustomListNode {
  int item;
  CustomListNode* next;
};

/** A linked list of strings. */
class CustomList {
 public:
  /** Constructor. */
  CustomList() {}

  /** Destructor. */
  ~CustomList() {}

  /** Print out the items in the list. */
  void print() {
    std::cout << "Contents:\n";
    CustomListNode* p = begin_;
    while (p != nullptr) {
      std::cout << "- " << p->item << "\n";
      p = p->next;
    }
  }

  void push_front(int item) {
    CustomListNode* node = new CustomListNode;
    node->item = item;
    node->next = begin_;

    begin_ = node;
  }

  int size() {
    CustomListNode* p = begin_;

    int count = 0;

    while (p != nullptr) {
      count  ;
      p = p->next;
    }

    return count;
  }

  void pop_front() {
    CustomListNode* p = begin_->next;

    if (begin_ != nullptr) {
      delete begin_;
      begin_ = p;
    }
  }

  void push_back(int item) {
    CustomListNode* p = new CustomListNode;
    p->item = item;
    p->next = nullptr;

    if (begin_ == nullptr) {
      begin_ = p;
    } else {
      CustomListNode* node = begin_;

      while (node->next != nullptr) {
        node = node->next;
      }

      node->next = p;
    }
  }

  void pop_back() {
    CustomListNode* p = begin_;

    while (p->next->next != nullptr) {
      p = p->next;
    }

    CustomListNode* last = p->next;
    p->next = nullptr;
    delete p->next;
  }

  int get_item(int n) {
    CustomListNode* p = begin_;
    for (int i = 0; i < n; i  ) {
      p = p->next;
    }

    return p->item;
  }

  std::string ordered() {
    CustomListNode* p = begin_;

    while (p != nullptr) {
      if (p->item < p->next->item) {
        return "in order";
      } else {
        return "not in order";
      }

      p = p->next;
    }
  }

 private:
  /** Pointer to the first item in the list, or nullptr if the list is empty. */
  CustomListNode* begin_ = nullptr;
};

CodePudding user response：

It's a bit obvious... Let's look at you code....

//...
 std::string ordered()  // why return a string?  A bool would carry all the information
                        // you need, wouldn't it? 
{
    CustomListNode* p = begin_;

    while (p != nullptr) //  A 'for' loop would make your code more readable
                         //  for loop constructs are also less prone to bugs.
                         //  as the code in the loop becomes more complex.
    {
        if (p->item < p->next ->item )  // BUG here, what if p->next is NULL ?
                                        // what happens when your list has duplicates?
        {
            return "in order";           // Your bug is here.  You should
                                         // simply do nothing in this case
                                         // and return success AFTER the loop
                                         // has completed.
        }
        else
        {
            return "not in order"; 
        }
    
        p = p->next;
    }
    return "in order";           // This is where you should return success,
                                 // after all elements have been examined.
}

//...

In other words...

//...
bool ordered()
{
    for (CustomListNode* p = begin_; p && p->next; p = p->next)
    {
        if (p->item > p->next->item)
            return false;
    }

    return true; 
}
//...

CodePudding user response：

>     std::string ordered() {
>         CustomListNode* p = begin_;
>     
>         while (p!=nullptr && p->next != nullptr) { 

    // checking if list is empty or the next item is available for comparison.
    //if list is empty or contains only one element this function will return true

>           if (p->item > p->next->item) {
>             return false;
>           } 
>     
>           p = p->next;
>         }
>         return true;
>       }