Linked list delete trouble

Infinity08:

Mind giving me an example of all that?

Thanks! :o)

David

Sorry i understand the concept in text but when it comes to programming it with my code, i dont.

David

Which part are you confused about ?

Your current code seems to correctly delete one node from the linked list. You can repeat this deletion process 8 times (in a loop) to delete 8 consecutive nodes.
Keep trailCurrent pointing to the node before those 8, and use current to move over the 8 nodes, and delete them along the way. At the end, all you have to do is update the next pointer for the trailCurrent node (just like you're already doing), and possibly update the last pointer.

Instead of a loop you also could rename your deleteNode into deleteItem and have a new member function deleteNode which can be called recursively:

pseudocode:

  deleteItem(item)
  {
      NodePtr find = findNode(item)
      if  find is not null
            deleteNode(find)
      else
           output "empty list"
  }
 
The findNode would iterate from First until "item" was found. The the current node was returned. If not found NULL was returned.

The deleteNode would check whether the next node is not NULL and if so would call deleteNode passing the next. After the call it would delete the node passed.

That way "Bob" would call deleteNode for "Barker", "Barker" would call deleteNode for "is" and so on and after the whole branch after was deleted, it would delete the node itself.  

Infinity08: K... I tried this thinking that this is what your talking about:

But i get an error after it prints out the list after the delete.
Unhandled exception at 0x0041d7f6 in linkedlists.exe: 0xC0000005: Access violation reading location 0xfeeeff02.

current = first;
            first = first->link;
			trailCurrent = first;
			
            count--;
            if (first == NULL)    //the list has only one node
                last = NULL;
			
            delete current;
 
			current = trailCurrent->link;
 
			delete current;
 
			system("pause");

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

I'm not sure what the piece of code you just posted is intended to do ...

Could you maybe post the entire deleteNode function again, after your modifications.

Ok.

I suggest making a drawing of a linked list (each node represented by a box, with arrows between the representing the links).

Then, re-arrange the arrows repeatedly to remove one node at a time from the linked list. Once you understand how it works on paper, you can implement it.

deleting one node from a linked list goes something like this (where 'node' points to the node just before the one we want to delete) :

        tmp = node->next;                            // tmp now points to the node that has to be deleted
        node->next = node->next->next;     // we bypass the node that will be deleted, and point to the one after that
        delete tmp;                                        // and the node is deleted

To delete multiple nodes, these same three lines are just repeated as needed.

And then to finish it all off, you have to take into account the special cases (like the start and the end of the linked list).

I am unable to get it to work in my code infinity08:

tmp = first->next;
first->next = first->next->next;
delete tmp;

                                              

1:
2:
3:

It was just a quick overview of the operations that need to be done. You don't have to copy it literally. You have to understand it, and then adapt it to your situation.

The error it gives me is:

error C2039: 'next' : is not a member of 'nodeType<Type>'  with [Type=std::string]

David

I understand it, infinity but i cant seem to work it out in code. I know it needs to point to the node in the next node but i am unable to figure out how to go about doing that since there is no "NEXT" in my code.

David

>>>> error C2039: 'next' : is not a member of 'nodeType<Type>'  with [Type=std::string]


The 'next' member is called 'link' in your node template class nodeType.

So replace

   tmp = first->next;
   first->next = first->next->next;
   delete tmp;

by

   tmp = first->link;
   first->link = first->link->link;
   delete tmp;


A tip: if ever you got such an error message from the compiler: take it literally.

The message above clearly said  'next' is NOT a member of nodeType what is true as the member name is 'link'.

>> I know it needs to point to the node in the next node

Indeed.

>> but i am unable to figure out how to go about doing that since there is no "NEXT" in my code.

So, what could you use instead of 'next' in your code ?

But I see Alex already came to the rescue ...

Great! It works now :o) But this time it skips the previous one and just takes the one that is entered and then however many i deside to delete thereafter.

I tried using:

tmp = current->link;
first->link = first->link->link;
delete tmp;

and

tmp = trailCurrent;
first->link = first->link->link;
delete tmp;

but did nothing.

template <class Type>
void unorderedLinkedList<Type>::deleteNode(const Type& deleteItem)
{
    nodeType<Type> *current;
    nodeType<Type> *trailCurrent;
	nodeType<Type> *tmp;
	bool found;
 
    if (first == NULL)
        cout << "Cannot delete from an empty list." << endl;
    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;
                count--;
 
                if (last == current)
				{
                    last = trailCurrent;
				}
 
				cout << first->info << endl;
 
                tmp = first->link;
				first->link = first->link->link;
				delete tmp;
 
				tmp = first->link;
				first->link = first->link->link;
				delete tmp;
 
				tmp = first->link;
				first->link = first->link->link;
				delete tmp;
            }else
			{
                cout << "The item to be deleted is not in the list." << endl;
			}
        }
    }
}

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:

