feedback for ADT Sort Linked List

[techjohnny]

Just looking for some helpful feedback on an ADT Sorted Linked List constructor.

SortLabListP.H

 //*********************************************************
// Header file LabListP.h for the ADT list.
// Pointer-based implementation.
// The first "position" in a list is position = 1,
//   as implemented in the insert(), remove(), retrieve(),
//   and private ptrTo() methods.
//*********************************************************

//*********************************************************
// The "typedef" below must be configured for the type
//   of data stored in each node in the list
//*********************************************************
//typedef desired - type - of - list - item ListItemType;
typedef int SortListItemType;

class SortListClass
{
public:
	// constructors and destructor:
	SortListClass();                    // default constructor
	~SortListClass();                   // destructor

	SortListClass(const SortListClass& existingList);    // copy constructor
	SortListClass& operator=(const SortListClass& rhs);  // assignment operator

	// list operations:
	bool isEmpty() const;
	int  getLength() const;

	// Methods return true if successful, false otherwise
//	bool insert(int position, SortListItemType& newItem);
	bool insert(SortListItemType& newItem);

	bool remove(int position);
	
	bool retrieve(int position, SortListItemType& dataItem) const;
	void PrintsortList(); 
	int find(SortListItemType& dataItem) const;
	void SortListClass::deleteItem(int deleteItem);
	void DestoryNode();
private:
	struct SortListNode
	{
		SortListItemType  item;
		SortListNode     *next;
	};

	int       size;  // number of items in list
	

	SortListNode *head;  // pointer to linked list of items
	SortListNode *last;
	SortListNode *ptrTo(int position) const;
	// Returns a pointer to the node at position (1 .. k) in list
};

SortLabListP.cpp

//*******************************************************
// Implementation file LabListP.cpp for the ADT list.
// Pointer-based implementation.
//*******************************************************
#include "SortLabListP.h"     // header file
#include <cstddef>        // for NULL
#include <cassert>        // for assert()
#include <iostream>
using namespace std;
SortListClass::SortListClass()	  // Default Constructor
: size(0), head(NULL)
{
}


SortListClass::~SortListClass()	// Destructor
{
	bool success;

	while (!isEmpty())
	{
		success = remove(1);  // Repeatedly delete item 1
	}
}


bool SortListClass::isEmpty() const
{
	return bool(size == 0);
}


int SortListClass::getLength() const
{
	return size;
}


// Copy Constructor: Make DEEP copy
SortListClass::SortListClass(const SortListClass& existingList)
: size(existingList.size)
{
	if (existingList.head == NULL)
		head = NULL;  // original list is empty

	else
	{
		// copy first node
		head = new SortListNode;
		assert(head != NULL);  // check allocation

		head->item = existingList.head->item;

		// copy rest of list
		SortListNode *newPtr = head;  // new list pointer


		// newPtr points to last node in new list
		// origPtr points to nodes in original list
		for (SortListNode *origPtr = existingList.head->next;
			           origPtr != NULL;
			           origPtr = origPtr->next)
		{
			newPtr->next = new SortListNode;   // link new node to end of list
			assert(newPtr->next != NULL);
			newPtr = newPtr->next;

			newPtr->item = origPtr->item;  // copy the data
			newPtr->next = NULL;
		}
	}
}

// assignment operator: Make DEEP copy
SortListClass& SortListClass::operator=(const SortListClass& rhs)
{
	// TODO
	// Similar to Copy Constructor, except
	// - Avoid self-assignments such as  “X = X;”
	// - Delete existing this-instance content before 
	//   making this-instance a copy of the rhs instance
	
	return(*this);
}


// ----------------------------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: position is the number of the desired node.
// Postcondition: Returns a pointer to the desired node.
// If position < 1 or position > size (the number of nodes in the list),
//    returns NULL.
// ----------------------------------------------------------------------

SortListClass::SortListNode *SortListClass::ptrTo(int position) const
{
	if ((position < 1) || (position > size))
		return NULL;

	else  // count from the beginning of the list
	{
		
		SortListNode *cur = head;

		for (int skip = 1; skip < position; ++skip)
			cur = cur->next;

		return cur;
	}
}


bool SortListClass::retrieve(int position, SortListItemType& dataItem) const
{
	bool success = bool( (position >= 1) && (position <= size) );
	success = true;
	if (success)
	{
		// get pointer to node, then data in node
		SortListNode *cur = ptrTo(position);

		dataItem = cur->item;
	}

	return(success);
}



