Circular Linked List RANGE DELETION!

Mar 16, 2015 at 6:12pm
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.

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
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;
}
Mar 16, 2015 at 6:57pm
help please!
Mar 16, 2015 at 7:42pm
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.
Last edited on Mar 16, 2015 at 8:29pm
Mar 16, 2015 at 8:08pm
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

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


1
2
3
4
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
Last edited on Mar 16, 2015 at 8:11pm
Mar 17, 2015 at 1:12am
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?

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
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;
}
Mar 17, 2015 at 1:30am
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
Mar 17, 2015 at 5:37am
bump help please!
Mar 17, 2015 at 7:00am
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.
Last edited on Mar 17, 2015 at 7:10am
Mar 17, 2015 at 7:27am
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
Last edited on Mar 17, 2015 at 7:38am
Mar 17, 2015 at 7:44am
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?
Mar 17, 2015 at 8:07am
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

1
2
3
4
5
6
7
8
9
10
11
12
13
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
Last edited on Mar 17, 2015 at 8:09am
Mar 17, 2015 at 1:05pm
That does still feel a bit fishy.

1
2
3
4
5
6
7
8
9
10
11
12
13
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.
Mar 17, 2015 at 6:02pm
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

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
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;
}
Last edited on Mar 17, 2015 at 6:03pm
Mar 17, 2015 at 9:17pm
Ok, when last element is removed cursor points to nullptr now
I think this covers all cases now, not tested though

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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?
Last edited on Mar 17, 2015 at 9:23pm
Mar 17, 2015 at 9:59pm
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.
Last edited on Mar 17, 2015 at 10:13pm
Mar 17, 2015 at 10:20pm
oh yeah, stupid me didn't think about it
I forgot the else statement.
It should not move if the next one is deleted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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);
Last edited on Mar 17, 2015 at 10:22pm
Topic archived. No new replies allowed.