linked list implementation

[unregistered]

can someone help me check whether my linked list implementation is correct, as in without any logic errors? Do comment on any possible improvements that could be done as well

#include<iostream>

using namespace std;

struct Node
{
	int data;
	Node *next;
};

struct HeadNode
{
	int count;
	Node *headPtr;
};

class LinkedList
{
	public:
		LinkedList();
		~LinkedList();

		void addToHead( int );
		bool removeFromHead();

//		bool addToTail( int );
//		bool removeFromTail();

		void addNode( int );
		bool deleteNode( int );
		void deleteAllNodes();

		bool isEmpty();
		int getNoOfNodes();

		void displayAllNodes();

	private:
		int dataCmp( int, int );
		void displayNode( Node* );

		HeadNode head;

};

LinkedList::LinkedList()
{
	head.count = 0;
	head.headPtr = NULL;
	return;
}

LinkedList::~LinkedList()
{
	deleteAllNodes();
	return;
}

void LinkedList::addToHead( int newData )
{
	Node *pNew = new Node;
	pNew -> data = newData;
	pNew -> next = head.headPtr;
	head.headPtr = pNew;
	head.count++;
}

bool LinkedList::removeFromHead()
{
	bool exit;
	Node *temp;

	if ( head.headPtr )
	{
		temp = head.headPtr;
		head.headPtr = head.headPtr -> next;
		delete temp;
		head.count--;
		exit = true; // returns true if successful
	}
	else
		exit = false; // returns false if unsuccessful

	return exit;
}

/*
bool LinkedList::addToTail( int )
{

}
bool LinkedList::removeFromTail()
{

}
*/

void LinkedList::addNode( int newData )
{
	Node *pNew = new Node,
	     *pPre = NULL,
	     *pCur = head.headPtr;
	pNew -> data = newData;

	while ( pCur && dataCmp( pNew -> data, pCur -> data ) >= 0 )
	{
		pPre = pCur;
		pCur = pCur -> next;
	}

	if ( pPre )
	{
		pNew -> next = pPre -> next;
		pPre -> next = pNew;
		head.count++;
	}
	else
	{
		pNew -> next = head.headPtr;
		head.headPtr = pNew;
		head.count++;
	}
	
}

bool LinkedList::deleteNode( int data )
{
	bool exit;
	Node *pPre = NULL,
	     *pCur = head.headPtr;

	while ( pCur && dataCmp( pCur -> data, data ) < 0 )
	{
		pPre = pCur;
		pCur = pCur -> next;
	}

	if ( pCur && dataCmp( pCur -> data, data ) == 0 )
	{
		if ( pPre )
		{
			pPre -> next = pCur -> next;
			delete pCur;
			head.count--;
			exit = true; // return true if successful
		}
		else
		{
			head.headPtr = pCur -> next;
			delete pCur;
			head.count--;
			exit = true; // return true if successful
		}
	}
	else
		exit = false; // return false if unsuccessful

	return exit;
}

void LinkedList::deleteAllNodes()
{
	Node *temp;

	while ( head.headPtr )
	{
		temp = head.headPtr;
		head.headPtr = head.headPtr -> next;
		delete temp;
		head.count--;
	}

	return;
}

bool LinkedList::isEmpty()
{
	return head.count == 0;
}


int LinkedList::getNoOfNodes()
{
	return head.count;
}

void LinkedList::displayAllNodes()
{
	Node *pCur = head.headPtr;
	int nodeCount = 1;

	while ( pCur )
	{
		cout << "Node " << nodeCount << ": ";
		displayNode( pCur );
		cout << endl;

		nodeCount++;
		pCur = pCur -> next;
	}

	return;
}


int LinkedList::dataCmp( int value0, int value1 )
{
	int exit = 0;

	if ( value0 < value1 )
		exit = -1;
	else if ( value0 > value1 )
		exit = 1;

	return exit;
}

void LinkedList::displayNode( Node *node )
{
	cout << node -> data;
	return;
}

void printMenu()
{
	cout << "1. Add to head" << endl;
	cout << "2. Remove from head" << endl;
	cout << "3. Add node " << endl;
	cout << "4. Delete node" << endl;
	cout << "5. Delete all nodes" << endl;
	cout << "6. Is the list empty?" << endl;
	cout << "7. Get number of nodes" << endl;
	cout << "8. Display all nodes" << endl;
	cout << "9. Quit" << endl;
}

