Circular Linked List RANGE DELETION!

[alex067]

I have to delete the nodes in a circular linked list which contains the values between the min and the max.

For example, the node list looks like this:

20 - > 10 -> 80 -> 60 -> 30 -> 90 -> 15 -> (pointing back to 20)

the min and max values are: 10, 30

Which means, any node which contains the info field between values 10 and 30 get deleted.

So after, it should look like:

20 -> 80 -> 60 -> 90 -> (pointing back to 20)


I am having a compiler error when it reaches my while statement, the main traversing portion.

The node list for this program looks exactly like the example provided above.

void CLinkedList :: deleteInRange(int min, int max)
{
	NodeType *temp = cursor;
	if (IsEmpty())
	{
		cout << "Nothing to delete, the list is empty! Add values please:)" << endl;
		cursor = NULL;
	}
	else
	{
		NodeType *prev;
		while (temp->next != cursor) //traverse whole node till you reach cursor
		{
			if (temp->info >= min && temp->info <= 30)
			{ 
				NodeType *garbage = temp;
				prev = temp->next;
				delete garbage;
			}
			else
				prev = temp; //always staying behind
				temp = temp->next;
		}
		prev = NULL;
	}
	temp  = NULL;
}

[alex067]

help please!

[keskiverto]

This requires thinking.

* Parameter "max" is not used.
* Code contains magic "30".
* The condition does not return true for values in range.
* The condition does return true for values not in range.
* What if cursor it within deleted range?

Do the operation in phases:
1. Find beginning or range 2. Find end of range
3. Do removal, if necessary, and handle special cases

Edit: Different meaning of "range". To me, a range is a set of consecutive elements. Your case is a remove_if, where the predicate has a value range.

[Gamer2015]

20 - > 10 -> 80 -> 60 -> 30 -> 90 -> 15 -> (pointing back to 20)

the min and max values are: 10, 30

Which means, any node which contains the info field between values 10 and 30 get deleted.

So after, it should look like:

20 -> 80 -> 60 -> 90 -> (pointing back to 20)

shouldn't be the 20 deleted as well?


just some little changes, I don't know if it was the way you wanted it to be

