2
\$\begingroup\$

Edited: incorporated some feedback and added a lot of features

I've written a basic Doubly Linked List Class where every insertion into the class should be sorted into ascending order. The project will eventually merge two LinkedLists so the prev pointers to the Nodes will assist with that.

For now, I was looking for feedback on how well implemented an insertion method. I elected to create two private methods to cover cases where you need to insert at the front and everywhere else.

SortedList.h


#include <iostream>

#pragma once


class SortedList
{
   struct Node {
      int data = 0;
      Node* prev = nullptr;
      Node* next = nullptr;
   };

private:
   int m_numItems;
   Node* m_head;

public:
   // CONSTRUCTOR
   SortedList();

   // copy constructor
   SortedList(const SortedList& otherList);

   // move constructor
   SortedList(SortedList&& rhs) noexcept;

   // DESTRUCTOR
   ~SortedList();

   // ACCESSORS

   /** Gets the current number of entries in this list.
   @return The integer number of entries currently in the list. */
   int size() const;

   /** Sees whether this list is empty.
   @return true if the list is empty, or false if not. */
   bool empty() const;

   /** Output the contents of a sorted list in order,
   with each element separated by a space.*/
   void display(std::ostream& out) const;

   // MUTATORS
   /** Creates a new Node (dynamically allocated) where Node member data = item. 
   Inserts in the correct location of the sorted list (ascending order), and increases m_numItems by 1. 
   @return true if the new Node with item was added successfully, otherwise returns false. */
   bool insert(int item);

   /** Searches and removes the first occurrence of item in the list. If found,
   deallocates memory for the removed Node. 
   @return true if item was removed successfully, otherwise returns false if item 
   was not found in the List or the List was empty.
   Reduces m_numItems by 1 */
   bool remove(int item);

   /** Removes all entries from this list.
   @post  List contains no items, and the count of items is 0. */
   void clear();

   /** Overloads [] operator to find an index for a given item.
   First item in the list is at location 0.
   @return int index for a given value, -1 if item isn't found. */
   int operator[] (int item) const;

   /** Overloaded assignment operator for deep copy. First deallocates memory for all of the Nodes (if any) in the 
   sorted list on the left-hand side before creating new Nodes for all Nodes in the sorted list on the 
   right-hand side and copying each data item. 
   @return the new lhs list. If the lhs and rhs lists are the same, it will do nothing. */
   SortedList& operator=(const SortedList& rhs);

   /** Move assignment operator: will be used instead of the assignment operator when assigning a temporary SortedList 
   to another SortedList. Instead of copying the Nodes from the temporary list into a non-temporary list and destroying 
   the temporary list, it can simply pass that temporary list over to be assigned. 
   @return the new lhs list */
   SortedList& operator=(SortedList&& rhs) noexcept;

   /** Overloads the equality operator to check if the current sorted list (the left-hand side) is equal to 
   sl (the sorted list on the right-hand side). Two sorted lists are equal if they are the same size and every 
   item in one list is the same as the corresponding item in the other list. 
   @return true if the two sorted lists are equal, otherwise false. */
   bool operator==(const SortedList& otherList) const;

   bool operator!=(const SortedList& otherList) const;

private:
   // MUTATORS

   /** prepend new item to the head of the list
   @return true if item was inserted successfully */
   bool insertFront(int item);

   /** append new item to the tail of the list
   @return true if item was inserted successfully */
   bool insertBack(Node* tail, int item);

   /** Called by insert method to insert new item before a given node in the list
   that is not at the head of the list
   @return true if item was inserted successfully */
   bool insertBefore(Node* curr_node, int item);

   /** remove item at the head of the list
   @return true if item was removed successfully*/
   bool removeFront(Node* prev_node);

   /** remove current Node that's not at head of list 
   @return true if item was removed successfully */
   bool removeCurr(Node* prev_node, Node* curr_node);

   /** Creates a deep copy of the sorted list that is passed in (otherList). 
   A deep copy will create new Node objects for each Node in otherList and copy the data for each Node in the correct order. 
   If otherList is empty, it will do nothing.*/
   void copyListNodes(const SortedList& other_list);

public:
   // FRIENDS

