Template Linked Lists

[camouser]

I have been working on an assignment in my CSII class over Linked Lists in template classes and would like someone to take a look at this. (I am not asking anyone to do my homework by the way) Just want to know if im on the right track with these two particular functions. The assignment is as follows:


Assignment

Your task is to complete the following LinkList as we discussed in class and then write a C++ program to test your LinkList. You need to test all of the functions in your LinkList with at least two types of LinkList, such as an integer LinkList and a string LinkList.

The following is the class declaration from the header file:

template <typename T> 
class LinkList
{ 
   private:
    class Node
    {
      public:
      T info;
      Node *next;
    };
    typedef Node *nodePtr;
 
   public:
  	LinkList(); 		//constructor 
	LinkList(const LinkList<T> & orig); //copy constructor
	~LinkList();		//destructor
	bool empty(); 		//determine if the LinkList is empty 
        T Front(); 			// returns item at front of LinkList
	T Back();			// returns item at back of LinkList
	Void Pus_back(const T & item);// add an item at the end of the LinkList
        void Push_front(const T & item); //add item at the begining of LinkList
        void pop_back(); 	//remove the last item of the LinkList
        void pop_front(); //remove the first item of the LinkList
        void insert(T item);//insert the item in ascending order
        void erase(T item);//remove the item in the list
        bool Search(T item);	//search a given item, if it can be found, return true, otherwise return false
	int Count();		//return the number of items in the list
	LinkList<T>& operator=(const LinkList<T> & orig); //overloaded assignment operator
	friend ostream& operator<<(ostream &out, const LinkList<T> & L); 
								//overloaded output operator 

  private:       
     nodePtr First;      //node pointer which points to the front(first node)
};  

I've written the TFront() and TBack() functions below as I thought they should be but I need the feedback on them. They are as follows:

//TFront(): returns item at the back of the list
//Postcondition: nodePtr points to the front of the list
template <typename T>
TFront()
{
  nodePtr nPtr = front;
  return front;
}

and

//TBack(): returns the item at the back of the list
//Precondition: nodePtr points to the front of the list
//Postcondition: nodePtr points to back
template <typename T>
TBack()
{
  nodePtr nPtr = back;
  while (nPtr != 0)
   {
     nPtr->next = back;
   }

   if (nPtr->next == 0)
    {
      nPtr->next = back;
      return back;
    }
   
   return back;
}

Also, I wasnt sure if the if statement from the TBack() function should have gone inside the while loop or outside. So, I revised it for that too.

template <typename T>
TBack()
{
  nodePtr nPtr = back;
  while (nPtr != 0)
   {
     nPtr->next = back;
     if (nPtr->next == 0)
      {
        nPtr->next = back;
        return back;
      }
   
     return back;
   }
}

Any constructive criticism would be greatly appreciated and again, I'm not asking anyone to do my homework. Just let me know if i'm on the right track. Thanks

[coder777]

It is not

TFront() and TBack()

it is T Front() and T Back() and must be placed entirely within the templated class.

//TFront(): returns item at the back of the list
//Postcondition: nodePtr points to the front of the list
template <typename T>
TFront()
{
nodePtr nPtr = front;
return front;
}

is completely wrong (since you don't have 'front'). Must be

T Front()
{
  T result;
  if(First != NULL)
    result = First->info;
  return result;
}

You may throw if 'First' is actually NULL though.

Sometimes you name the functions with a capital letter sometimes not. Make it consistent.

[Kulaghma4]

nice, friendly up !!

[camouser]

friendly up?

[sharris]

camouser, at this line on my Dev-Cpp I get "Void" does not have same type.

nice, friendly up !!

Btw: I never saw a first time poster throwing in a sly remark. I guest the whole world is piss-off at students of C++, especially when there was no possible or easy answer in the first place. It's not our fault they did not have INTERNET to go to back in the stone-ages.

[coder777]

sharris wrote:

camouser, at this line on my Dev-Cpp I get "Void" does not have same type.

There are more errors.

My intention was not only to show the errors but to show a way how to make it right. He ignored my constructive criticism so why bother.

[sharris]

I see your point. I have no more comments until I near master C++, but I will never take another course in C++, ever. One or two semester is more than enough to get a clue, after that it's only a progress killer (is it homework or is it Bill). I learn 10x more on my own. It's strange that a stone-age asm coder like myself now love C++ also. Just making the move is mostly un-thought of. It took me years. Thanks for the friendly up coder777 :)

[camouser]

wow im lost. the feedback did help though so thank you

[camouser]

Ive taken the feedback and applied it before finishing the header file completely so here it is. Hopefully, there arent too many more issues to tend to

//Author: Chris Mouser
//Purpose: Header file for close lab 7: LinkList class
//Date: 3/14/2011
#ifndef LINKLIST
#define LINKLIST
#include <iostream>
#include <new>
#include <cassert>
using namespace std;

