1 files changed, 266 insertions, 0 deletions
diff --git a/Bachelor/Prog2/SortedList/list.h b/Bachelor/Prog2/SortedList/list.h
new file mode 100644
index 0000000..f50f6db
--- /dev/null
+++ b/Bachelor/Prog2/SortedList/list.h
@@ -0,0 +1,266 @@
+// Template List class definition
+
+#ifndef LIST_H
+#define LIST_H
+
+#include <iostream>
+using std::cout;
+
+#include <new>
+
+#include "listnode.h"  // ListNode class definition
+
+template< class NODETYPE >
+class List {
+
+public:
+   List();
+   ~List();
+   void insertInOrder( const NODETYPE &value );
+   bool removeFromFront( NODETYPE & );
+   bool removeFromBack( NODETYPE & );
+   bool deleteNode( const NODETYPE &, NODETYPE & );
+   bool isEmpty() const;
+   void print() const;
+
+private:
+   void insertAtFront( const NODETYPE & );
+   void insertAtBack( const NODETYPE & );
+
+   ListNode< NODETYPE > *firstPtr;  // pointer to first node
+   ListNode< NODETYPE > *lastPtr;   // pointer to last node
+
+}; // end class List
+
+// default constructor
+template< class NODETYPE >
+List< NODETYPE >::List() 
+   : firstPtr( 0 ), 
+     lastPtr( 0 ) 
+{ 
+   // empty body
+
+} // end List constructor
+
+// destructor
+template< class NODETYPE >
+List< NODETYPE >::~List()
+{
+   if ( !isEmpty() ) {    // List is not empty
+      cout << "Destroying nodes ...\n";
+
+      ListNode< NODETYPE > *currentPtr = firstPtr;
+      ListNode< NODETYPE > *tempPtr;
+
+      while ( currentPtr != 0 ) {  // delete remaining nodes
+         tempPtr = currentPtr;
+         cout << tempPtr->data << '\n';
+         currentPtr = currentPtr->nextPtr;
+         delete tempPtr;
+
+      } // end while
+
+   } // end if
+
+   cout << "All nodes destroyed\n\n";
+
+} // end List destructor
+
+// insert node at front of list
+template< class NODETYPE >
+void List< NODETYPE >::insertAtFront( const NODETYPE &value )
+{
+   ListNode< NODETYPE > *newPtr = new ListNode< NODETYPE >( value );
+
+   if ( isEmpty() )  // List is empty
+      firstPtr = lastPtr = newPtr;
+
+   else {  // List is not empty
+      newPtr->nextPtr = firstPtr;
+      firstPtr = newPtr;
+
+   } // end else
+
+} // end function insertAtFront
+
+// insert node at back of list
+template< class NODETYPE >
+void List< NODETYPE >::insertAtBack( const NODETYPE &value )
+{
+   ListNode< NODETYPE > *newPtr = new ListNode< NODETYPE >( value );
+
+   if ( isEmpty() )  // List is empty
+      firstPtr = lastPtr = newPtr;
+
+   else {  // List is not empty
+      lastPtr->nextPtr = newPtr;
+      lastPtr = newPtr;
+
+   } // end else
+
+} // end function insertAtBack
+
+// delete node from front of list
+template< class NODETYPE >
+bool List< NODETYPE >::removeFromFront( NODETYPE &value )
+{
+   if ( isEmpty() )  // List is empty
+      return false;  // delete unsuccessful
+
+   else {  
+      ListNode< NODETYPE > *tempPtr = firstPtr;
+
+      if ( firstPtr == lastPtr )
+         firstPtr = lastPtr = 0;
+      else
+         firstPtr = firstPtr->nextPtr;
+
+      value = tempPtr->data;  // data being removed
+      delete tempPtr;
+
+      return true;  // delete successful
+
+   } // end else
+
+} // end function removeFromFront
+
+// delete node from back of list
+template< class NODETYPE >
+bool List< NODETYPE >::removeFromBack( NODETYPE &value )
+{
+   if ( isEmpty() )
+      return false;  // delete unsuccessful
+
+   else {
+      ListNode< NODETYPE > *tempPtr = lastPtr;
+
+      if ( firstPtr == lastPtr )
+         firstPtr = lastPtr = 0;
+      else {
+         ListNode< NODETYPE > *currentPtr = firstPtr;
+
+         // locate second-to-last element
+         while ( currentPtr->nextPtr != lastPtr )
+            currentPtr = currentPtr->nextPtr;
+
+         lastPtr = currentPtr;
+         currentPtr->nextPtr = 0;
+
+      } // end else
+
+      value = tempPtr->data;
+      delete tempPtr;
+
+      return true;  // delete successful
+
+   } // end else
+
+} // end function removeFromBack
+
+
+// insert node in sorted order
+template< class NODETYPE >
+void List< NODETYPE >::insertInOrder( const NODETYPE &value )
+{
+   if ( isEmpty() ) {
+      ListNode< NODETYPE > *newPtr = new ListNode< NODETYPE >( value );
+      firstPtr = lastPtr = newPtr;
+   }
+   else {
+      if( firstPtr->data >= value)
+         insertAtFront( value );
+      else if( lastPtr->data < value)
+         insertAtBack( value );
+      else {
+         ListNode< NODETYPE > *currentPtr = firstPtr->nextPtr,
+                              *previousPtr = firstPtr,
+                              *newPtr = new ListNode< NODETYPE >( value );
+
+         // locate element before new node gets inserted
+         while ( currentPtr != lastPtr && currentPtr->data < value ) {
+            previousPtr = currentPtr;
+            currentPtr = currentPtr->nextPtr;
+         }
+
+         previousPtr->nextPtr = newPtr;
+         newPtr->nextPtr = currentPtr;
+
+      } // end else
+
+   } // end else
+
+} // end function insertInOrder
+
+// delete a node from anywhere in the list
+template< class NODETYPE >
+bool List< NODETYPE >::deleteNode( const NODETYPE &value, NODETYPE &deletedVal )
+{
+   if ( isEmpty() )
+      return false;   // delete unsuccessful
+   else {
+      if ( firstPtr->data == value ) {
+         removeFromFront( deletedVal );
+         return true;  // delete successful
+      }
+      else if ( lastPtr->data == value ) {
+         removeFromBack( deletedVal );
+         return true;  // delete successful
+      }
+      else {
+         ListNode< NODETYPE > *currentPtr = firstPtr->nextPtr,
+                              *previousPtr = firstPtr;
+
+         while ( currentPtr != lastPtr && currentPtr->data < value ) {
+            previousPtr = currentPtr;
+            currentPtr = currentPtr->nextPtr;
+         }
+
+         if ( currentPtr->data == value ) {
+            ListNode< NODETYPE > *tempPtr = currentPtr;
+            deletedVal = currentPtr->data;
+            previousPtr = currentPtr->nextPtr;
+            delete tempPtr;
+            return true;  // delete successful
+         }
+         else
+            return false;  // delete unsuccessful
+
+      } // end else
+
+   } // end else
+
+} // end function deleteNode
+
+// is List empty?
+template< class NODETYPE > 
+bool List< NODETYPE >::isEmpty() const 
+{ 
+   return firstPtr == 0; 
+   
+} // end function isEmpty
+
+// display contents of List
+template< class NODETYPE >
+void List< NODETYPE >::print() const
+{
+   if ( isEmpty() ) {
+      cout << "The list is empty\n\n";
+      return;
+
+   } // end if
+
+   ListNode< NODETYPE > *currentPtr = firstPtr;
+
+   cout << "The list is: ";
+
+   while ( currentPtr != 0 ) {
+      cout << currentPtr->data << ' ';
+      currentPtr = currentPtr->nextPtr;
+
+   } // end while
+
+   cout << "\n\n";
+
+} // end function print
+
+#endif
+\ No newline at end of file