Deletion from a circular linked list

[helixprog]

Hello there,

I have been having a few problems recently while getting to grips with a template circular linked list for learning purposes. Sometimes when I try to delete from the first node in the list, it will either delete that node or delete that and the node after it or the program crashes.

Every other item in the list I am successful in deleting including the last.
For example,

Apple <- Pear
Orange Banana
Pear
Banana

Another problem is if I delete Banana first and then apple thereafter the program will crash and I will get this error,

Exception thrown: read access violation.
std::_String_alloc<std::_String_base_types<char,std::allocator<char> > >::_Mysize(...) returned 0xFFFFFFFFFFFFFFFF.

I will attach the code for the creation of the linked list node and deletion
I am thinking there is a problem with the deletion function but I have no idea what. If anyone could share some insight into this it would be much appreciated,

Thanks in advance.

// for deletenode
  nodeType<Type> *current; 
	nodeType<Type> *trailCurrent; 
	
	bool found;

	if (first == NULL)    
		cout << "Cannot delete from an empty list."
		<< endl;
	else
	{
		if (first->info == deleteItem) 
		{
			current = first;
			count--;
			if (first->link == first) 
			{
				first = NULL;
				last = NULL;
			}
			else if (first->link == last) 
			{
				first = first->link;
				first->link = first;
				last = first;
			}
			else
			{
				first = first->link;
				last->link = first;
				
				
			}
			delete current;
		}
		else 
		{
			found = false;
			trailCurrent = first; 
			current = first->link; 
 
			
			while (current != NULL && !found)
				if (current->info != deleteItem)
				{
					trailCurrent = current;
					current = current->link;
				}
				else
					found = true;
			if (found) 
			{

				trailCurrent->link = current->link;
				if (current == last)
					first = first->link;

				delete current;
			
				count--;
				
				 

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

// creation of the node inserted last
nodeType<Type> *newNode; 
	newNode = new nodeType<Type>; 
	newNode->info = newItem; 
	if (first == NULL) 
	{
		first = newNode;
		last = first;
		last->link = first;
	}
	else   
	{
		newNode->link = last->link;
		last->link = newNode; 
		last = newNode;
	}
	count++;

[ne555]

> if (first == NULL)
I'll recommend you to create a list with an empty header cell.

class list{
   node header; //note that it's not a pointer
   list(){
      header.link = &header; //points to itsef
   }
};

that way all your pointers would always be valid/dereferenceable.


> I will attach the code for the creation of the linked list node and deletion
I want to simply run your program through a debugger.
Then may focus on what to read.

[helixprog]

Thank you for your advice, the above functions are derived from an ADT linked list type. The functions insert and delete as virtual functions.

My program is split across different files I will try and condense it into a small program in main.

Part of the ADT function template,

template <class Type>

struct nodeType
{
	Type info;
	nodeType<Type> *link;
	
};

template <class Type>
class LinkedListType
{
public:

void initializeList();
	//Initialize the list to an empty state.
	//Postcondition: first = NULL, last = NULL, count = 0; 

protected:
	int count; //variable to store the number of list elements
			   //
	nodeType<Type> *first; //pointer to the first node of the list
	nodeType<Type> *last; //pointer to the last node of the list
	nodeType<Type> header; // dummy node <-------

I am unsure of how to implement what you suggested, add the dummy header in the ADT class members along with first and last and also the header.link = &header;

in the default constructor?

Thanks

[dhayden]

You don't need the case at lines 22-27. When deleting the first node, the only special case is when it's the only node. If there are multiple nodes and you're deleting the first then the last doesn't change. So lines 22-24 should be:

} else {
    first = first->link;
}

Line 44: since it's a circular list, current will never be NULL. This should be
while (trailCurrent != last && !found)

Line 57 is wrong. If you're deleting the last node then you want to do:
last = trailCurrent;

This is untested, but I think you can combine all of this like so:

    for (trailCurrent=NULL, current = first;
         current && trailCurrent != last;
         trailCurrent = current, current = current->link) {

        if (current->info == deleteInfo) {
            if (trailCurrent) {
                // deleting 2nd-Nth
                trailCurrent->link = current->link;
                if (current == last) {
                    last = trailCurrent;
                }
            } else {
                // deleting first
                if (current == last) {
                    first = last = NULL; // deleting only node
                } else {
                    first = last->link = current->link;
                }
            }
            delete current;
            --count;
            break;
        }
    }

[helixprog]

dhayden,

Thank you so much for your input the code worked perfectly.