   /** Overloads the stream insertion operator to output the contents of a sorted list in order, 
   with each element separated by a space. Makes the operator<< method a friend to SortedList class.*/
   friend std::ostream& operator<<(std::ostream& output, const SortedList& list);

   /** Function overloads + and is defined outside of the SortedList class. 
   Used to merge two SortedLists (lhs and rhs), keeping all items in sorted order.
   @return new merged SortedList. */
   friend SortedList operator+(const SortedList& lhs, const SortedList& rhs);
};

SortedList.cpp

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


// CONSTRUCTOR
SortedList::SortedList() {
   m_numItems = 0;
   m_head = nullptr;
}

// copy constructor
SortedList::SortedList(const SortedList& otherList) {
   copyListNodes(otherList);
}

// move constructor
SortedList::SortedList(SortedList&& rhs) noexcept {
   m_numItems = rhs.m_numItems;
   m_head = rhs.m_head;
   rhs.m_head = nullptr;
}

// DESTRUCTOR
SortedList::~SortedList() {
   this->clear();
}

// ACCESSORS
/** Gets the current number of entries in this list.
@return The integer number of entries currently in the list. */
int SortedList::size() const {
   return m_numItems;
}

/** Sees whether this list is empty.
@return true if the list is empty, or false if not. */
bool SortedList::empty() const {
   return m_head == nullptr;
}

/** Output the contents of a sorted list in order,
with each element separated by a space.*/
void SortedList::display(std::ostream& out) const {
   Node* curr = m_head;

   if (curr == nullptr) {
      out << "The sorted list is empty";
   }

   while (curr) {
      out << curr->data << " ";
      curr = curr->next;
   }
   out << std::endl;
}

// MUTATORS

/** Creates a new Node (dynamically allocated) where Node member data = item.
Inserts in the correct location of the sorted list (ascending order), and increases m_numItems by 1.
@return true if the new Node with item was added successfully, otherwise returns false. */
bool SortedList::insert(int item) {

   Node* curr_node = m_head;

   if (curr_node == nullptr) {
      insertFront(item);
      ++m_numItems;
      return true;
   }
   
   Node* prev_node = nullptr;

   while (curr_node != nullptr) {
      
      ; if (item <= curr_node->data) {

         if (curr_node->prev == nullptr) {
            insertFront(item);
         }

         else {
            insertBefore(curr_node, item);
         }

         ++m_numItems;
         return true;
      }
      prev_node = curr_node;
      curr_node = curr_node->next;
   }
   insertBack(prev_node, item);
   ++m_numItems;
}


/** Searches and removes the first occurrence of item in the List. If found,
deallocates memory for the removed Node.
@return true if item was removed successfully, otherwise returns false if anEntry
was not found in the List or the List was empty.
Reduces m_numItems by 1 */
bool SortedList::remove(int item) {

      Node* curr_node = m_head;
      Node* prev_node = nullptr;

      while (curr_node != nullptr) {

         if (item == curr_node->data) {
            // item is at the head position
            if (prev_node == nullptr) {
               removeFront(prev_node);
            }
            
            // item is elsewhere
            else {
               removeCurr(prev_node, curr_node);
            }
            --m_numItems;

            return true;
         }
         else {
            // advance pointers
            prev_node = curr_node;
            curr_node = curr_node->next;
         }
      }

      return false;
}

/** Removes all entries from this list.
@post  List contains no items, and the count of items is 0. */
void SortedList::clear()
{
   Node* current = m_head;
   while (current) {
      Node* next = current->next;
      delete current;
      --m_numItems;
      current = next;
   }
   m_head = nullptr;
}

/**overloads [] operator to find an index for a given item. 
First item in the list is at location 0. 
@return int index for a given value, -1 if item isn't found. */
int SortedList::operator[] (int item) const {

   Node* curr_node = m_head;
   int curr_index = 0;
   while (curr_node != nullptr) {
      if (curr_node->data == item) {
         return curr_index;
      }
      ++curr_index;
      curr_node = curr_node->next;
   }
   return -1;
}

/** Overloaded assignment operator for deep copy. First deallocates memory for all of the Nodes (if any) in the
sorted list on the left-hand side before creating new Nodes for all Nodes in the sorted list on the
right-hand side and copying each data item.
@return the new lhs list. If the lhs and rhs lists are the same, it will do nothing.*/
SortedList& SortedList::operator=(const SortedList& rhs) {
   if (this != &rhs) {
      this->clear();
      copyListNodes(rhs);
   }
   return *this;
}

