dynamic link list

[1w0XoG1T]

i'm not really familiar with this one,.. but can anyone help me make a program
somewhat having this algorithm -


1. add record(node)
2. delete record
3. edit record
4. search and display record
5. display list
6. count records
7. delete records
8. delete list

so far here's what ive done:
-DList.h
-DList.cpp (the one that implements the DList.h)


"DList.h" -
/*------------------------------------------------------------------------------

This header file defines the data type List for processing list,
basic operations are:
Constructor
Destructor
Copy operator
Assignment operator
empty: Check if list is empty
insert: Insert an item
erase: remove an item
display: Output the list
<< : Output operator
------------------------------------------------------------------------------*/

#include <iostream>

#ifndef DLIST
#define DLIST

typedef int ElementType;

class List
{
public:
/***** Function Members *****/
/***** Class constructor *****/
List(int maxSize = 1024);

/***** Class distructor *****/
-List();

/***** Copy Constructor *****/
List(const List & origList);

/***** Assignment operator *****/
const List & operator=(const List & rightHandSide);

/***** empty operation *****/
bool empty() const;

/***** insert and erase *****/
void insert(ElementType item, int pos);

void erase(int pos);

/***** output *****/
void display(ostream & out) const;

private:

int mySize;
int myCapacity;
ElementType * myArray;

}; //---end of List class

ostream & operator<< (ostream & out, const List & aList)

#endif
//end of "DList.h"

"DList.cpp" -

/*-- DList.cpp ------------------------------------------------------------
This file implements list member functions.
----------------------------------------------------------------------------*/

#include <cassert>
#include <new>
using namespace std;

#include "DList.h"

List::List(int maxSize)
: mySize(0), myCapacity(maxSize)
{
myArray = new(nothrow) ElementType[maxSize];
assert(myArray != 0);

}

List::-List()
{
delete [] myArray;
}