>> But this time it skips the previous one

What do you mean ? If you want to start deleting from the previous one, then you just have to make sure to point to one node earlier ...

>>>> tmp = current->link;
>>>> first->link = first->link->link;
>>>> delete tmp;

The sequence above is for deleting one single node in the chain and chaining (linking) the previous with the next, e. g. if you have a list with 6 nodes

   RN -> N1 -> N2 -> N3 -> N4 -> N5 -> 0

and current is N2, then the above code would unlink the N3 and delete it and would link N2 to N4.

     RN -> N1 -> N2 -> N4 -> N5 -> 0

So, if you would like to delete N4 and N5 as well you would need to keep the N2 as current and repeat the above sequence until current->link is NULL.

But actually the deleteNode rarely will/should delete more than one node but only one node. You would iterate from root until you find the node you want to delete, then make the previous of the found node the current (deleting the root node would be a special case to handle) and apply the above statements. You best safe the 'previous' node with each iteration so that the pointer variable already is filled when you found the node to delete.

I thought thats what i was doing with this code, itsmeandnobodyelse:

tmp = trailCurrent;
first->link = first->link->link;
delete tmp;

But i get an error of:
Unhandled exception at 0x0041b6d3 in linkedlists.exe: 0xC0000005: Access violation reading location 0xfeeeff0a.

and thats on the line of the next node:

tmp = first->link;
first->link = first->link->link;    // <-error on this line
delete tmp;

Right now i have "bob, barker, 1, 2, 3, 4, 5, 6, 7, 8" and when i type in barker it shows this:

bob, 6, 7, 8

However, when the user types in barker, i need it to take away bob as well. Thats where i am stuck and thought the code above was taking the previous node (bob) and deleting that as well..

David

>>>> Access violation reading location 0xfeeeff0a.

Hmm. You are dealing with tmp and trailCurrent but the delete statements operate with first and first->link. If any of those isn't valid it makes kaboom.

Pointers need carefulness. Always check a pointer to be valid before accessing it.

if (first != NULL && first->link != NULL)
{
     // now the statement is safe
     first->link = first->link->link;
}

Can you tell what trailCurrent is? And why you use 'first' instead of 'previous'  as in the code I posted?

trailCurrent = first;
current = first->link;

and "first" is defined in the header file

David

Could we go back to http:#25660584, and start again from there, Stealthrt ? Your code worked at that point, except that it didn't delete the right set of nodes. So, all you had to do, is modify your code there to start deleting at a different node ...

Try that again, and post your modified code here if it doesn't work.

To add to above comment.

In order that the following code should not crash

>>>> tmp = current->link;
>>>> current->link = current->link->link;
>>>> delete tmp;


the linked list must contain at least two valid nodes: current and current->link

The situation where a list has only one node left must be handled seperately.

Alright, i did as you suggested infinity08 but it seems to delete the one before it now BUT now doesn't delete the one that was chosen....

Here is the output:

bob
barker
1
2
3
4
5
6
7
8

Enter the string to be deleted: barker

After deleting barker
barker
5
6
7
8

Press any key to continue . . .

David

template <class Type>
void unorderedLinkedList<Type>::deleteNode(const Type& deleteItem)
{
    nodeType<Type> *current;
    nodeType<Type> *trailCurrent;
	nodeType<Type> *tmp;
	bool found;
 
    if (first == NULL)
        cout << "Cannot delete from an empty list." << endl;
    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;
                count--;
 
                if (last == current)
				{
                    last = trailCurrent;
				}
 
				//delete trailCurrent;
 
                current = first;
				first = first->link;
                trailCurrent = first;
 
				if (first == NULL)    //the list has only one node
                last = NULL;
                        
				delete current;
 
				tmp = first->link;
				first->link = first->link->link;
				delete tmp;
 
				tmp = first->link;
				first->link = first->link->link;
				delete tmp;
 
				tmp = first->link;
				first->link = first->link->link;
				delete tmp;
 
				tmp = first->link;
				first->link = first->link->link;
				delete tmp;
            }else
			{
                cout << "The item to be deleted is not in the list." << endl;
			}
        }
    }
}

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:

>>             trailCurrent = first;
>>             current = first->link;

What if the item to be deleted is in the first node ?


>>                 trailCurrent = current;
>>                 //current = current-> link;

Why did you comment that second line ?


>>             }else
>>                   {
>>                         found = true;
>>             }

I think you're missing a closing } ... Properly indenting your code will help avoid this kind of mistake.


>>                 current = first;
>>                         first = first->link;
>>                 trailCurrent = first;