if (temp->info >= min && temp->info <= 30) // make it <= max
{

else {// insert bracket
    prev = temp; //always staying behind
    temp = temp->next;
} // insert bracket 

you don't check the value of cursor, you may want to check it too if you want to erase ALL elements in the range

NodeType *prev;
do
{
    if (temp->info >= min && temp->info <= max) // changed max
    { 
        NodeType *garbage = temp;
        prev = temp->next;
        delete garbage;
    }
    else
    { // added bracket
        prev = temp;
        temp = temp->next;
    } // added bracket
} while (temp->next != cursor) //traverse whole node till you reach cursor, also checks cursor 

these are all just little things but i think they add up, I didn't run through the code in detail though, I just assumed that your algorithm will work but that u forgot some little things

[alex067]

Thank you Gamer!

I fixed the small semantic errors, but the problem still persists.

Once again, it is found in the while condition, why is this happening?

void CLinkedList :: deleteInRange(int min, int max)
{
	NodeType *temp = cursor;
	if (IsEmpty())
	{
		cout << "Nothing to delete, the list is empty! Add values please:)" << endl;
		cursor = NULL;
	}
	else
	{
		NodeType *prev;
		do
		{
			if (temp->info >= min && temp->info <= max)
			{
				NodeType *garbage = temp;
				prev = temp->next;
				delete garbage;
				garbage = NULL;
			}
			else
			{
				prev = temp;
				temp = temp->next;
			}
		} while (temp->next != cursor); //traverse whole node till you reach cursor
		prev = NULL;
	}
	temp  = NULL;
}

[alex067]

Ok so I sketched out my code on paper to see if the iteration follows correctly and if I was linking and delinking properly.

I found the source of my problem to come from the de-link processes. I need to re-link the node previous to the cursor, back to the cursor. For example, since my last node value is 15, and 15 is between 10-30, it gets deleted. Thus, I have to re-link the node before that to the cursor.

Can anyone please help me with this

[alex067]

bump help please!

[keskiverto]

How about considering the temp->next for delete, rather than the temp?


Unrelated notes about your code:
* Lines 19, 27 and 29 are unnecessary.
* C++11: use nullptr, not NULL or 0.
* The temp is used only within the scope of else (lines 11-27), so it should be declared there.
* Line 7: if list is empty but cursor is not nullptr, then your other methods are not consistent.

[Gamer2015]

do
{
    if (temp->info >= min && temp->info <= max)
    {
        NodeType *garbage = temp;
        prev = temp->next;
        delete garbage;
    // garbage = NULL;
    }
    else
    {
	prev = temp;
	temp = temp->next;
    }
} while(temp->next != cursor)

Let us go over it part by part
you set garbage to temp
prev to next temp
and delete garbage which results in deleting temp
then you ask if temp-> next == cursor, temp is deleted so this will have problems.

also keep in mind that you may end up delete cursor

[alex067]

garbage = temp;

doesn't this mean that garbage is acting as a holder for temp, and not deleting temp itself?

So is the correct codee:

NodeType *garbage = temp;
temp = temp->next;
delete garbage;
garbage = NULL;

?

@Keskiverto

So are you saying I should initialize garbage to temp->next rather than temp?

[Gamer2015]

garbage = temp;

doesn't this mean that garbage is acting as a holder for temp, and not deleting temp itself?

It just means that garbage now points to the same location as temp.

Keskivetro's Idea is a good one, allways check the next node, so you allways know prev node and can change it's next

do
{
    NodeType *next = temp->next;

    if (next->info >= min && next->info <= max)
    {
        if(temp->next == cursor) // if cursor gets destroyed point cursor to cursors next
            cursor = next->next; 

        temp->next = next->next;
        delete next;
    }
} while(temp != cursor)

this was a simple but surpriseingly complex

[keskiverto]

That does still feel a bit fishy.

auto temp = cursor; // this is where we start

// usual case:
auto dead = temp->next;
if ( dead must die )
{
  temp->next = dead->next; // remove node from list
  delete dead;
}
else
{
  temp = dead; // let live and advance temp
}

// That doesn't cover the special cases

// 1. The list has only one node (left): cursor->next == cursor
// The list may become empty and then: cursor = nullptr

// 2. The list has more than one, and we are looking at the last: temp->next == cursor
// Whether the dead must die or not, this is the end of iteration
// If the dead must die, then and only then the cursor updates to next (remaining) node.

[alex067]

Hm Keskiverto, I kind of understand what you are saying. Are you stating that the iteration is not enough because it will stop the loop once it deletes the first node thats between min and max?

This is what happened in my code, it only deleted 1 node but nothing else.

Currently my node looks like:
20 - 10 - 80 - 60 - 30 - 90 - 15 - back to 20

and after the function call:
20 - 80 - 60 - 30 - 90 - 15 - back to 20

it should look like:
80 - 60 - 90 - back to 80

void CLinkedList :: deleteInRange(int min, int max)
{
	NodeType *temp = cursor;
	if (IsEmpty())
	{
		cout << "Nothing to delete, the list is empty! Add values please:)" << endl;
		cursor = NULL;
	}
	else
	{
		do
		{
			NodeType *prev = temp->next;
			if (prev->info >= min && prev->info <= max)
			{
				if (temp->next == cursor) //incase cursor gets destroyed, point to next node
				{
					cursor = prev->next;
				}
				else
				{
					temp->next = prev->next;
					delete prev;
					prev = NULL;
				}
			}
		} while (temp != cursor); //traverse whole node till you reach cursor
	}
	temp  = NULL;
}

[Gamer2015]

Ok, when last element is removed cursor points to nullptr now
I think this covers all cases now, not tested though

do
{
    NodeType *next = temp->next;

    if (next->info >= min && next->info <= max)
    {
        if(next->next == next) // delete last element
            cursor = nullptr;

        else if(temp->next == cursor) // last element to check
            cursor = next->next; 

        temp->next = next->next; // next node in chain
        delete next;
    }
    temp = temp->next;
} while(temp != cursor && cursor != nullptr);

Uhm, may I be a little curious?
Do you make that CircularBuffer out of fun?

[keskiverto]

That (only 1 deleted) should be elementary:
Line 3 does temp=cursor
Line 27 sees that temp==cursor
You never change the temp.


The Gamer2015 version is quite opposite:
Lets have list:
42, 20, 10, 16.
* temp is at 42
* next is at 20. Will be removed.
* After line 15 the list is 42, 10, 16 and temp is still at 42
* Line 16 moves temp to 10
### next iteration
* next is at 16. Will be removed.
The node 10 was skipped. The temp moves even when it should not.

[Gamer2015]

oh yeah, stupid me didn't think about it
I forgot the else statement.
It should not move if the next one is deleted

do
{
    NodeType *next = temp->next;

    if (next->info >= min && next->info <= max)
    {
        if(next->next == next) // delete last element
            cursor = nullptr;

        else if(temp->next == cursor) // last element to check
            cursor = next->next; 

        temp->next = next->next; // next node in chain
        delete next;
    }
    else // added else
        temp = temp->next;
} while(temp != cursor && cursor != nullptr);