If you are comfortable with templated classes, then you can design your classes as shown below. If not, then use a typedef for now and you can templated classes before you submit your work.
template <typename ITEM_TYPE> struct node { public: node(const ITEM_TYPE& item = ITEM_TYPE(), node* next = nullptr); template <typename T> friend std::ostream& operator <<(std::ostream& outs, const node<T> &printMe); ITEM_TYPE _item; node* _next; };
Please note that the operators of a templated class require a different template argument than the template argument of the class they are friends with (T, and not ITEM_TYPE). This is only true when the definition of the friend function is outside the class declaration.
These are "free floating" functions that do the heavy lifting for the List class we will be writing later. Do not make a class until you have these functions in place. The reason for this is that this method gives us the flexibility to design many similar classes effortlessly and quickly.
I suggest you study the algorithms you are going to use on paper very carefully before you start to write code. (Never write pointer or linked list related code without first drawing boxes and arrows.) Linked list bugs (pointer related bugs in general) tend to be illusive and hard to find and debug. Best strategy is avoidance.
//Linked List General Functions: template <typename ITEM_TYPE> void _print_list(node<ITEM_TYPE>* head); //recursive fun! :) template <typename ITEM_TYPE> void _print_list_backwards(node<ITEM_TYPE> *head); //return ptr to key or NULL template <typename ITEM_TYPE> node<ITEM_TYPE>* _search_list(node<ITEM_TYPE>* head, ITEM_TYPE key); template <typename ITEM_TYPE> node<ITEM_TYPE>* _insert_head(node<ITEM_TYPE> *&head, ITEM_TYPE insert_this); //insert after ptr template <typename ITEM_TYPE> node<ITEM_TYPE>* _insert_after(node<ITEM_TYPE>*& head, node<ITEM_TYPE> *after_this, ITEM_TYPE insert_this); //insert before ptr template <typename ITEM_TYPE> node<ITEM_TYPE>* _insert_before(node<ITEM_TYPE>*& head, node<ITEM_TYPE>* before_this, ITEM_TYPE insert_this); //ptr to previous node template <typename ITEM_TYPE> node<ITEM_TYPE>* _previous_node(node<ITEM_TYPE>* head, node<ITEM_TYPE>* prev_to_this); //delete, return item template <typename ITEM_TYPE> ITEM_TYPE _delete_node(node<ITEM_TYPE>*&head, node<ITEM_TYPE>* delete_this); //duplicate the list... template <typename ITEM_TYPE> node<ITEM_TYPE>* _copy_list(node<ITEM_TYPE>* head); //duplicate list and return the last node of the copy template <typename T> node<T> *_copy_list(node<T>* &dest, node<T> *src); //delete all the nodes template <typename ITEM_TYPE> void _clear_list(node<ITEM_TYPE>*& head); //_item at this position template <typename ITEM_TYPE> ITEM_TYPE& _at(node<ITEM_TYPE>* head, int pos); //. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . // Sorted List Routines. order: 0: ascending, order: other: descending // Assume a Sorted List //. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . template <typename ITEM_TYPE> node<ITEM_TYPE>* _insert_sorted(node<ITEM_TYPE>* &head, //insert ITEM_TYPE item, bool ascending=true); //insert or add if a dup template <typename ITEM_TYPE> node<ITEM_TYPE>* _insert_sorted_and_add(node<ITEM_TYPE>* &head, ITEM_TYPE item, bool ascending=true); //node after which this item goes order: 0 ascending template <typename ITEM_TYPE> node<ITEM_TYPE>* _where_this_goes(node<ITEM_TYPE>* head, ITEM_TYPE item, bool ascending=true); //Last Node in the list template <typename ITEM_TYPE> node<ITEM_TYPE>* _last_node(node<ITEM_TYPE>* head); //never use this function.
Testing:Test each and group of functions using test functions defined in main.
If you have any bugs in these functions, it will be very difficult to debug the higher level classes built on these functions. So, be very cautious!