Why are you starting over ? You already found the first node that needs to be deleted.

The item will never be the first node. It will go by last name and last name is going to be the second node. I took out the comment slashes and i get this now:


bob
barker
1
2
3
4
5
6
7
8

Enter the string to be deleted: barker

After deleting barker
1
6
7
8

Press any key to continue . . .

notice that it now deletes "bob" but leave "1" now.. gerr! This is so crazy. What do i need to change this:

tmp = first->link;
first->link = first->link->link;
delete tmp;

in order for it to delete the 1 as well?

David

>> Why are you starting over ? You already found the first node that needs to be deleted.

Just think about this question ^

The first while loop was there to find the first node to be deleted.

Once you found that node (after the while loop), you need to start deleting the amount of nodes you want, starting with that node.

Alright, this is what i have tried and they all have given me errors:

tmp = current;
first->link = first->link;
delete tmp;
 
and
 
tmp = current;
first->link = first->link->link;
delete tmp;
 
and
 
tmp = first;
first->link = first->link->link;
delete tmp;
 
and
 
tmp = first;
first->link = first->link;
delete tmp;
 
and
 
tmp = trailCurrent;
first->link = first->link->link;
delete tmp;
 
and
 
tmp = trailCurrent;
first->link = first->link;
delete tmp;

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

Why do you think you need to start from first again ?

current is already pointing to the node that needs to be deleted. Just delete that node, and the nodes after it. Do NOT use first. first is the start of the linked list, and you don't want to start deleting there.

I must be missing something because i try this and it does not worth either:

tmp = trailCurrent;
trailCurrent->link = trailCurrent->link->link;
delete tmp;

David

>> trailCurrent->link = trailCurrent->link->link;

This skips the current node, so you also need to delete the current node.

Ok. This still brings an error:

tmp = trailCurrent;
trailCurrent->link = trailCurrent->link;
delete tmp;

I must be going all around the answer....

David

>> Ok. This still brings an error:

Don't just guess. Think about it.


What effect do you think this line has :

>> trailCurrent->link = trailCurrent->link;

? None at all.


You want to delete the node that is pointed to by 'current'.
And you want trailCurrent->link to point to the node after the 'current' node.

Do you understand why ? Do you understand how deleting a node in a linked list works ?
Take a look at this image, and that will hopefully make things clearer :

        http://en.wikipedia.org/wiki/File:Singly_linked_list_delete_after.png

Yes it makes since but like i said, i cant seem to code it like that.

David

>> Yes it makes since but like i said, i cant seem to code it like that.

Why not ?

Remember these three lines I posted earlier :

>>         tmp = node->next;                            // tmp now points to the node that has to be deleted
>>         node->next = node->next->next;     // we bypass the node that will be deleted, and point to the one after that
>>         delete tmp;                                        // and the node is deleted

? If 'node' points to the node before the one that needs to be deleted, then after these 3 lines, that node will be deleted from the linked list.

So, how does that apply to 'trailCurrent' and 'current', if 'current' is the one you want to delete ? Refer to the image if it isn't clear.

current can not be used since it was already deleted....

tmp = current;
current->link = current->link->link;
delete tmp;

David

>> current can not be used since it was already deleted....

What do you mean ? The first time, it's pointing to the node that needs to be deleted. After deleting the node, you make it point to the next one, so that it too can be deleted, etc.


>> tmp = current;
>> current->link = current->link->link;
>> delete tmp;

Ok. Again.

trailCurrent points to the node BEFORE the one that needs to be deleted.
current points to the node that needs to be deleted.

Then you need to execute some code that does a few things :

(a) trailCurrent->link needs to point to the node AFTER the one that needs to be deleted (we skip it)
(b) the node to be deleted needs to be deleted
(c) current now needs to point to the following node that needs to be deleted

Repeat as necessary.

I dont see how trailCurrent is used after it has been deleted by current

trailCurrent->link = current->link;
count--;

if (last == current)
{
last = trailCurrent;
}

current = first;
first = first->link;
trailCurrent = first;

if (first == NULL)
last = NULL;
                       
delete current;

tmp = current;
current->link = current->link->link;
delete tmp;

since trailCurrent  points right back to the first node..

David

You probably should go back to your initial code which seems to be ok beside that it deletes only one node (the node found) but not the requested number of following nodes.

Then you should add the number of nodes to delete after finding the initial node as an argument:

template <class Type>
void unorderedLinkedList<Type>::deleteNode(const Type& deleteItem, int numNodesToDelete)
{
    if (numNodesToDelete < 1)    // nothing to do
    {
         cout << "numNodesToDelete should be 1 or greater" << endl;
         return;
    }
    ...
}