template <typename T>
class LinkList
{
private:
	class Node
	{
      Public:
		T info;
		Node *next;
	};
	typedef Node *nodePtr;

Public:
	LinkList()                               //default constructor, written inline
	{
		front = 0;
		numNodes = 0;
	}
	LinkList (const LinkList <T>& orig);     //copy constructor
	~LinkList();                             //destructor
	bool empty();                            //determine if LinkList is empty
	T Front();                               //return item at front of LinkList
	T Back();                                //return item at back of LinkList
	void Push_Back (const T& item);          //add item at the end of the LinkList
	void Push_Front (const T& item);         //add item at the beginning of the LinkList
	void Pop_Back();                         //remove the last item in the LinkList
	void Pop_Front();                        //remove the first item in the LinkList
	void insert (T item);                    //insert the item in ascending order
	void erase (T item);                     //remove the item in the list
	void search (T item);                    //search for a given item. If it can be found, return true. Otherwise, return false
	int Count();                             //return the number of items in the list
	LinkList<T>& operator = (const LinkList<T> & orig);                 //overloaded assignment operator
	friend ostream& operator << (ostream& out, const LinkList<T>& L)
	{                                                                   //overloaded output operator, written inline
		nodePtr nPtr = L.Front;
		while (First != NULL)
		{
			out << First->data << endl;
			First = First->next;
		}

		return out;
	}

Private:
	nodePtr *First;                          //node pointer that points to front (first node)
};
//end of template class declaration

//Copy-Constructor
//Precondition: A copy of a LinkList is needed.
//Postcondition: A copy of original has been constructed.
//Receives: The LinkList to be copied (as a const reference parameter.)
template <typename T>
LinkList<T>::LinkList(const LinkList<T> & original)
{
	if (original.front == 0)
	{
		front = 0;
		return;
	}

	nodePtr origPtr = original.front;
	nodePtr lastPtr = new node;    //allocating memory for new node
	if (lastPtr == 0)
	{
		cout << "No free memory available.\n"
			 << "Value cannot be inserted.\n";
		exit(1);
	}
	
	lastPtr->data = origPtr->date;
	Front = lastPtr;

	numNodes = original.numNodes;

	while (origPtr->next != 0)   //begin copy from second node
	{
		origPtr = origPtr->next;
		nodePtr tempPtr = new node;
		if (tempPtr == 0)
		{
			cout << "No free memory available.\n"
				 << "Value cannot be inserted.\n";
			exit(1);
		}

		tempPtr->data = origPtr->data;
		tempPtr->next = 0;
		lastPtr->next = tempPtr;
		lastPtr = lastPtr->next;
	}
}

//LinkList destructor
//Precondition: The lifetime of the list containing this functions end
//Postcondition: The routine allocated memory has been deallocated
template <typename T>
Linklist<T>::~LinkList()
{
	nodePtr nPtr = front;
	while (nPtr != 0)
	{
		front = ->next;
		delete nPtr;
		nPtr = front;
	}

	if (front == 0)
	{
		cout << "List Deleted.\n";
	}
	else
	{
		cout << "List not deleted.\n";
	}
}

//empty() function
//Precondition: List is not empty
//Postcondition: List is empty
//Receives: numNodes
template <typename T>
bool LinkList<T>::empty()
{
	if (numNodes == 0)
		return true;
	else
		return false;
}

//T Front(): Returns the item at the front of the list.
//Precondition: nodePtr points to NULL
//Postcondition:nodePtr points to the front of the list
template <typename T>
LinkList<T>::Front()
{
	T Front;
	if (first != NULL)
	{
		front = first->data;
	}
	return front;
}

//T Back(): returns the item at the back of the list
//Precondition: nodePtr points to front
//Postcondition: nodePtr points to back
//Receives: item at the back of the list
template <typename T>
T Back()
{
	T back;
	nodePtr nPtr = back;
	while (nPtr != 0)
	{
		back = nPtr->next;
		if (nPtr->next == 0)
		{
			back = nPtr->next;
			return back;
		}
		return nPtr->, back;
	}
}

//Push_back() function to add item at the end of the list.
//Precondition: item is at the front of the list
//Postcondition: item is at the end of the link list
template <typename T>
void LinkList<T>::Push_Back(T item)
{
	if (First != NULL)       //check for end of list
		T item = First->next;  //if end is not reached, move to next node
	else
		item = First->data;    //item inserted back of list
}

//Push_Front() function adds item at beginning of list
//Precondition: adds item to the back of the list
//Postcondition: item at the front of the list
template <typename T>
void LinkList<T>::Push_Front (T item)
{
	if (first != NULL)    //check for end of list
		First->data = item;
	else
		cerr << "List empty.";
}

//Pop_Back() function removes the last item in the LinkList
//Precondition: Last item is in the LinkList
//Postcondition: Last item is not in the LinkList
template <typename T>
void LinkList<T>::Pop_Back()
{
	if (empty ())       //check if list is empty
		cout << "List is empty.\n";
	else
		first--;
}