List::List(const List & origList)
: mySize(origList.mySize), myCapacity(origList.myCapacity)
{
myArray = new(nothrow) ElementType[myCapactiy];

if (myArray != 0)
for(int i = 0; i < mySize; i++_
myArray[i] = origList.myArray[i];
else
{
cerr << "*** Omadeqiate memory to allocate storage for list ***\n";
exit(1);
}
}

const List & aList::operator=(const List & rightHandSide)
{
if (this != &rightHandSide)
{
if (myCapacity != rightHandSide.myCapacity)
{
delete[] myArray;
myCapacity = rightHandSide.myCapacity;
myArray = new(nothrow) ElementType[myCapacity];

if (myArray == 0)
{
cerr << "*Inadequate memory to allocate stack ***\n";
exit(1);
}
}
mySize = rightHandSide.mySize;
for(int i = 0; i < mySize; i++)
myArray[i] = rightHandSide.myArray[i];
}
return *this;
}

bool List::empty() const
{
return mySize == 0;
}

void List::display(ostream & out) const
{
for(int i = 0; i < mySize; i++)
out << myArray[i] << " ";
}

ostream & operator<< (ostream & out, const List & aList)
{
aList.display(out);
return out;
}

void List::insert(ElementType item, int pos)
{
if(mySize == CAPACITY)
{
cerr << "*** No space for list element -- terminating "
"execution ***\n";
exit(1);
}
if(pos < 0 || pos > mySize)
{
cerr << "*** Illegal location to insert -- " << pos
<< ". List unchange. ***\n";
return;
}

// First shift array elements right to make room for item

for(int i = mySize; i > pos; i--)
myArray[i] = myArray[i - 1];

// Now insert item at position pos and increase list size
myArray[pos] = item;
mySize++;
}

void List::erase(int pos)
{
if(mySize == 0)
{
cerr << "*** List is empty ***\n";
return;
}
if(pos < 0 || pos >= mySize)
{
cerr << "Illegal location to delete -- " << pos
<< ". List unchange. ***\n";
return;
}

// Shift array elements left to close the gap
for(int i = pos; i < mySize; i++)
myArray[i] = myArray[i + 1];

// Decrease list size
mySize--;
}
//end of "DList.cpp"


* as long as the algorithm is concenred,.. i hope anyone can help me with this one.. thanks in advance

[tummychow]

Code tags.

[somshekhar]

Do step by step:
(1) you want to create a node , so have a structure that contains your data field and the address of the next node.
(2) Don't set the size.Let the compiler gives u error when it is unable to create the node.
(3) Inside the class whenever you are inserting a node, create a new node and there increase the entries,
and if u want to set the limit of entries , you can have this entry as a check.
(3) Now i felt u r making a single linked list, that means you can traverse in a single direction, so be care ful while deleting a node.

I have changed your code, let me know if you dont understand.
check for effiecincy.

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include<iostream.h>
#include<math.h>

template<class Itemtype> struct Node;
template <class Itemtype>
 struct Node
{
	Itemtype mItem;
	 Node<Itemtype> *mNext;
    
};

template <class itemtype>
class List
{
Node<itemtype> *mFirst;
Node<itemtype> *mLast;
int mEntries;	
public:
		List();
		~List();
		Node<itemtype>* GetFirstNode(){return mFirst? mFirst: NULL;}
		Node<itemtype>* GetLastNode(){return mLast? mLast: NULL;}
		int GetEntries(){ return mEntries;}
		void DisplayNode();
		void InsertNodeAtFirstPosition(itemtype item);
		void InsertNodeAtLastPosition(itemtype item);
		void InsertNode(itemtype item,bool bFirst=false);
		void DeleteNode(itemtype item);
		void DeleteFirstNode();
		void DeleteLastNode();
		void DeleteNodeAtPosition(int iPosition);
		Node<itemtype>* GetNode(itemtype item);
		void EditNode(itemtype currentItem,itemtype newItem);
	
};
template <class itemtype>
List<itemtype>::List():mEntries(0),mFirst(NULL),mLast(NULL)
{

}
template <class itemtype>
void List<itemtype>::DisplayNode()
{
	if(mEntries)
	{
		cout<<"Num of entries="<<mEntries<<endl;
		Node<itemtype> *tempNode;
		tempNode = mFirst;
		while(tempNode!=NULL)
		{
			cout<<tempNode->mItem<<endl;
			tempNode = tempNode->mNext;
		}
	}
	else
	{
		cout<<"No nodes to display"<<endl;
	}
}

template <class itemtype>
void List<itemtype>::InsertNodeAtFirstPosition(itemtype item)
{
	
	Node<itemtype> *pNode = new Node<itemtype>;
	pNode->mItem = item;
	//check for no Nodes
	if(!mFirst)
	{
		pNode->mNext = mFirst;
		mFirst = pNode;
		mLast = pNode;
	}
	else
	{
		pNode->mNext = mFirst;
		mFirst = pNode;
	}
	mEntries++;
}
template <class itemtype>
void List<itemtype>::InsertNodeAtLastPosition(itemtype item)
{
	Node<itemtype> *pNode = new Node<itemtype>;
	pNode->mItem = item;
	//check if there are no nodes
	if(!mLast)
	{
		pNode->mNext = mLast;
		mLast = pNode;
		mFirst = pNode;
	}
	else
	{
		mLast->mNext = pNode;
		pNode->mNext = NULL;
		mLast = pNode;
	}
}

/*
 *	Function : InsertNode
 *	Details  : if the flag bFirst is false then by default the node will be inserted at the last
 *	           else if the flag is set to true, the node will be appended at the front.
 */
template <class itemtype>
void List<itemtype>::InsertNode(itemtype item,bool bFirst/*=false*/)
{
	Node<itemtype> *pNode = new Node<itemtype>;
	pNode->mItem = item;
	//check if there are no nodes
	if(!mLast)
	{
		pNode->mNext = mLast;
		mLast = pNode;
		mFirst = pNode;
		
		
	}
	else
	{
		if(bFirst)
		{
			pNode->mNext = mFirst;
			mFirst = pNode;
		}
		else
		{
			mLast->mNext = pNode;
			pNode->mNext = NULL;
			mLast = pNode;
		}
	}
	mEntries++;
}
template <class itemtype>
List<itemtype>::~List()
{
	if(mEntries)
	{
		Node<itemtype> *currentNode;
		Node<itemtype> *aheadNode;
		currentNode = mFirst;
		while(currentNode!=NULL)
		{
			aheadNode = currentNode->mNext;
			delete currentNode;
			currentNode = aheadNode;
			
		}
	}
}
template <class itemtype>
void List<itemtype>::DeleteNode(itemtype item)
{
	if(mEntries)
	{
		bool bNodeDeleted = false;
		Node<itemtype> *currentNode=NULL;
		Node<itemtype> *previousNode=NULL;
		currentNode = mFirst;
		while(currentNode!=NULL)
		{
			
			if(currentNode->mItem == item)
			{
				bNodeDeleted = true;
				/*
				 *
				 *	If deleting the first node, the previous node will be null,
				 *	so assigning the next node to be the first.
				 */
				if(currentNode == mFirst)
				{
					 mFirst=currentNode->mNext ;
				}
				else if(currentNode == mLast)
				{
					/*
					 *	if deleting the last node, then currentNode->mNext will be NULL,
				     *	so assigning the previous node to be last.
					 */
					 mLast=previousNode ;
					 mLast->mNext = NULL;
				}
				else
					previousNode->mNext = currentNode->mNext;

				delete currentNode;
				mEntries--;
				break;
			}
			previousNode = currentNode;
			currentNode  = currentNode->mNext;
			
		}
		if(!bNodeDeleted)
		{
			cout<<"Node"<<item<<" not found"<<endl;
		}
	}
	else
	{
		cout<<"There are no items to delete in the list"<<endl;
	}
}

template <class itemtype>
void List<itemtype>::DeleteFirstNode()
{
	if(mEntries)
	{
		/*
			if the number of entries is one
		*/
		Node<itemtype> *pCurrentNode = NULL;
		pCurrentNode = mFirst;
		if(pCurrentNode == mLast)
		{
			delete pCurrentNode;
			mFirst = mLast = NULL;
			mEntries = 0;
		}
		else
		{
			mFirst = pCurrentNode->mNext;
			delete pCurrentNode;
			mEntries--;

		}
	

	}
	else
	{
		cout<<"No Entries found"<<endl;
	}
}

template <class itemtype>
void List<itemtype>::DeleteLastNode()
{
	if(mEntries)
	{
		/*
			if the number of entries is one
		*/
		Node<itemtype> *pCurrentNode = NULL;
		Node<itemtype> *pPreviousNode = NULL;
		pCurrentNode = mFirst;
		if(pCurrentNode == mLast)
		{
			delete pCurrentNode;
			mFirst = mLast = NULL;
			mEntries = 0;
		}
		else
		{
			while(pCurrentNode !=NULL)
			{
				pPreviousNode = pCurrentNode;
				pCurrentNode = pCurrentNode->mNext;
			}
			delete pCurrentNode;
			mEntries--;
			mLast = pPreviousNode;
			mLast->mNext = NULL;

		}
	

	}
	else
	{
		cout<<"No Entries found"<<endl;
	}
}
template <class itemtype>
void List<itemtype>::DeleteNodeAtPosition(int iPosition)
{
	if(mEntries)
	{
		if(abs(iPosition) <= mEntries)
		{
			int iWalker = 0;
			Node<itemtype> *pCurrentNode = NULL;
			Node<itemtype> *pPreviousNode = NULL;
			pCurrentNode = mFirst;
			/*
				if we are deleting the first entry
			*/
			if(pCurrentNode == mLast)
			{
				DeleteFirstNode();
			}
			else
			{
				while(pCurrentNode != NULL)
				{
					iWalker++;
					if(iWalker == iPosition)
					{
						pPreviousNode->mNext = pCurrentNode->mNext;
						delete pCurrentNode;
						mEntries--;
						break;
					}
					pPreviousNode = pCurrentNode;
					pCurrentNode = pCurrentNode->mNext;
					
				}
			}
			
		}
		else
		{
			cout<<"Position"<<iPosition <<"is not valid"<<endl;
		}
	}
	else
	{
		cout<<"No Entry found:"<<endl;
	}


}

template <class itemtype>
Node<itemtype>* List<itemtype>::GetNode(itemtype item)
{
	if(mEntries > 0)
	{
		Node<itemtype> *pCurrentNode = mFirst;
		while(pCurrentNode != NULL)
		{
			if(pCurrentNode->mItem == item)
				return pCurrentNode;
			pCurrentNode = pCurrentNode->mNext;
		}
		return NULL;
	}
	return NULL;
}
template <class itemtype>
void  List<itemtype>::EditNode(itemtype currentItem,itemtype newItem)
{
	Node<itemtype> * pRequiredNode = GetNode(currentItem);
	if(pRequiredNode != NULL)
	{
		pRequiredNode->mItem = newItem;
	}
	else
	{
		cout<<"Node"<<currentItem<<" not found"<<endl;
	}
}

#endif