Then, you should use a little helper function which gets a node pointer as argument and the number of nodes to delete after and would return the node pointer the last of those nodes was linked to:

template <class Type>
nodeType<Type> *  unorderedLinkedList<Type>::deleteNodesFrom(nodeType<Type> * node, int numNodesToDelete)
{
     if (node == NULL) return NULL;
     nodeType<Type> * next = node->link;
     int count = 0;

     // put here a do while loop that would first set the next to node->link
     // and then delete the node and increment the counter
     // the loop would stop either if next is NULL or if the counter reached the number of nodes to delete

     do
     {
          ...
     }
     while (...);
     // finally return the next which points to the next node not deleted or NULL
     return next;
}

The function above could be used both for "case 2" where the first node of list needs to get deleted and for the "else" case where one of the middle nodes was the initial node to be deleted.

In "case 2" the pointer returned from above function would become the new first (and last if list now is empty or has one node only) or would be the pointer the previous before the found node (trailCurrent) would link to.

>> I dont see how trailCurrent is used after it has been deleted by current

Ok. Drawing time ...

This is the linked list before the while loop :

                    -----      -----       -----      -----      -----
        first--->| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 |--->NULL
                    -----      -----       -----      -----      -----

We want to delete the node 3 (and those after it), so after the while loop, 'current' points to that node, and 'trailCurrent' points to the node before it :

                    -----      -----       -----      -----      -----
        first--->| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 |--->NULL
                    -----      -----       -----      -----      -----
                                  /\           /\
                                   |            |
                       trailCurrent    current

To delete node 3, we first "skip" it :
                                     ____________
                                    /                      \/
                    -----      -----       -----      -----      -----
        first--->| 1 |--->| 2 |      | 3 |--->| 4 |--->| 5 |--->NULL
                    -----      -----       -----      -----      -----
                                  /\           /\
                                   |            |
                       trailCurrent    current

Then we delete the node :

                                     ____________
                                    /                      \/
                    -----      -----                    -----      -----
        first--->| 1 |--->| 2 |                   | 4 |--->| 5 |--->NULL
                    -----      -----       NULL     -----      -----
                                  /\           /\
                                   |            |
                       trailCurrent    current

'current' now no longer points to an existing node, so we let it point to the next node we want to delete :

                                     ____________
                                    /                      \/
                    -----      -----                    -----      -----
        first--->| 1 |--->| 2 |                   | 4 |--->| 5 |--->NULL
                    -----      -----                    -----      -----
                                  /\                        /\
                                   |                         |
                       trailCurrent                current

So, this time we can delete node 4 in exactly the same way.

Go over these drawings and explanations, and please ask if anything is not clear. As long as you don't understand what's happening, and why, you will not be able to correctly implement this.

First understand it, then write the code.

Well using your examples Infinity08:

                    -----      -----       -----      -----      -----
        first--->| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 |--->NULL
                    -----      -----       -----      -----      -----
                      /\           /\
                      |            |
       trailCurrent    current

Thats what i am trying to do. Where is current = "barker" and trailCurrent = "bob"

I need to start from "bob" and delete down the list til say, the 5th node. Right now, its skipping the node after "barker".

This is how i am reading this code:

found = false; // set to false
trailCurrent = first; // put "bob" into trailCurrent
current = first->link; // set current = to "barker"

while (current != NULL && !found) // make sure there is nodes
{
if (current->info != deleteItem) //check to see if current = "barker"
{
trailCurrent = current; // if so then set "barker" to trailCurrent
current = current-> link; // set current to whatever node is after "barker"
}else
{
found = true; // set it to true
}

if (found)
{
trailCurrent->link = current->link; // set trailCurrent = to current "baker"
count--; // count minus current count

if (last == current) // check to see if "barker" is the last in the node
{
last = trailCurrent; // if it is then set it to last
}

current = first; // I do not know what this does.. would this be "bob"?
first = first->link; // if its "bob" above then this must be "barker"
trailCurrent = first; // sets trailCurrent to "barker" if code above is correct

if (first == NULL) // check to see if first is null
last = NULL; // if so then last must be null
                       
delete current; // delete "bob"

tmp = first->link; // set tmp to "barker"
first->link = first->link->link; // set first to whatever comes next after "barker"
delete tmp; // delete "barker"

etc etc...

David

>> I need to start from "bob" and delete down the list til say, the 5th node.

You're starting off all wrong.

If you want to start deleting from the first node, then that's a special case.

Either way, 'current' should point to the first node (because that's the first node you want to delete).

Instead of starting with a special case, try starting with the basic case - ie. the one I showed. Once you get that to work, you can work on the special cases (involving the start and end of the linked list).

Alright, i've been working on it and still am not getting anywhere.

David