/** Move assignment operator: will be used instead of the assignment operator when assigning a temporary SortedList
to another SortedList. Instead of copying the Nodes from the temporary list into a non-temporary list and destroying
the temporary list, it can simply pass that temporary list over to be assigned.
@return the new lhs list */
SortedList& SortedList::operator=(SortedList&& rhs) noexcept {
   m_numItems = rhs.m_numItems;
   m_head = rhs.m_head;
   rhs.m_head = nullptr;

   return *this;
}

/** Overloads the equality operator to check if the current sorted list (the left-hand side) is equal to
sl (the sorted list on the right-hand side). Two sorted lists are equal if they are the same size and every
item in one list is the same as the corresponding item in the other list.
@return true if the two sorted lists are equal, otherwise false. */
bool SortedList::operator==(const SortedList& otherList) const {
   if (this->size() != otherList.size()) {
      return false;
   }

   Node* this_curr = m_head;
   Node* other_curr = otherList.m_head;
   while (this_curr != nullptr || other_curr != nullptr) {
      if (this_curr->data != other_curr->data) {
         return false;
      }
      this_curr = this_curr->next;
      other_curr = other_curr->next;
   }
   return true;
}

bool SortedList::operator!=(const SortedList& otherList) const {
   if (this->size() != otherList.size()) {
      return true;
   }

   Node* this_curr = m_head;
   Node* other_curr = otherList.m_head;
   while (this_curr != nullptr || other_curr != nullptr) {
      if (this_curr->data != other_curr->data) {
         return true;
      }
      this_curr = this_curr->next;
      other_curr = other_curr->next;
   }
   return false;
}

/** Called by insert method to prepend new item to the head of the list
@return true if item was inserted successfully*/
bool SortedList::insertFront(int item) {

   Node* curr_node = new Node;

   curr_node->data = item;
   curr_node->next = m_head;
   curr_node->prev = nullptr;

   if (m_head != nullptr) {
      m_head->prev = curr_node;
   }

   m_head = curr_node;

   return true;
}

/** append new item to the tail of the list
@return true if item was inserted successfully */
bool SortedList::insertBack(Node* tail_node, int item) {
   if (tail_node->next != nullptr) {
      return false;
   }
   
   Node* new_node = new Node;
   new_node->data = item;

   tail_node->next = new_node;
   new_node->prev = tail_node;

   return true;
}

/** Called by insert method to insert new item before a given node in the list 
that is not at the head of the list
@return true if item was inserted successfully */
bool SortedList::insertBefore(Node* curr_node, int item) {
   if (curr_node->prev != nullptr) {
      Node* new_node = new Node;
      new_node->data = item;

      new_node->next = curr_node;
      new_node->prev = curr_node->prev;
      curr_node->prev->next = new_node;
      curr_node->prev = new_node;
   }
   else {
      insertFront(item);
   }

   return true;
}

/** remove item at the head of the list
@return true if item was removed successfully */
bool SortedList::removeFront(Node* prev_node) {
   prev_node = m_head;
   m_head = m_head->next;
   m_head->prev = nullptr;
   delete prev_node;

   return true;
}

/** remove current Node that's not at head of list 
@return true if item was removed successfully */
bool SortedList::removeCurr(Node* prev_node, Node* curr_node) {
   prev_node->next = curr_node->next;

   // conditional for when removing node at end of list
   if (curr_node->next != nullptr) {
      curr_node->next->prev = prev_node;
   }
   delete curr_node;

   return true;

}

/** Creates a deep copy of the sorted list that is passed in (otherList).
A deep copy will create new Node objects for each Node in otherList and copy 
the data for each Node in the correct order. If otherList is empty, it will 
do nothing.*/
void SortedList::copyListNodes(const SortedList& otherList) {
   
   Node* other_list_curr = otherList.m_head;
   // copy first item new node to head
   if (other_list_curr != nullptr) {
      Node* new_node = new Node;

      new_node->data = other_list_curr->data;
      new_node->next = nullptr;
      new_node->prev = m_head;
      ++m_numItems;

      m_head = new_node;

      other_list_curr = other_list_curr->next;
   }
   // copy remaining items to new nodes
   Node* curr_node = m_head;
   while (other_list_curr != nullptr) {
      Node* new_node = new Node;
      new_node->data = other_list_curr->data;

      curr_node->next = new_node;
      new_node->prev = curr_node;

      curr_node = curr_node->next;
      other_list_curr = other_list_curr->next;
      ++m_numItems;
   }
}