//Pop_Front() function removes the first item in the LinkList
//Precondition: first item in LinkList is not null
//Postcondition: First item is removed from LinkList
template <typename T>
void LinkList<T>::Pop_Front()
{
	if (empty())
		cout << "List is empty.\n";
	else
		first++;
}

//insert() function inserts the item in ascending order
//Precondition: item does not exist in list
//Postcondition: item inserted in ascending order
template <typename T>
void LinkList<T>::insert(T item)
{
	nodePtr nPtr = newNode;
	if (first == 0)
	{
		cout << "No free memory available and value cannot be inserted.\n";
		return;
	}

	First->data = item;
	First->next = 0;
	nodePtr cursor = first;   //cursor used to traverse list

	if (first == NULL)           //empty list case
	{
		First->next = 0;
		Front = First;
	}
	else
	{
		//insert at front of case
	    if (cursor->data > item)
	    {
		First->next = Front;
		First = Front;
	    }
	    else
	    {
		//insert in the middle case
		  for (cursor = front; cursor->next != 0; cursor = cursor->next)
		  {
			 if (cursor->next->data > item)
				 break;
		  }
		
		First->next = cursor->next;
		cursor->next = first;
	}
}
numNodes++;
}

//erase() function removes an item from the list
//Precondition: List contains item
//Postcondition: List does not contain item
template <typename T>
void LinkList<T>::erase(T item)
{
	//empty list case
	if (first == NULL)
	{
		cout << "List is empty.\n";
		return;
	}

	//single node list case
	if (First->next == 0)
	{
		if (First->data == item)
		   delete First;
		else
			cout << "Item not found in list.\n";

		return;
	}

	nodePtr cursor = First, prePtr = First;
	while (cursor->next != 0 && cursor->data != item)
	{
		prePtr = cursor;
		cursor = cursor->next;
	}

	if (cursor->data == item)
	{
		if (cursor == First)
		{
			First = cursor->next;
			delete cursor;
		}
	}
	else
		cout << "Item not found in list.\n";

	return;
}

//search() function searches for a given item. If it is found, return true. Otherwise, return false.
//Precondition: item is not found in list
//Postcondition: item is found in the list
template <typename T>
void LinkList<T>::search(T item)
{
	for (int i = 0; i < First; i++)
	{
		if (numNodes[i] == item)
		   return true;
	}

	return false
}

//Count() function returns the number of items in the link list
//Precondition: none
//Postcondition: count++
template <typename T>
int LinkList<T>::Count()
{
	int count;
	for (int i = 0; i < first; i++)
	{
		numNodes[i];
		count++;
		cout << "Node: " << numNodes[i] << "Node count: " << count << endl;
	}

	return count;
}

[camouser]

continued from previous...

//overloaded assignment operator
template <typename T>
LinkList<T> & operator = (const LinkList<T> & orig)
{
	cout << "Overloaded Assignment Operator.\n";
	if (this != &orig)
	{
		nodePtr nPtr = First;
		while (First != 0)
		{
			First = First->next;
			delete First;
			First = nPtr;
		}

		nodePtr origPtr = orig.front;
		nodePtr lastPtr = new Node;     //allocate memory for new node
		if (lastPtr == NULL)
		{
			cout << "No free memory available.\n"
				 << "Value cannot be inserted.\n";
			exit(1);
		}

		lastPtr->data = origPtr->data;
		First = lastPtr;

		numNodes = orig.numNodes;
		if (orig.First == NULL)
		   First = 0;
		else
		{
			int i = 1;
			while (i < numNodes)   //begin copy from second node
			{
				origPtr = origPtr->next;
				nodePtr tempPtr = newNode;
				if (tempPtr == NULL)
				{
					cout << "No free memory available.\n"
						 << "Item cannot be inserted.\n";
					exit(1);
				}

				tempPtr->data = origPtr->data;
				tempPtr->next = 0;
				lastPtr->next = tempPtr;
				lastPtr = lastPtr->next;
				i++;
			}
		}
		return *this;
	}
}
#endif

[guestgulkan]

Is this stream << operator function correct??

   
 friend ostream& operator << (ostream& out, const LinkList<T>& L)
    {                                                                   //overloaded output operator, written inline
        nodePtr nPtr = L.Front;
        while (First != NULL)
        {
            out << First->data << endl;
            First = First->next;
        }

        return out;
    }

The assignment operator function definition (first line) is incorrect.

template <typename T>
LinkList<T> & operator = (const LinkList<T> & orig) //this line here 

[hanst99]

nodePtr nPtr = First;
		while (First != 0)
		{
			First = First->next;
			delete First;
			First = nPtr;
		}

Did you actually try your code before posting it? Please think about what this does.

[camouser]

no i didnt try it...thats y i posted it here first to get stuff like this worked out. thanks for being so kewl about it.

[waqqassheikh]

Hi guys,

I've started learning Linked Lists and I'm looking up at online examples. I'd like to ask a few questions:

Void Pus_back(const T & item);// add an item at the end of the LinkList
void Push_front(const T & item); //add item at the begining of LinkList 

why do we need the CONSTs there????

and why do many templated linked list class have a friend method function??