Source of insertSorted.cpp

Structures and functions

  1: //  Created by Frank M. Carrano and Timothy M. Henry.
  2: //  Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.

  4: template<class ItemType>
  5: void LinkedSortedList<ItemType>::insertSorted(const ItemType& newEntry)
  6: {
  7:    auto newNodePtr(std::make_shared<Node<ItemType>>(newEntry));
  8:    auto prevPtr = getNodeBefore(newEntry);
  9:    
 10:    if (isEmpty() || (prevPtr == nullptr)) // Add at beginning
 11:    {
 12:       newNodePtr–>setNext(headPtr);
 13:       headPtr = newNodePtr;
 14:    }
 15:    else                                   // Add after node before
 16:    {
 17:       auto aftPtr = prevPtr–>getNext();
 18:       newNodePtr–>setNext(aftPtr);
 19:       prevPtr–>setNext(newNodePtr);
 20:    } // end if
 21:    
 22:    itemCount++;
 23:    return true;
 24: }  // end insertSorted

 26: template<class ItemType>
 27: auto LinkedSortedList<ItemType>::
 28:      getNodeBefore(const ItemType& anEntry) const
 29: {
 30:    auto curPtr = headPtr;
 31:    std::shared_ptr<Node<ItemType>> prevPtr;
 32:    
 33:    while ( (curPtr != nullptr) && (anEntry > curPtr–>getItem()) )
 34:    {
 35:       prevPtr = curPtr;
 36:       curPtr = curPtr–>getNext();
 37:    }  // end while
 38:    
 39:    return prevPtr;
 40: }  // end getNodeBefore