// List_step1.cpp // // 2013-05-08 //
// design a struct to hold data and a 'next' address i.e. a link to 'next' Node
// here, at step 1, we will just be holding, for the data, an int ...
// NOTE how C++ facilites, via a constructor, assigning initial values ...
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* next;
// ctor ... handles both cases of default ctor and value passed ctor ...
// if call Node myNode; in your program, default value for int data is 0
// if call Node myNode(7); in your program, default value for int data is 7
// Note that the value assigned to next is NULL in both of the above cases
Node( int dt = 0 ) : data(dt), next(NULL) {}
};
void print( const Node* cur )
{
cout << cur->data;
}
// NOTE below that head is a pointer to Node
// AND updated by being passed in (and back) by C++ reference style passing
void push_back( Node*& head, int n )
{
Node* newNode = new Node( n );
Node* cur = head;
if( cur ) // not first node
{
while( cur )
{
if( cur->next == NULL )
{
cur->next = newNode;
return;
}
else cur = cur->next;
}
}
else head = newNode;
}
//delete specific item ...
void deleteItem( Node*& head, int item )
{
Node* cur = head; // get copy
Node* prev = NULL;
while( cur )
{
if( cur->data == item ) break;
prev = cur;
cur = cur->next;
}
// test end conditions ...
if( cur ) // was found
{
if( prev ) // was not first node, so prev and cur exist
{
prev->next = cur->next; // skip over cur ...
delete cur;
}
else // was first node
{
head = head->next;
delete cur;
}
}
else cout << "\nNot found ...\n";
}
void printAll( const Node* cur )
{
if( !cur )
{
cout << "\nThe list is empty ... so can't print anything ...\n";
return;
}
while( cur )
{
print( cur );
cout << " ";
cur = cur->next;
}
cout << endl;
}
void clean( Node*& cur ) // updated head to NULL when done
{
while( cur )
{
Node* delNode = cur;
cur = cur->next;
delete delNode;
}
}
int main()
{
// NOTE! 'head' MUST be initialled to NULL for push_back etc to work ... //
Node* head = NULL;
push_back( head, 10 );
push_back( head, 30 );
push_back( head, 20 );
push_back( head, 40 );
printAll( head );
cout << "\ndeleting 20 ... \n";
deleteItem( head, 20 );
printAll( head );
cout << "\ndeleting 10 ... \n";
deleteItem( head, 10 );
printAll( head );
cout << "\nclean list ... \n";
clean( head );
printAll( head );
cout << "\nPress 'Enter' to continue/exit ... " << flush;
cin.get();
}
// List_step2.cpp // // 2013-05-08 //
// Note that here we add a struct 'List' to hold (to track)
// the head and tail addresses ... (of the Node struct's in our List)
// we also track the size (i.e the length of the List)
// NOTE that we have moved our functions that work on our List to now being
// inside the C++ struct List (namespace)
// And since we have data members head, tail and size declared inside our List,
// we do NOT have to pass these values (back and forth now) to the List
// member functions ... since these List member functions have access to these
// data mambers as if they were 'global valiables' ...
// but with the 'global scope of access limited now' ... to just be available
// to things inside a 'List::' scoped namespace
#include <iostream>
using namespace std;
struct Node
{
int val;
Node* next;
// default ctor ...and value passed in ...ctor(s)...
// (this code handles both)
// Note initialization list and how default values are handled here...
Node( int vl = 0 ) : val( vl ), next( NULL ) {}
// can define functions inside a C++ struct (or class)
// to work on 'this' data inside 'this' Node ... if we wish
void print() const
{
cout << val;
}
} ;
struct List
{
Node* head;
Node* tail;
int size;
// default ctor with initialization list ...
List() : head( NULL ), tail( NULL ), size( 0 ) {}
~List() { clear() ; }
void push_back( int val );
void push_front( int val );
// erase FIRST node with this val (if it exists in list)
bool erase( int val );
void print() const ;
void clear();
int get_size() const { return size; }
} ;
void List::push_back( int val )
{
Node* newNode = new Node( val );
if( size ) // then newNode not first node
{
tail->next = newNode;
tail = newNode;
}
else head = tail = newNode;
++ size;
}
void List::push_front( int val )
{
Node* newNode = new Node( val );
newNode->next = head;
head = newNode; // can now update head ...
if( ++size == 1 ) tail = newNode;
}
bool List::erase( int val ) // erase FIRST node with this val (if it exists in list)
{
Node* cur = head; // get copy
Node* prev = NULL;
while( cur )
{
if( cur->val == val ) break;
prev = cur;
cur = cur->next;
}
// test end conditions ...
if( cur ) // was found
{
if( prev ) // was not first node, so prev and cur exist
prev->next = cur->next; // skip over cur ...
else // was first node
head = head->next;
if( cur == tail ) tail = prev;
delete cur;
-- size;
return true; // was erased ...
}
// else cout << "\nNot found ...\n";
return false;
}
void List::print() const
{
if( !head )
{
cout << "\nThe list is empty ... so can't print anything ...\n";
return;
}
Node* cur = head;
while( cur )
{
cur->print();
cout << " ";
cur = cur->next;
}
cout << endl;
}
void List::clear()
{
Node* cur;
while( head )
{
cur = head;
head = head->next; // head set to NULL at end of loop //
delete cur;
}
tail = NULL;
size = 0;
}
int main()
{
List myLst;
myLst.push_back( 10 );
myLst.push_back( 30 );
myLst.push_back( 20 );
myLst.push_back( 40 );
myLst.print();
cout << "\ndeleting 20 ... \n";
myLst.erase( 20 );
myLst.print();
cout << "\ndeleting 40 ... \n";
myLst.erase( 40 );
myLst.print();
cout << "\nclear list ... \n";
myLst.clear();
myLst.print();
cout << "\nPress 'Enter' to continue/exit ... " << flush;
cin.get();
}
// List_step3.cpp // // 2013-05-08 //
// Note: here we have moved our struct Node inside
// NOW using class List (instead of struct list ...
// Note: public and private labels and sections ...
// to limit public access to public parts ...
// So here ... struct Node is defined inside List (and as) private wrt List ...
// So access to Node is, NOW HERE, limited to inside the List:: scope ...
// Note: public access is available by (and linmited by) ... the ...
// List public member functions
// Note also, that here we have moved our definitions to all be inside ...
// the List declaration ... just to show this alternative coding style ...
// so that, now by default ... we ask ...
// the compuler to generate 'inline function calls' ...
// for all these function calls,
// whenever they are called now, from our program
#include <iostream>
using namespace std;
class List
{
public:
// default ctor with initialization list ...
List() : head( 0 ), tail( 0 ), size( 0 ) {}
~List() { clear() ; }
void push_back( int val )
{
Node* newNode = new Node( val );
if( size ) // then newNode not first node
{
tail->next = newNode;
tail = newNode;
}
else head = tail = newNode;
++ size;
}
void push_front( int val )
{
Node* newNode = new Node( val );
newNode->next = head;
head = newNode; // can now update head ...
if( ++size == 1 ) tail = newNode;
}
bool erase( int val ) // erase FIRST node with this val (if it exists in list)
{
Node* cur = head; // get copy
Node* prev = 0;
while( cur )
{
if( cur->val == val ) break;
prev = cur;
cur = cur->next;
}
// test end conditions ...
if( cur ) // was found
{
if( prev ) // was not first node, so prev and cur exist
prev->next = cur->next; // skip over cur ...
else // was first node
head = head->next;
if( cur == tail ) tail = prev;
delete cur;
-- size;
return true; // was erased ...
}
// else cout << "\nNot found ...\n";
return false;
}
void print() const
{
if( !head )
{
cout << "\nThe list is empty ... so can't print anything ...\n";
return;
}
Node* cur = head;
while( cur )
{
cur->print();
cout << ", ";
cur = cur->next;
}
cout << "the size now is " << size << endl;
}
void clear()
{
Node* cur;
while( head )
{
cur = head;
head = head->next; // head set to 0 at end of loop //
delete cur;
}
tail = 0;
size = 0;
}
int get_size() const { return size; }
private:
struct Node
{
int val;
Node* next;
// default ...and value passed in ...ctor(s)... (this code handles both)
// Note initialization list and how default values are handled here...
Node( int vl = 0 ) : val( vl ), next( 0 ) {}
void print() const
{
cout << val;
}
} ;
Node* head;
Node* tail;
int size;
} ;
int main()
{
List myLst;
myLst.push_back( 10 );
myLst.push_back( 30 );
myLst.push_back( 20 );
myLst.push_back( 40 );
myLst.print();
cout << "\ndeleting 20 ... \n";
myLst.erase( 20 );
myLst.print();
cout << "\ndeleting 40 ... \n";
myLst.erase( 40 );
myLst.print();
cout << "\nclear list ... \n";
myLst.clear();
myLst.print();
cout << "\nNow myLst.get_size() = " << myLst.get_size();
cout << "\n\nPress 'Enter' to continue/exit ... " << flush;
cin.get();
}
// List_step4.cpp // // 2013-05-08 //
// Note that here we have added a copy constructor and overloaded operator =
#include <iostream>
using namespace std;
class List
{
public:
// default ctor with initialization list ...
List() : head( 0 ), tail( 0 ), size( 0 ) {}
~List() { clear() ; }
List( const List& old )
{
head = tail = 0;
size = 0;
Node* cur = old.head;
while( cur ) { push_back( cur->val ); cur = cur->next; }
}
List& operator = ( const List& old )
{
if( this != &old )
{
clear();
//head = tail = 0;
//size = 0;
Node* cur = old.head;
while( cur ) { push_back( cur->val ); cur = cur->next; }
}
return *this;
}
void push_back( int val )
{
Node* newNode = new Node( val );
if( size ) // then newNode not first node
{
tail->next = newNode;
tail = newNode;
}
else head = tail = newNode;
++ size;
}
void push_front( int val )
{
Node* newNode = new Node( val );
newNode->next = head;
head = newNode; // can now update head ...
if( ++size == 1 ) tail = newNode;
}
bool erase( int val ) // erase FIRST node with this val (if it exists in list)
{
Node* cur = head; // get copy
Node* prev = 0;
while( cur )
{
if( cur->val == val ) break;
prev = cur;
cur = cur->next;
}
// test end conditions ...
if( cur ) // was found
{
if( prev ) // was not first node, so prev and cur exist
prev->next = cur->next; // skip over cur ...
else // was first node
head = head->next;
if( cur == tail ) tail = prev;
delete cur;
-- size;
return true; // was erased ...
}
// else cout << "\nNot found ...\n";
return false;
}
void print() const
{
if( !head )
{
cout << "\nThe list is empty ... so can't print anything ...\n";
return;
}
Node* cur = head;
while( cur )
{
cur->print();
cout << " ";
cur = cur->next;
}
cout << endl;
}
void clear()
{
Node* cur;
while( head )
{
cur = head;
head = head->next; // head set to 0 at end of loop //
delete cur;
}
tail = 0;
size = 0;
}
int get_size() const { return size; }
private:
struct Node
{
int val;
Node* next;
// default ...and value passed in ...ctor(s)... (this code handles both)
// Note initialization list and how default values are handled here...
Node( int value = 0 ) : val( value ), next( 0 ) {}
void print() const
{
cout << val;
}
} ;
Node* head;
Node* tail;
int size;
} ;
int main()
{
List myLst;
myLst.push_back( 10 );
myLst.push_back( 30 );
myLst.push_back( 20 );
myLst.push_back( 40 );
cout << "Showing myLst ...\n";
myLst.print();
List myLst2 = myLst;
cout << "\ndeleting 20 ... \n";
myLst.erase( 20 );
cout << "Showing myLst ...\n";
myLst.print();
cout << "\ndeleting 40 ... \n";
myLst.erase( 40 );
cout << "Showing myLst ...\n";
myLst.print();
cout << "\nclear list ... \n";
myLst.clear();
cout << "Showing myLst ...\n";
myLst.print();
cout << "\nShowing myLst2 ...\n";
myLst2.print();
cout << "\nPress 'Enter' to continue/exit ... " << flush;
cin.get();
}
// List_step5.cpp // // 2013-05-08 //
// Note that here we have moved out class List (of int) code
// ... into a separate .h file
#include "classList_SLL.h"
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
List myLst;
myLst.push_back( 10 );
myLst.push_back( 30 );
myLst.push_back( 20 );
myLst.push_back( 40 );
cout << "Showing myLst ...\n";
myLst.print();
List myLst2 = myLst;
cout << "\ndeleting 20 ... \n";
myLst.erase( 20 );
cout << "Showing myLst ...\n";
myLst.print();
cout << "\ndeleting 40 ... \n";
myLst.erase( 40 );
cout << "Showing myLst ...\n";
myLst.print();
cout << "\nclear list ... \n";
myLst.clear();
cout << "Showing myLst ...\n";
myLst.print();
cout << "\nShowing myLst2 ...\n";
myLst2.print();
cout << "\nPress 'Enter' to continue/exit ... " << flush;
cin.get();
}
// classList_SLL.h // // 2013-05-07 //
#ifndef CLASSLIST_SLL_H
#define CLASSLIST_SLL_H
#include <iostream>
class List
{
public:
// default ctor with initialization list ...
List() : head( NULL ), tail( NULL ), size( 0 ) {}
~List() { clear() ; }
List( const List& old ); // copy ctor ...
List& operator = ( const List& old ); // overloaded =
void push_back( int val );
void push_front( int val );
bool erase( int val ); // erase FIRST node with this val (if it exists in list)
void print() const ;
void clear();
int get_size() const { return size; }
private:
struct Node
{
int val;
Node* next;
// default ...and value passed in ...ctor(s)... (this code handles both)
// Note initialization list and how default values are handled here...
Node( int vl = 0 ) : val( vl ), next( NULL ) {}
void print() const
{
std::cout << val;
}
} ;
Node* head;
Node* tail;
int size;
} ;
List::List( const List& old )
{
head = tail = NULL;
size = 0;
Node* cur = old.head;
while( cur ) { push_back( cur->val ); cur = cur->next; }
}
List& List::operator = ( const List& old )
{
if( this != &old )
{
clear();
//head = tail = NULL;
//size = 0;
Node* cur = old.head;
while( cur ) { push_back( cur->val ); cur = cur->next; }
}
return *this;
}
void List::push_back( int val )
{
Node* newNode = new Node( val );
if( size ) // then newNode not first node
{
tail->next = newNode;
tail = newNode;
}
else head = tail = newNode;
++ size;
}
void List::push_front( int val )
{
Node* newNode = new Node( val );
newNode->next = head;
head = newNode; // can now update head ...
if( ++size == 1 ) tail = newNode;
}
bool List::erase( int val ) // erase FIRST node with this val (if it exists in list)
{
Node* cur = head; // get copy
Node* prev = NULL;
while( cur )
{
if( cur->val == val ) break;
prev = cur;
cur = cur->next;
}
// test end conditions ...
if( cur ) // was found
{
if( prev ) // was not first node, so prev and cur exist
prev->next = cur->next; // skip over cur ...
else // was first node
head = head->next;
if( cur == tail ) tail = prev;
delete cur;
-- size;
return true; // was erased ...
}
// else cout << "\nNot found ...\n";
return false;
}
void List::print() const
{
if( !head )
{
std::cout << "\nThe list is empty ... so can't print anything ...\n";
return;
}
Node* cur = head;
while( cur )
{
cur->print();
std::cout << " ";
cur = cur->next;
}
std::cout << std::endl;
}
void List::clear()
{
Node* cur;
while( head )
{
cur = head;
head = head->next; // head set to NULL at end of loop //
delete cur;
}
tail = NULL;
size = 0;
}
#endif
// List_step6.cpp // // 2013-05-08 //
// Here we have upgraded our (int) class List to NOW be a template class
// so that it can NOW handle any type of data (NOT just int data)
// We have also added a nested iterator class so that we can traverse the list
// and access the elements in the list ... i.e. the data in any Node in the list
// i.e can read the (const) data ... or change (update) the data in a node
// Note: the data could be another data struct or class
// Also note, that HERE we have NOW moved our 'io' print functions
// to NOW be defined *outside* our class ...
// See the overloaded << operator in the template function def'n right below ...
// that uses the iterators (added here) ...
// for the class to traverse AND to access the elements in the class
// Note that the iterators behave also as a 'wrapper class' that 'wrap' a Node
// to permit access to a Node and the data in a Node ...
// as facilitating traversing the elements in the List ...
// (from the head element ... to the tail element)
#include "template_class_List_SLL.h"
#include <iostream>
#include <fstream> // re. ostream
using namespace std;
template < typename T >
ostream& operator << ( ostream& os, List < T > & lst )
{
typename List < T > ::iterator it;
for( it = lst.begin(); it != lst.end(); ++ it )
os << *it << ", ";
return os << "size now is " << lst.size() << endl;
}
int main()
{
List < int > myLst;
myLst.push_back( 10 );
myLst.push_back( 30 );
myLst.push_back( 20 );
myLst.push_back( 40 );
cout << "Showing myLst ...\n" << myLst;
List < int > myLst2 = myLst;
cout << "\ndeleting 20 ... \n";
myLst.erase( 20 );
cout << "Showing myLst ...\n" << myLst;
cout << "\ndeleting 40 ... \n";
myLst.erase( 40 );
cout << "Showing myLst ...\n" << myLst;
cout << "\nclear list ... \n";
myLst.clear();
cout << "Showing myLst ...\n" << myLst;
cout << "\nShowing myLst2 ...\n" << myLst2;
cout << "\nShowing myLst2 ...\n";
List< int >::iterator it;
for( it = myLst2.begin(); it != myLst2.end(); ++ it )
cout << *it << endl;
cout << "Press 'Enter' to continue/exit ... " << flush;
cin.get();
}
// template_class_List_SLL.h // // 2013-05-08 //
#ifndef TEMPLATE_CLASS_LIST_SLL_H
#define TEMPLATE_CLASS_LIST_SLL_H
template < typename T >
class List
{
// this section is private by default (for a class)
// we are putting this private Node definition at the top so that it is 'known'
// inside our 'nested' interator class that follows here ...
struct Node
{
T val;
Node* next;
// default ...and value passed in ...ctor(s)... (this code handles both)
// Note initialization list and how default values are handled here...
Node( const T& value = 0 ) : val( value ), next( 0 ) {}
} ;
Node* head;
Node* tail;
int len;
public:
// default ctor with initialization list ...
List() : head( 0 ), tail( 0 ), len( 0 ) {}
~List() { clear() ; }
List( const List& old ); // copy ctor ...
List& operator = ( const List& old ); // overloaded =
void push_back( const T& val );
void push_front( const T& val );
// erase FIRST node with this val (if it exists in list)
bool erase( const T& val );
void clear();
int size() const { return len; }
class iterator
{
friend class List< T >; // to give class List access to private ptr
public:
iterator& operator ++ () { ptr = ptr->next; return *this; }
iterator& operator ++ ( int ) { ptr = ptr->next; return *this; }
bool operator != (const iterator& ) const;
T operator * () const;
T& operator * ();
private:
Node* ptr;
};
iterator begin();
iterator end();
} ;
template < typename T >
List< T >::List( const List& old )
{
head = tail = 0;
len = 0;
Node* cur = old.head;
while( cur ) { push_back( cur->val ); cur = cur->next; }
}
template < typename T >
List< T >& List< T >::operator = ( const List& old )
{
if( this != &old )
{
clear();
//head = tail = 0;
//len = 0;
Node* cur = old.head;
while( cur ) { push_back( cur->val ); cur = cur->next; }
}
return *this;
}
template < typename T >
void List< T >::push_back( const T& val )
{
Node* newNode = new Node( val );
if( len ) // then newNode not first node
{
tail->next = newNode;
tail = newNode;
}
else head = tail = newNode;
++ len;
}
template < typename T >
void List< T >::push_front( const T& val )
{
Node* newNode = new Node( val );
newNode->next = head;
head = newNode; // can now update head ...
if( ++len == 1 ) tail = newNode;
}
// erase FIRST node with this val (if it exists in list)
template < typename T >
bool List< T >::erase( const T& val )
{
Node* cur = head; // get copy
Node* prev = 0;
while( cur )
{
if( cur->val == val ) break;
prev = cur;
cur = cur->next;
}
// test end conditions ...
if( cur ) // was found
{
if( prev ) // was not first node, so prev and cur exist
prev->next = cur->next; // skip over cur ...
else // was first node
head = head->next;
if( cur == tail ) tail = prev;
delete cur;
-- len;
return true; // was erased ...
}
// else cout << "\nNot found ...\n";
return false;
}
template < typename T >
void List< T >::clear()
{
Node* cur;
while( head )
{
cur = head;
head = head->next; // head set to NULL at end of loop //
delete cur;
}
tail = 0;
len = 0;
}
// Compares two iterators and returns true or false depending on whether
// or not ... they are referencing the same Node.
template < typename T >
bool List< T >::iterator::operator != (
const typename List< T >::iterator& it ) const
{
return ptr != it.ptr;
}
// Returns the value of the Node that the iterator is referencing.
template < typename T >
T List< T >::iterator::operator * () const
{
return ptr->val;
}
// Permits assigning a Node a new value, via an iterator.
template < typename T >
T& List< T >::iterator::operator * ()
{
return ptr->val;
}
template < typename T >
typename List< T >::iterator List< T >::begin()
{
typename List< T >::iterator it;
it.ptr = head;
return it;
}
template < typename T >
typename List< T >::iterator List< T >::end()
{
typename List< T >::iterator it;
it.ptr = 0;
return it;
}
#endif
// template_class_List_SLL.h // // 2018-03-23 //
#ifndef TEMPLATE_CLASS_LIST_SLL_H
#define TEMPLATE_CLASS_LIST_SLL_H
template < typename T >
class List
{
// this section is private by default (for a class)
// we are putting this private Node definition at the top so that it is 'known'
// inside our 'nested' interator class that follows here ...
struct Node
{
T val;
Node* next;
// default ...and value passed in ...ctor(s)... (this code handles both)
// Note initialization list and how default values are handled here...
Node( const T& value, Node* next = 0 ) : val( value ), next( next ) {}
} ;
Node* head;
Node* tail;
int len;
public:
// default ctor with initialization list ...
List() : head( 0 ), tail( 0 ), len( 0 ) {}
~List() { clear() ; }
List( const List& old ); // copy ctor ...
List& operator = ( const List& old ); // overloaded =
void push_back( const T& val );
void push_front( const T& val );
// erase FIRST node with this val (if it exists in list)
bool erase( const T& val );
void clear();
int size() const { return len; }
class iterator
{
friend class List< T >; // to give class List access to private ptr
public:
iterator& operator ++ () { ptr = ptr->next; return *this; }
bool operator != ( const iterator& ) const;
T operator * () const;
T& operator * ();
private:
Node* ptr;
};
iterator begin();
iterator end();
} ;
template < typename T >
List< T >::List( const List& old )
{
head = tail = 0;
len = 0;
Node* cur = old.head;
while( cur ) { push_back( cur->val ); cur = cur->next; }
}
template < typename T >
List< T >& List< T >::operator = ( const List& old )
{
if( this != &old )
{
clear();
//head = tail = 0;
//len = 0;
Node* cur = old.head;
while( cur ) { push_back( cur->val ); cur = cur->next; }
}
return *this;
}
template < typename T >
void List< T >::push_back( const T& val )
{
if( len ) // then newNode not first node
{
tail->next = new Node( val );
tail = tail->next;
}
else head = tail = new Node( val );
++ len;
}
template < typename T >
void List< T >::push_front( const T& val )
{
head = new Node( val, head );
if( ++len == 1 ) tail = head;
}
// erase FIRST node with this val (if it exists in list)
template < typename T >
bool List< T >::erase( const T& val )
{
Node* cur = head; // get copy
Node* prev = 0;
while( cur )
{
if( cur->val == val ) break;
prev = cur;
cur = cur->next;
}
// test end conditions ...
if( cur ) // was found
{
if( prev ) // was not first node, so prev and cur exist
prev->next = cur->next; // skip over cur ...
else // was first node
head = head->next;
if( cur == tail ) tail = prev;
delete cur;
-- len;
return true; // was erased ...
}
// else cout << "\nNot found ...\n";
return false;
}
template < typename T >
void List< T >::clear()
{
Node* cur;
while( head )
{
cur = head;
head = head->next; // head set to NULL at end of loop //
delete cur;
}
tail = 0;
len = 0;
}
// Compares two iterators and returns true or false depending on whether
// or not ... they are referencing the same Node.
template < typename T >
bool List< T >::iterator::operator != (
const typename List< T >::iterator& it ) const
{
return ptr != it.ptr;
}
// Returns the value of the Node that the iterator is referencing.
template < typename T >
T List< T >::iterator::operator * () const
{
return ptr->val;
}
// Permits assigning a Node a new value, via an iterator.
template < typename T >
T& List< T >::iterator::operator * ()
{
return ptr->val;
}
template < typename T >
typename List< T >::iterator List< T >::begin()
{
typename List< T >::iterator it;
it.ptr = head;
return it;
}
template < typename T >
typename List< T >::iterator List< T >::end()
{
typename List< T >::iterator it;
it.ptr = 0;
return it;
}
#endif
// List_step6.cpp // // 2018-03-23 //
// Here we have upgraded our (int) class List to NOW be a template class
// so that it can NOW handle any type of data (NOT just int data)
// We have also added a nested iterator class so that we can traverse the list
// and access the elements in the list ... i.e. the data in any Node in the list
// i.e can read the (const) data ... or change (update) the data in a node
// Note: the data could be another data struct or class
// Also note, that HERE we have NOW moved our 'io' print functions
// to NOW be defined *outside* our class ...
// See the overloaded << operator in the template function def'n right below ...
// for the class to traverse AND to access the elements in the class
// Note that the iterators behave also as a 'wrapper class' that 'wrap' a Node
// to permit access to a Node and the data in a Node ...
// as facilitating traversing the elements in the List ...
// (from the head element ... to the tail element)
// that uses the iterators (added here) ...
#include "template_class_List_SLL.h"
#include <iostream>
using namespace std;
template < typename T >
ostream& operator << ( ostream& os, List < T > & lst )
{
typename List < T > ::iterator it;
for( it = lst.begin(); it != lst.end(); ++ it )
os << *it << ", ";
return os << "size now is " << lst.size() << endl;
}
int main()
{
List < int > myLst;
myLst.push_front( 10 );
myLst.push_front( 30 );
myLst.push_front( 20 );
myLst.push_front( 40 );
cout << "Showing myLst ...\n" << myLst;
List < int > myLst2 = myLst;
cout << "\ndeleting 20 ... \n";
myLst.erase( 20 );
cout << "Showing myLst ...\n" << myLst;
cout << "\ndeleting 40 ... \n";
myLst.erase( 40 );
cout << "Showing myLst ...\n" << myLst;
cout << "\nclear list ... \n";
myLst.clear();
cout << "Showing myLst ...\n" << myLst;
cout << "\nShowing myLst2 ...\n" << myLst2;
cout << "\nShowing myLst2 ...\n";
List< int >::iterator it;
for( it = myLst2.begin(); it != myLst2.end(); ++ it )
cout << *it << endl;
cout << "Press 'Enter' to continue/exit ... " << flush;
cin.get();
}
// insertSortedDLLofString.cpp //
#include <iostream>
#include <string>
using namespace std;
struct Node
{
string str;
Node* prev;
Node* next;
Node( const string& str = "" ) : str(str), prev(0), next(0) {}
} ;
struct List
{
Node* head;
Node* tail;
int size;
List() : head(0), tail(0), size(0) {}
~List() { clear(); }
void clear()
{
while( head )
{
Node* del = head;
head = head->next;
delete del;
}
tail = 0;
size = 0;
}
void push_front( const string& str )
{
Node* nNode = new Node( str );
if( size )
{
nNode->next = head; // N->A
head->prev = nNode; // N<-A
head = nNode;
}
else tail = head = nNode;
++size;
}
void push_back( const string& str )
{
Node* nNode = new Node( str );
if( size )
{
tail->next = nNode; // B->N
nNode->prev = tail; // B<-N
tail = nNode;
}
else tail = head = nNode;
++size;
}
void insert_sorted( const string& str)
{
Node* nNode = new Node( str );
// case 1 ... NOT inserted as the head node
if( head && head->str <= str )
{
// find Node to insert after
Node* prev = head;
Node* cur = head->next;
while( cur && cur->str <= str )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
nNode->prev = prev;
if( cur ) // NOT at tail
{
cur->prev = nNode;
nNode->next = cur;
}
else // at tail
{
tail = nNode;
}
}
else // insert at head ...
{
if( size )
{
nNode->next = head;
head->prev = nNode;
head = nNode;
}
else tail = head = nNode;
}
++ size;
}
void print() const
{
Node* cur = head;
while( cur )
{
cout << cur->str << ' ';
cur = cur->next;
}
}
void printReversed() const
{
Node* cur = tail;
while( cur )
{
cout << cur->str << ' ';
cur = cur->prev;
}
}
} ;
int main()
{
List myLst;
cout << "Now testing push_front:\n";
myLst.push_front( "Sam" );
myLst.push_front( "Joe" );
myLst.push_front( "Anne" );
myLst.print();
cout << "\nPrinting reversed:\n";
myLst.printReversed();
myLst.clear();
cout << "\n\nNow testing push_back:\n";
myLst.push_back( "Sam" );
myLst.push_back( "Joe" );
myLst.push_back( "Anne" );
myLst.print();
cout << "\nPrinting reversed:\n";
myLst.printReversed();
myLst.clear();
cout << "\n\nNow testing insert_sorted:\n";
myLst.insert_sorted( "Billy" );
myLst.insert_sorted( "Sam" );
myLst.insert_sorted( "Joe" );
myLst.insert_sorted( "Anne" );
myLst.insert_sorted( "Jill" );
myLst.print();
cout << "\nPrinting reversed:\n";
myLst.printReversed();
cout << "\n\nPress 'Enter' to continue/exit ..." << flush;
cin.get();
}
// insertSortedDLLofString2.cpp //
#include <iostream>
#include <string>
using namespace std;
class List
{
public:
List() : head(0), tail(0), size(0) {}
~List() { clear(); }
void clear()
{
while( head )
{
Node* del = head;
head = head->next;
delete del;
}
tail = 0;
size = 0;
}
void push_front( const string& str )
{
Node* nNode = new Node( str );
if( size )
{
nNode->next = head; // N->A
head->prev = nNode; // N<-A
head = nNode;
}
else tail = head = nNode;
++size;
}
void push_back( const string& str )
{
Node* nNode = new Node( str );
if( size )
{
tail->next = nNode; // B->N
nNode->prev = tail; // B<-N
tail = nNode;
}
else tail = head = nNode;
++size;
}
void insert_sorted( const string& str)
{
Node* nNode = new Node( str );
// case 1 ... NOT inserted as the head node
if( head && head->str <= str )
{
// find Node to insert after
Node* prev = head;
Node* cur = head->next;
while( cur && cur->str <= str )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
nNode->prev = prev;
if( cur ) // NOT at tail
{
cur->prev = nNode;
nNode->next = cur;
}
else // at tail
{
tail = nNode;
}
}
else // insert at head ...
{
if( size )
{
nNode->next = head;
head->prev = nNode;
head = nNode;
}
else tail = head = nNode;
}
++ size;
}
void print() const
{
Node* cur = head;
while( cur )
{
cout << cur->str << ' ';
cur = cur->next;
}
}
void printReversed() const
{
Node* cur = tail;
while( cur )
{
cout << cur->str << ' ';
cur = cur->prev;
}
}
private:
struct Node
{
string str;
Node* prev;
Node* next;
Node( const string& str = "" ) : str(str), prev(0), next(0) {}
} ;
Node* head;
Node* tail;
int size;
} ;
int main()
{
List myLst;
cout << "Now testing push_front:\n";
myLst.push_front( "Sam" );
myLst.push_front( "Joe" );
myLst.push_front( "Anne" );
myLst.print();
cout << "\nPrinting reversed:\n";
myLst.printReversed();
myLst.clear();
cout << "\n\nNow testing push_back:\n";
myLst.push_back( "Sam" );
myLst.push_back( "Joe" );
myLst.push_back( "Anne" );
myLst.print();
cout << "\nPrinting reversed:\n";
myLst.printReversed();
myLst.clear();
cout << "\n\nNow testing insert_sorted:\n";
myLst.insert_sorted( "Billy" );
myLst.insert_sorted( "Sam" );
myLst.insert_sorted( "Joe" );
myLst.insert_sorted( "Anne" );
myLst.insert_sorted( "Jill" );
myLst.print();
cout << "\nPrinting reversed:\n";
myLst.printReversed();
cout << "\n\nPress 'Enter' to continue/exit ..." << flush;
cin.get();
}
// insertSortedDLL.cpp // // 2016-02-12 //
// Note: still need to code copy ctor... and overloaded operator =
// But these are not needed in the short 'test code' used in 'main' below. //
#include <iostream>
#include <string>
using namespace std;
template< typename T >
class List
{
public:
List() : head(0), tail(0), len(0) {}
~List() { clear(); }
void clear()
{
while( head )
{
Node* del = head;
head = head->next;
delete del;
}
tail = 0;
len = 0;
}
void push_front( const T& val )
{
Node* nNode = new Node( val );
if( len )
{
nNode->next = head; // N->A
head->prev = nNode; // N<-A
head = nNode;
}
else tail = head = nNode;
++len;
}
void push_back( const T& val )
{
Node* nNode = new Node( val );
if( len )
{
tail->next = nNode; // B->N
nNode->prev = tail; // B<-N
tail = nNode;
}
else tail = head = nNode;
++len;
}
void insert_sorted( const T& val)
{
Node* nNode = new Node( val );
// case 1 ... NOT inserted as the head node
if( head && head->val <= val )
{
// find Node to insert after
Node* prev = head;
Node* cur = head->next;
while( cur && cur->val <= val )
{
prev = cur;
cur = cur->next;
}
// ok found spot ... insert after 'prev'
prev->next = nNode;
nNode->prev = prev;
if( cur ) // NOT at tail
{
cur->prev = nNode;
nNode->next = cur;
}
else // at tail
{
tail = nNode;
}
}
else // insert at head ...
{
if( len )
{
nNode->next = head;
head->prev = nNode;
head = nNode;
}
else tail = head = nNode;
}
++ len;
}
void print( ostream& os = cout ) const
{
Node* cur = head;
while( cur )
{
os << cur->val << ' ';
cur = cur->next;
}
}
void print_reversed() const
{
Node* cur = tail;
while( cur )
{
cout << cur->val << ' ';
cur = cur->prev;
}
}
size_t size() const { return len; }
private:
struct Node
{
T val;
Node* prev;
Node* next;
Node( const T& val = T() ) : val(val), prev(0), next(0) {}
} ;
Node* head;
Node* tail;
size_t len;
} ;
int main()
{
List< string > my_lst;
cout << "Now testing push_front:\n";
my_lst.push_front( "Sam" );
my_lst.push_front( "Joe" );
my_lst.push_front( "Anne" );
my_lst.print();
cout << "\nPrinting reversed:\n";
my_lst.print_reversed();
my_lst.clear();
cout << "\n\nNow testing push_back:\n";
my_lst.push_back( "Sam" );
my_lst.push_back( "Joe" );
my_lst.push_back( "Anne" );
my_lst.print();
cout << "\nPrinting reversed:\n";
my_lst.print_reversed();
my_lst.clear();
cout << "\n\nNow testing insert_sorted:\n";
my_lst.insert_sorted( "Billy" );
my_lst.insert_sorted( "Sam" );
my_lst.insert_sorted( "Joe" );
my_lst.insert_sorted( "Anne" );
my_lst.insert_sorted( "Jill" );
my_lst.print();
cout << "\nPrinting reversed:\n";
my_lst.print_reversed();
cout << "\n\nPress 'Enter' to continue/exit ..." << flush;
cin.get();
}
// test_List_SLL.cpp // // 2018-02-12 //
// Here we have upgraded our (int) class List to NOW be a template class
// so that it can NOW handle any type of data (NOT just int data)
// We have also added a nested iterator class so that we can traverse the list
// and access the elements in the list ... i.e. the data in any Node in the list
// i.e can read the (const) data ... or change (update) the data in a node
// Note: the data could be another data struct or class
// Also note, that HERE we have NOW moved our 'io' print functions
// to NOW be defined outside our class ...
// See the overloaded << operator in the template function def'n right below ...
// that uses the iterators (added here) ...
// for the class to traverse AND to access the elements in the class
// Note that the iterators behave also as a 'wrapper class' that 'wrap' a Node
// to permit access to a Node and the data in a Node ...
// as facilitating traversing the elements in the List ...
// (from the head element ... to the tail element)
[code]#include "List_SLL.h"
#include <iostream>
#include <fstream> // re. ostream
template < typename T >
std::ostream& operator << ( std::ostream& os, const List < T > & lst )
{
typename List < T >::const_iterator it;
for( it = lst.begin(); it != lst.end(); ++ it )
os << *it << ", ";
return os << "size now is " << lst.size() << std::endl;
}
int main()
{
using std::cout;
using std::cin;
List < int > myLst;
myLst.push_back( 10 );
myLst.push_back( 20 );
myLst.push_back( 30 );
myLst.push_back( 40 );
cout << "Showing myLst ...\n" << myLst;
List < int > myLst2 = myLst; // test copy ctor //
cout << "\ndeleting 50 ... \n";
if( !myLst.erase( 50 ) ) cout << "50 was NOT found ... ";
cout << "Showing myLst ...\n" << myLst;
cout << "\ndeleting 40 ... \n";
List< int >::iterator it;
if( (it = myLst.find( 40 )) != myLst.end() )
myLst.erase( it );
else cout << "40 was NOT found ... ";
cout << "Showing myLst ...\n" << myLst;
cout << "\ndeleting 20 ... \n";
if( (it = myLst.find( 20 )) != myLst.end() )
myLst.erase( it );
else cout << "20 was NOT found ... ";
cout << "Showing myLst ...\n" << myLst;
cout << "\ndeleting 10 ... \n";
if( (it = myLst.find( 10 )) != myLst.end() )
myLst.erase( it );
else cout << "10 was NOT found ... ";
cout << "Showing myLst ...\n" << myLst;
cout << "\ndeleting 30 ... \n";
if( (it = myLst.find( 30 )) != myLst.end() )
myLst.erase( it );
else cout << "30 was NOT found ... ";
cout << "Showing myLst ...\n" << myLst;
cout << "\ndeleting 30 ... \n";
if( (it = myLst.find( 30 )) != myLst.end() )
myLst.erase( it );
else cout << "30 was NOT found ... ";
cout << "Showing myLst ...\n" << myLst;
myLst.push_back( 30 );
cout << "\nAfter push_back(30) and clear list ... \n";
myLst.clear();
cout << "Showing myLst ...\n" << myLst;
myLst.push_front( 30 );
cout << "\nAfter push_front(30) and clear list ... \n";
myLst.clear();
cout << "Showing myLst ...\n" << myLst;
cout << "\nShowing myLst2 ...\n" << myLst2;
cout << "\nShowing myLst2 ...\n";
for( it = myLst2.begin(); it != myLst2.end(); ++ it )
cout << *it << ' ';
cout << "\n\nTesting push_front, pop_front, etc... \n";
myLst.push_front( 10 );
myLst.push_front( 20 );
myLst.push_front( 30 );
myLst.push_front( 40 );
// testing front and pop_front ...
while( !myLst.empty() )
{
cout << myLst.front() << ' ';
myLst.pop_front();
}
cout << "\n\nPress 'Enter' to continue/exit ... ";
cin.get();
}
// List_SLL.h // // 2018-02-12 //
#ifndef LIST_SLL_H
#define LIST_SLL_H
#include <iostream> // re. size_t //
template < typename T >
class List
{
// This section is private by default (for a class)
// we are putting this private Node definition at the top so that it is 'known'
// inside our 'nested' interator class that follows here ...
struct Node
{
T val;
Node* next;
// default ...and value passed in ...ctor(s)... (this code handles both)
// Note initialization list and how default values are handled here...
Node( const T& value = 0 ) : val( value ), next( 0 ) {}
} ;
Node* head;
Node* tail;
size_t len;
public:
// default ctor with initialization list ...
List() : head( 0 ), tail( 0 ), len( 0 ) {}
~List() { clear() ; }
List( const List& old ); // copy ctor ...
List& operator = ( const List& old ); // overloaded =
void push_back( const T& val );
void push_front( const T& val );
// erase FIRST node with this val (if it exists in list)
bool erase( const T& val );
void clear();
size_t size() const { return len; }
class iterator
{
Node* ptr;
friend class List< T >; // to give class List access to private ptr
public:
iterator& operator ++ () { ptr = ptr->next; return *this; }
iterator& operator ++ ( int ) { ptr = ptr->next; return *this; }
bool operator != ( const iterator& ) const;
const T& operator * () const;
T& operator * ();
} ;
iterator begin();
iterator end();
typedef iterator const_iterator;
const_iterator begin() const;
const_iterator end() const;
iterator find( const T& val );
bool erase( iterator it );
// These added so can use List as a stack using push_front, pop_front and empty //
T front() const { return head->val; }
T back() const { return tail->val; }
void pop_front()
{
if( len )
{
Node* tmp = head;
head = head->next;
delete tmp;
-- len;
if( len <= 1 ) tail = head;
}
}
bool empty() const { return len == 0; }
} ;
template < typename T >
List< T >::List( const List& old )
{
head = tail = 0;
len = 0;
for( Node* cur = old.head; cur; cur = cur->next )
push_back( cur->val );
}
template < typename T >
List< T >& List< T >::operator = ( const List& old )
{
if( this != &old )
{
clear(); // also does // head = tail = 0; len = 0; //
for( Node* cur = old.head; cur; cur = cur->next )
push_back( cur->val );
}
return *this;
}
template < typename T >
void List< T >::push_back( const T& val )
{
Node* newNode = new Node( val );
if( len ) // then newNode not first node
tail->next = newNode;
else
head = newNode;
tail = newNode;
++ len;
}
template < typename T >
void List< T >::push_front( const T& val )
{
Node* newNode = new Node( val );
newNode->next = head;
head = newNode; // can now update head ...
if( ++len == 1 ) tail = newNode;
}
// erase FIRST node with this val (if it exists in list)
template < typename T >
bool List< T >::erase( const T& val )
{
Node* prev = 0;
Node* cur = head; // get copy
while( cur )
{
if( cur->val == val ) break;
prev = cur;
cur = cur->next;
}
// test end conditions ...
if( cur ) // was found
{
if( prev ) // was not first node, so prev and cur exist
prev->next = cur->next; // skip over cur ...
else // was first node
head = head->next;
if( cur == tail ) tail = prev;
delete cur;
-- len;
return true; // was erased ...
}
// else cout << "\nNot found ...\n";
return false;
}
template < typename T >
void List< T >::clear()
{
Node* cur;
while( head )
{
cur = head;
head = head->next; // head set to NULL at end of loop //
delete cur;
}
tail = 0;
len = 0;
}
// Compares two iterators and returns true or false depending on whether
// or not ... they are referencing the same Node.
template < typename T >
bool List< T >::iterator::operator != (
const typename List< T >::iterator& it ) const
{
return ptr != it.ptr;
}
// Returns the value of the Node that the iterator is referencing.
template < typename T >
const T& List< T >::iterator::operator * () const
{
return ptr->val;
}
// Permits assigning a Node a new value, via an iterator.
template < typename T >
T& List< T >::iterator::operator * ()
{
return ptr->val;
}
template < typename T >
typename List< T >::iterator List< T >::begin()
{
List< T >::iterator it;
it.ptr = head;
return it;
}
template < typename T >
typename List< T >::iterator List< T >::end()
{
List< T >::iterator it;
it.ptr = 0;
return it;
}
template < typename T >
typename List< T >::const_iterator List< T >::begin() const
{
List< T >::const_iterator it;
it.ptr = head;
return it;
}
template < typename T >
typename List< T >::const_iterator List< T >::end() const
{
List< T >::const_iterator it;
it.ptr = 0;
return it;
}
template < typename T >
typename List< T >::iterator List< T >::find( const T& val )
{
List< T >::iterator it;
for( it.ptr = head; it.ptr; it.ptr = it.ptr->next )
{
if( *it == val ) return it;
}
return end();
}
template < typename T >
bool List< T >::erase( iterator it )
{
Node* prev = 0;
Node* cur = head;
for( ; cur && cur != it.ptr; cur = cur->next )
{
prev = cur;
}
// check end conditions //
if( cur ) // found //
{
if( prev )
prev->next = cur->next;
else
head = head->next;
if( cur == tail ) tail = prev;
delete cur;
-- len;
return true;
}
// NOT found //
return false;
}
#endif