int getChoice()
{
	int choice;

	cout << "Select choice: ";
	cin >> choice;
	cin.clear();
	cin.ignore( 200, '\n' );
	return choice;
}

int getData()
{
	int data;

	cout << "Enter data: ";
	cin >> data;
	cin.clear();
	cin.ignore( 200, '\n' );

	return data;
}

void processChoice( int choice, LinkedList& list )
{
	int data;
	bool opStatus;

	switch ( choice )
	{
		case 1: data = getData();
			list.addToHead( data );
			break;
		case 2: if ( list.removeFromHead() )
			{
				cout << "Removed node from head" << endl;
			}
			else
				cerr << "List is empty" << endl;
			break;
		case 3: data = getData();
			list.addNode( data );
			cout << "Node " << data
			     << " added";
			cout << endl;
			break;
		case 4: if ( !list.isEmpty() )
			{
				data = getData();
				if ( list.deleteNode( data ) )
				{
					cout << "Node " << data
					     << " deleted";
					cout << endl;
				}
				else
					cerr << "Node not found" << endl;
			}
			else
				cerr << "List is empty" << endl;
			break;
		case 5: list.deleteAllNodes();
			cout << "All nodes deleted" << endl;
			break;
		case 6: cout << ( list.isEmpty() ? 
			          "List is empty" : "List is not empty" );
			cout << endl;
			break;
		case 7: cout << "No. of nodes: "
			     << list.getNoOfNodes();
			cout << endl;
			break;
		case 8: list.displayAllNodes();
			break;
		default: cout << "Invalid choice" << endl;
	}

}

int main()
{
	LinkedList list;
	int choice;
	do
	{
		printMenu();
		choice = getChoice();

		if ( choice != 9 )
			processChoice( choice, list );

	} while ( choice != 9 );
	


	return 0;
}

[jsmith]

Have you tested your code?

There are many things I'd do to the implementation as a software professional, however for the purposes of a college class it seems fine.

[unregistered]

What would you do as a software professional?

I've tested the code but I'm not sure if I have weeded out all the logical errors.

[CrimsonAngel]

um usulay you might say some thing thats happening and not acting the way you would like it too but i cant see any errors just quick looking at it

Have you tested your code?

I've tested the code but I'm not sure if I have weeded out all the logical errors.

so what happened when you tested it?

[unregistered]

so what happened when you tested it?

Tested then debug tested then debug until it seems to be working fine, but I want to know if there are still any errors or not as well as improvements in efficiency that can be done to the code.

[jsmith]

As a software professional, I would develop a set of test cases:

1) Make sure that every line of code in the linked list implementation got executed
at least once;
2) Determine the "edge" cases and make sure I have tests for them;
3) Test every scenario I can think of that might affect the way the code executes.

Here's a start at a testcase list:
a) addToHead() called on empty list
b) addToHead() called on non-empty list
c) removeFromHead() called with list containing 0 elements;
d) removeFromHead() called with list containing exactly 1 element;
e) removeFromHead() called with list containing >1 element.
f) addNode() called on empty list;
g) addNode() called with list containing 1 element less than the value to insert;
h) addNode() called with list containing 1 element greater than value to insert;
i) addNode() called with list containing 1 element equal to value to insert;
j) g, h, and i with list containing > 1 element;
k) deleteNode() called on empty list;
l) deleteNode() called on list with 1 element, target element does not exist;
m) deleteNode() called on list with 1 element, target element exists;
n) l and m with list containing >1 element;
o) deleteAllNodes() called on empty list;
p) deleteAllNodes() called on non-empty list;
q) isEmpty() called on empty list;
r) isEmpty() called on non-empty list;
s) getNoOfNodes() called on initially empty list;
t) getNoOfNodes() called on non-empty list;
u) getNoOfNodes() called after addNode();
v) getNoOfNodes() called after addToHead();
w) getNoOfNodes() called after removeFromHead();
x) getNoOfNodes() called after deleteNode();
y) displayAllNodes() called on empty list;
z) displayAllNodes() called on non-empty list.

In true blackbox testing, there would still be more testcases I could argue should be executed, however I focused more on whitebox testing since this is development test.
You should write all of the testcases as functions that main() calls.

The bottom line is that software testing cannot prove that code is defect-free; it can only show that bugs do exist by virtue of a failed test case.

[unregistered]

gee must be hard work typing all that out but thanks for the tips, I appreciate it