// FRIENDS

/** Overloads the stream insertion operator to output the contents of a sorted list in order,
with each element separated by a space. Makes the operator<< method a friend to SortedList class.*/
std::ostream& operator<<(std::ostream& out, const SortedList& list) {
   list.display(out);
   return out;
}

/** Function overloads + and is defined outside of the SortedList class.
Used to merge two SortedLists (lhs and rhs), keeping all items in sorted order.
@return new merged SortedList. */
SortedList operator+(const SortedList& lhs, const SortedList& rhs) {
   
   SortedList mergedList;

   if (&lhs == nullptr && &rhs == nullptr) {
      return mergedList;
   }

   SortedList::Node* lhs_curr = lhs.m_head;
   SortedList::Node* rhs_curr = rhs.m_head;
   
   // for head, check if lhs data is <= rhs data
   if (lhs_curr != nullptr && lhs_curr->data <= rhs_curr->data) {
      SortedList::Node* new_node = new SortedList::Node;

      new_node->data = lhs_curr->data;
      new_node->next = nullptr;
      new_node->prev = mergedList.m_head;
      ++mergedList.m_numItems;

      mergedList.m_head = new_node;

      lhs_curr = lhs_curr->next;
   }
   // for head, check if rhs data is <= lhs data
   else if (rhs_curr != nullptr && rhs_curr->data <= lhs_curr->data) {
      SortedList::Node* new_node = new SortedList::Node;

      new_node->data = rhs_curr->data;
      new_node->next = nullptr;
      new_node->prev = mergedList.m_head;
      ++mergedList.m_numItems;

      mergedList.m_head = new_node;
      

      rhs_curr = rhs_curr->next;
   }

   SortedList::Node* ml_node = mergedList.m_head;
   while (lhs_curr != nullptr || rhs_curr != nullptr) {

      if (lhs_curr != nullptr) {
         // while lhs is smaller or equal rhs, keep adding nodes from lhs
         while (rhs_curr == nullptr || lhs_curr->data <= rhs_curr->data) {
            SortedList::Node* new_node = new SortedList::Node;
            new_node->data = lhs_curr->data;

            ml_node->next = new_node;
            new_node->prev = ml_node;

            // advance nodes
            ml_node = ml_node->next;
            lhs_curr = lhs_curr->next;
            ++mergedList.m_numItems;

            if (lhs_curr == nullptr) {
               break;
            }
         }
      }

      if (rhs_curr != nullptr) {
         // while rhs is smaller or equal rhs, keep adding nodes from rhs
         while (lhs_curr == nullptr || rhs_curr->data <= lhs_curr->data) {

            SortedList::Node* new_node = new SortedList::Node;
            new_node->data = rhs_curr->data;

            ml_node->next = new_node;
            new_node->prev = ml_node;

            // advance nodes
            ml_node = ml_node->next;
            rhs_curr = rhs_curr->next;
            ++mergedList.m_numItems;

            if (rhs_curr == nullptr) {
               break;
            }
         }
      }
   }
   return mergedList;
}
\$\endgroup\$
11
  • \$\begingroup\$ I don't see how a second link of the items will help merging two lists. And I'm not sure but I think this could be seen as a follow up from the last question you asked. If that's the case it's always nice to link to that. \$\endgroup\$ Nov 2, 2022 at 7:41
  • \$\begingroup\$ Time complexity of inserting n items into sorted list is O(n^2). Doing the same with two lists of length n1+n2=n and merging them is O(n1^2+n2^2+n) which is basically the same. Use a heap to reduce the complexity to O(n*log(n)). Or just keep them unsorted and sort them after merging. Or sort them first and then merge them. Those will all be linearitmic in time (assuming that's also the time complexity of the used sort method). \$\endgroup\$
    – slepic
    Nov 2, 2022 at 10:34
  • \$\begingroup\$ You forgot the rule of three. Code is broken if yo use an assignment operator. \$\endgroup\$ Nov 3, 2022 at 23:53
  • \$\begingroup\$ You should think about move semantics. \$\endgroup\$ Nov 3, 2022 at 23:53
  • \$\begingroup\$ If this is doubly linked. Why not have a head and tail in the SortedList class otherwise what is the point of the double linking. Double linking means you can traverse the list both ways but you only have one end to start from so you can only traverse it one way (you can go back I suppose). Look up Sentinal node. \$\endgroup\$ Nov 3, 2022 at 23:55

2 Answers 2

4
\$\begingroup\$

Overview

This use of a list does not need to be doubly linked.
You could just as easily have made this a singly linked list and it would not have changed the complexity. The use of a singly linked list would reduce the memory used by 1/3.

Works great for int. But lots of things can be sorted. Would be nice to generalize this with a template so you can keep a sorted list of any type of object.

You should expand to have the basic properties of a container (i.e. you need to add iterators).

  1. Use your own namespace for your code.
  2. Avoid magic numbers (-1).
    Create a named constant value.
  3. Use modern assignment operator form.
    See below.
  4. Learn the "Copy and Swap" idiom.
    It is the exception-safe optimal way to implement assignment. It is worth studying so you can spot similar patterns in the code.
  5. Use a sentinel value (here is an example)
    if you plan to keep using the doubly linked list. It solves all corner cases with head and avoids you needing to check for null pointers.
  6. Found 3 bugs.
    Move operators (constructor/assignment) broken.
    Undefined behavior because of a missing return.
  7. Bad Interface design:
    operator[] does not do what is expected.
  8. If you templatize this code for the data, then you will need to add move semantics for the value being inserted.

Code review

Why is this outside the include guards?

#include <iostream>

This is not portable.

#pragma once

I would use normal include guards. Most IDEs will do it for you nowadays.


This is a perfectly good idea. **BUT** is `-1` not a perfectly valid number that can be placed in the list?

How do you determine if it is a valid -1 or a -1 that indicates an out of range error? AVOID magic numbers.

   /** Overloads [] operator to find an index for a given item.
   First item in the list is at location 0.
   @return int index for a given value, -1 if item isn't found. */
   int operator[] (int item) const;

Most C++ containers would say it is undefined to access elements lower than zero or greater than or equal to size() (thus allowing for unchecked accesses). i.e. optimal access speed.

They usually also include an at() method for checked accesses that would throw for out of range index values.

Leaving the above comment (though it is wrong). Because it shows that misusing the built in operators do do things that are not expected is a bad idea. I expected this to get the itemth item in the list. But it searches the list for item.

Bad Interface design.
People are going to trip up on this. Because people don't read documentation.


Don't delete data before you have correctly copied the source.

   /** Overloaded assignment operator for deep copy. First deallocates memory for all of the Nodes (if any) in the 
   sorted list on the left-hand side before creating new Nodes for all Nodes in the sorted list on the 
   right-hand side and copying each data item. 
   @return the new lhs list. If the lhs and rhs lists are the same, it will do nothing. */

What happens if you start copying but there is an error?

In this situation, you are supposed to throw an exception. But if you do you have already released the original list, so your object has been modified. This means you don't provide the strong exception guarantee.

Strong Exception Guarantee: Either the operation works or the object is unmodified.


This is a bit old school.

   SortedList& operator=(const SortedList& rhs);
   SortedList& operator=(SortedList&& rhs) noexcept;

The modern way to do this:

   SortedList& operator=(SortedList rhs) noexcept;

Then you would implement like this:

   SortedList& operator=(SortedList rhs) noexcept
   {
       swap(rhs);
       return *this;
   }

Assuming you have implemented the Move constructor correctly, this works for both move and copy assignment optimally.

  SortedList   a;
  SortedList   b;

  a = b;             // This is now a standard copy and swap
  a = std::move(b);  // This moves the value to rhs.
                     // Then you swap rhs with the content of this.

  // in both cases the destructor of rhs handles the cleanup
  // of the original value in `a`

You have a bug here.

// move constructor
SortedList::SortedList(SortedList&& rhs) noexcept {
   m_numItems = rhs.m_numItems;
   m_head = rhs.m_head;
   rhs.m_head = nullptr;
}

Think about this situation:

SortedList   a;
a.insert(1)

SortedList   b(std::move(a));

a.insert(2);
std::cout << "A Size: " << a.size() << " ?\n"; // why does it print 2.
std::cout << a << "\n";                        // when this has one element.

Don't use this->.

SortedList::~SortedList() {
   this->clear();
}

The only reason to use this-> is to disambiguate something.


Personally, for one-liners like this I would just leave in the header file. There is no need to have the implementation in the source file.

int SortedList::size() const {
   return m_numItems;
}
bool SortedList::empty() const {
   return m_head == nullptr;
}

Comment rot is a real thing.

/** Output the contents of a sorted list in order,
with each element separated by a space.*/
void SortedList::display(std::ostream& out) const {

Don't write the same thing in the header and source file. Write it once in one place. Otherwise you need to keep both versions in sync and that will not happen. Over time they will become out of sync. Then which do you believe?


Prefer "\n" over std::endl.

   out << std::endl;

You don't want to force a flush every time!


bool SortedList::insert(int item) {

   .... 

   insertBack(prev_node, item);
   ++m_numItems;
   // Forgot your return statement
}

Turn on all your compiler warnings and turn on the setting that treats them like errors. All warnings are logical errors in your thinking.

For g++ use -Wall -Wextra -Werror.

PS. This function always returns true at the moment.

I would expect it to return false if the value is already in the list or something like that.


/**
.....    
Reduces m_numItems by 1 */

It's obvious. But you should probably say reduces by 1 if an item is removed.


bool SortedList::remove(int item) {

    .....

            return true;
         }
         else {

This else is redundant. If the associated if() fired then you hit the above return statement.


void SortedList::clear()
{
   ....
   while(...) {
      ...
      --m_numItems;
      ....
   }

Seems like an expensive way of saying:

   m_numItems = 0;

Use the "Copy and Swap" Idiom.

SortedList& SortedList::operator=(const SortedList& rhs) {
   if (this != &rhs) {
      this->clear();
      copyListNodes(rhs);
   }
   return *this;
}

Checking for assignment to self is a code pessimization.


Broken in the same way as the move constructor.

SortedList& SortedList::operator=(SortedList&& rhs) noexcept {
   m_numItems = rhs.m_numItems;
   m_head = rhs.m_head;
   rhs.m_head = nullptr;

   return *this;
}

Your don't reset the m_numItems on rhs. Remember that rhs must be in a valid state.

After moving from an object, the source of the move may return a non-zero value from size() but a call to empty() would return true.


   // We have already established that the lists are the same size.
   // So if `this_curr` is not nullptr then `other_curr` is not nullptr
   // I suppose this protects against bugs in the code. But if your 
   // objects are already invalid because of a bug you want it to blow up sooner rather than later.    
   while (this_curr != nullptr || other_curr != nullptr) {

Don't repeat code.

bool SortedList::operator!=(const SortedList& otherList) const {

You should implement the != in terms of the == operator.

bool SortedList::operator!=(const SortedList& otherList) const {
    return !(*this == otherList);
}

You can simplify this:

   Node* curr_node = new Node;

   curr_node->data = item;
   curr_node->next = m_head;
   curr_node->prev = nullptr;

It is the same as:

   Node* curr_node = new Node{item, null, null};

In fact I would simplify to:

bool SortedList::insertFront(int item) {

    m_head = new Node{item, nullptr, m_head};
    if (m_head->next) {
        m_head->next->prev = m_head;
    }
    return true;
}

Lets simplify:

bool SortedList::insertBack(Node* tail_node, int item) {
   if (tail_node->next != nullptr) {
      return false;
   }
   
   tail_node->next = new Node{item, tail_node, nullptr};
   return true;
}

bool SortedList::insertBefore(Node* curr_node, int item) {

   // Don't you already do this check before calling insertBefore()?
   // Looks like you are doing the same check in two places.
   // I would remove it from one place.
   if (curr_node->prev != nullptr) {

       .....

   }
   else {
      insertFront(item);
   }

   return true;
}

void SortedList::copyListNodes(const SortedList& otherList) {
   
   Node* other_list_curr = otherList.m_head;
   // copy first item new node to head
   if (other_list_curr != nullptr) {
      Node* new_node = new Node;

      new_node->data = other_list_curr->data;
      new_node->next = nullptr;
      new_node->prev = m_head;
      ++m_numItems;

      m_head = new_node;

      other_list_curr = other_list_curr->next;
   }
   // copy remaining items to new nodes
   Node* curr_node = m_head;
   while (other_list_curr != nullptr) {
      Node* new_node = new Node;
      new_node->data = other_list_curr->data;

      curr_node->next = new_node;
      new_node->prev = curr_node;

      curr_node = curr_node->next;
      other_list_curr = other_list_curr->next;
      ++m_numItems;
   }
}

Seems very convoluted. I would change it. So it returns a new list.

Node* SortedList::copyNode(Node* result, Node*& end, Node const* src) {
    Node* next = new Node{src->data, end, nullptr);
    if (end) {
        end->next = next;
    }
    end = next;
    return result == nullptr ? next : result;
}

Node* SortedList::copyList(Node const* other) {
    Node* result = nullptr;
    Node* endOfList = nullptr;
    while (other != nullptr) {
        result = copyNode(result, endOfList, other);
        other = other->next;
    }
    return result;
}

SortedList operator+(const SortedList& lhs, const SortedList& rhs) {

   ......


   // THIS CAN NEVER BE TRUE.
   // IT IS ILLEGAL TO CONVERT A nullptr INTO A REFERENCE.       
   if (&lhs == nullptr && &rhs == nullptr) {
      return mergedList;
   }

The rest of this function is far too complicated.

// Non optimal but simpleway.
SortedList operator+(const SortedList& lhs, const SortedList& rhs) {

    SortedList mergedList(lhs);
    for (Node const* loop = rhs.m_head; loop; loop=loop->next) {
        mergedList.insert(loop->data);
    }
}


// More optimal way.
SortedList operator+(const SortedList& lhs, const SortedList& rhs) {

    Node const*  lhsData = lhs.m_head;
    Node const&  rhsData = rhs.m_head;

    Node* result = nullptr;
    Node* endOfList = nullptr;

    // While there are values in both lists
    // Then we have to choose which to copy next.
    while (lhsData != nullptr && rhsData != nullptr) {
         Node next;
         if (lhsData->data < rhsData->data) {
             next = lhsData;
             lhsData = lhsData->next;
         }
         else {
             next = rhsData;
             rhsData = rhsData->next;
         }
         // See above
         result = copyNode(result, endOfList, next);
    }
    // One of the lists is now empty.
    // SO only one of these loops will be used.
    // We just need to loop through the remaining items
    // and add them to the list.
    for (;lhsData; lhsData = lhsData->next) {
        result = copyNode(result, endOfList, lhsData);
    }
    for (;rhsData; rhsData = rhsData->next) {
        result = copyNode(result, endOfList, rhsData);
    }
    return result;
}
   
\$\endgroup\$
4
  • \$\begingroup\$ Thanks for the feedback. Learned a lot. \$\endgroup\$
    – Hofbr
    Nov 5, 2022 at 20:26
  • \$\begingroup\$ If I’m leaving a short function in the header file (often necessary for template functions), its good practice to declare it static, so the linker will not get confused about multiple extern functions with the same name. I also normally declare short functions like that constexpr or inline. \$\endgroup\$
    – Davislor
    Nov 6, 2022 at 4:19
  • \$\begingroup\$ @Davislor Careful. If you use static you change the meaning of the function significantly and for the above functions will break them. If you leave them as one liners inside the class declaration, then inline becomes redundant. The keyword constexpr has a very defined meaning not sure it applies here. \$\endgroup\$ Nov 8, 2022 at 16:53
  • \$\begingroup\$ @MartinYork I should’ve distinguished between functions without external linkage and static member functions, which as you say have a different meaning. \$\endgroup\$
    – Davislor
    Nov 8, 2022 at 22:44
3
\$\begingroup\$

A bug

When:

SortedList l;
l.insert(1);
l.insert(3);
l.display(); // Will print: "1 ->"

Your SortedList::insert(int data) will not insert the data when that data is inserted to a non-empty list and that data is larger than any element in the list. You need to keep track of the previously iterated node, and finally insert after that previous node. (See Alternative implementation.)

Advice 1

In SortedList.h, you have

#include <iostream>

#pragma once

I suggest you revert the order. That way <iostream> is included only once and not at the second occasion.

Advice 2

m_numItems is not used. Remove it.

Advice 3

Often, you write:

Node* curr_node = new Node;

curr_node->data = item;

Why not provide the Node a constructor that takes the data?

Advice 4

Node* m_head;

I would rename to simply head.

Advice 5

In SortedList.cpp, you write:

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

This will attempt to include (in your version) <iostream> twice. Revert the order.

Advice 6

Your insertion methods are declared as returning bool values, but the only value returned is true. I would declare those methods as void.

Advice 7 Use \n instead of std::endl; this works faster.

Advice 8 I would wrap your list impelementation into a custom namespace. For example:

namespace your::company::util {

    class SortedList {
        ...
    };

}

Alternative implementation

All in all, I had this in mind:

SortedList.h:

#pragma once

#include <iostream>

class SortedList
{

    struct Node 
    {
        int data = 0;
        Node* prev = nullptr;
        Node* next = nullptr;

        Node(int data) : data{ data }, 
                         prev{ nullptr },
                         next{ nullptr } {}
    };

private:
    Node* head;

public:
    SortedList();
    ~SortedList();

    void insert(int item);
    void display(std::ostream& out) const;
    void clear();

private:
    void insertFront(int item);
    void insertBefore(Node* node, int item);
    void insertBack(Node* tail, int item);
};

std::ostream& operator<<(std::ostream& os, SortedList const& list);

SortedList.cpp:

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

SortedList::SortedList() {
    head = nullptr;
}

SortedList::~SortedList() {
    clear();
}

void SortedList::insert(int item) {

    Node* curr = head;

    if (curr == nullptr) {
        insertFront(item);
        return;
    }

    Node* previous_node = nullptr;

    while (curr != nullptr) {
        if (item <= curr->data) {
            insertBefore(curr, item);
            return;
        }

        previous_node = curr;
        curr = curr->next;
    }

    insertBack(previous_node, item);
}

void SortedList::insertBack(Node* tail, int item) {
    Node* new_node = new Node(item);
    tail->next = new_node;
    new_node->prev = tail;
}

void SortedList::insertFront(int item) {
    Node* new_node = new Node(item);

    if (head != nullptr) {
        new_node->next = head;
        head->prev = new_node;
    }

    head = new_node;
}

void SortedList::insertBefore(Node* node, int item) {
    if (node->prev != nullptr) {
        Node* new_node = new Node(item);

        new_node->next = node;
        new_node->prev = node->prev;
        node->prev->next = new_node;
        node->prev = new_node;
    } else {
        insertFront(item);
    }
}

void SortedList::display(std::ostream& out) const {
    Node* curr = head;

    while (curr) {
        std::cout << curr->data;

        if (curr->next != nullptr) {
            std::cout << " -> ";
        }

        curr = curr->next;
    }
}

void SortedList::clear()
{
    Node* current = head;

    while (current) {
        Node* next = current->next;
        delete current;
        current = next;
    }

    head = nullptr;
}

std::ostream& operator<<(std::ostream& os, SortedList const& list) {
    list.display(os);
    return os;
}

main.cpp:

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

int main(void)
{
    SortedList list;

    list.insert(3);
    list.insert(1);
    list.insert(5);
    list.insert(4);
    list.insert(2);

    std::cout << list << "\n";
    return 0;
}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ There is no need for such Node constructor. Node{5} works just as well without that. And will you add information about the bug you fixed with the added insertBack()? \$\endgroup\$ Nov 2, 2022 at 7:22
  • \$\begingroup\$ inserttBack(): if you add 1 and then, say, 3, 3 will be omitted and the list will remain <1>. \$\endgroup\$
    – coderodde
    Nov 2, 2022 at 8:00
  • \$\begingroup\$ I tried the code as is and the insertBack() solved the case where SortedList::insert(int data) will not insert the data when that data is inserted to a non-empty list and that data is larger than any element in the list. this worked for me. Thanks for catching @coderodde \$\endgroup\$
    – Hofbr
    Nov 2, 2022 at 18:19
  • \$\begingroup\$ Forgot the rule of three (like the OP's code). \$\endgroup\$ Nov 3, 2022 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.