//bool SortListClass::insert(int position, SortListItemType& newItem)
//{
//	int newLength = size + 1;
//
//	// check parameter validity
//	bool success = bool( (position >= 1) && (position <= newLength) );
//
//	if (success)
//	{
//		// create new node and place newItem in it
//		SortListNode *newPtr = new SortListNode;
//		if(newPtr == NULL)
//			return(false);  // cannot insert - allocation failed
//
//		size = newLength;
//
//		newPtr->item = newItem;
//
//		// attach new node to list
//		if (position == 1)
//		{
//			// insert new node at beginning of list
//			newPtr->next = head;
//			head = newPtr;
//		}
//
//		else
//		{
// 			// insert new node to right of previous node
// 			SortListNode *prev = ptrTo(position - 1);
//
//			// insert new node to right of prev
//			newPtr->next = prev->next;
//			prev->next = newPtr;
//		}
//	}
//
//	return(success);
//}

bool SortListClass::insert(SortListItemType& newItem) {
	
	SortListNode *prev = NULL;   SortListNode *cur = head;




	while ((cur != NULL) && (newItem > cur->item)) 
	{ 
		prev = cur;    
		cur = cur->next; 
	
		
		
	}

	SortListNode *newPtr = new SortListNode;  newPtr->item = newItem;

	newPtr->next = cur;

	if (prev == NULL)   head = newPtr;   else   prev->next = newPtr;
	size++;
	return(0);
}

void SortListClass::PrintsortList()
{
	SortListNode *cur;
	cur = head;
	while (cur != NULL)
	{
		
		std::cout << cur->item << endl;
		cur = cur->next;
	}
}



void SortListClass::deleteItem(int deleteItem)
{

	SortListNode *cur;
	SortListNode *trail;

	bool found;
	if (head == NULL)
		cout << "Cannot delete from an empty list" << endl;
	else
	{
		cur = head;
		found = false;
		while (cur != NULL && !found)
		{
			if (cur->item >= deleteItem)
			{
				found = true; size--;
			}
			
			else
			{
				trail = cur;
				cur = cur->next;
			}
			if (cur == NULL)
				cout << "The item to be deleted is not in the list" << endl;
			else
				if
					(cur->item == deleteItem)
				{
					head = head->next;
					if (head == NULL)
						last = NULL;
					
					delete cur;
					
				}
				else
				{
					trail->next = cur->next;
					if (cur == last)
					{
						last = trail;
						
						delete cur;
						
					}
					else

						cout << "The item to be deleted is not in the list " << endl;
				}

		}
	}

}

int SortListClass::find(SortListItemType& dataItem) const
{
	SortListNode *cur; 
	bool found = false;
	cur = head;
	int count = 0;
	while (cur != NULL)

	{

		if (cur->item == dataItem)
			return count;

		else
		{
			count++;
			cur = cur->next;
		}
	}


	
	return false;

}

bool SortListClass::remove(int position)
{
	
	SortListNode *cur;

	bool success = bool((position >= 1) && (position <= size));

	if (success)
	{
		--size;

		if (position == 1)
		{
			// delete the first node from the list
			cur = head;  // save pointer to node
			head = head->next;
		}

		else
		{
			SortListNode *prev = ptrTo(position - 1);

			// delete the node after the node
			//    to which prev points

			cur = prev->next;  // save pointer to node
			prev->next = cur->next;
		}

		// return node to system
		cur->next = NULL;	// safety - remove node from list
		delete cur;
		cur = NULL; 		// safety
	}

	return(success);
}


void SortListClass::DestoryNode()
{
	SortListNode *temp;

	while (head != NULL)

	{
		temp = head;
		head = head->next;
		delete temp;
	}
	last = NULL;
		
}

[jonnin]

assuming it works, it looks pretty good.. random thoughts late at night say

bool isEmpty() const;
int getLength() const;

Why bother? If length is 0, its empty. Right? Doesn't hurt anything, if you like it that way.

the names of your methods are either confusing or imply redundancy. I mean, if you hand me this to use, I have to ask you stuff:

what is the difference in usage for remove, destroy node and delete item? Find and retrieve? I can figure it out, but it needs to be told to the user by the function's name alone, even if wordy.

If it were mine, conceptually the "this one" created by the user would be the "head" (regardless of its variable name). When you make a variable of this type, what is it? Does that variable have data, or is it just a handle into the class, with empty innards?

[dhayden]

SortLabListP.cpp:
line 12: last is uninitialized.
Lines 19 & 23: success is unnecessary.
Copy Constructor: last is uninitialized.
Assignment operator: consider implementing this and then using it to implement copy constructor. E.g.:

SortListClass::SortListClass(const SortListClass& existingList)
    : size(0), head(nullptr), last(nullptr)
{
    *this = existingList;
}

SortListClass::retrieve: why not:

bool
SortListClass::retrieve(int position, SortListItemType& dataItem) const
{
	SortListNode *cur = ptrTo(position);
	if (cur) {
		dataItem = cur->item;
	}
	return cur;
}

I think the logic in deleteItem is flawed, or maybe I'm just having trouble following it:
Line 227: If cur->item > deleteItem then found = true??
Line 241: How do you know that head is the one to delete?

Line 303: each time through the loop, the size of the list shrinks?