Circular Linked List SPLIT

[alex067]

I have a nodelist of 7 nodes, and since its odd, the first node should contain one extra node than the second one.

Unfortunately, when I try to print the second node, it says the list is empty! and the all the values of the original node are still in place.

the call is on the main():

CLinkedList second; //create a second list as empty
	first.split(second); // split the first into two lists: first and second
	first.printList();
	second.printList();

the code for the actual split function, sorry if its a little messy, I know most of the code could be more compact but here it is:

void CLinkedList :: split(CLinkedList & list)
{
	int size, half;
	size = 1;
	NodeType *temp = cursor;
	bool even;
	if (IsEmpty())
	{
		cout << "List is empty, nothing to split!" << endl;
	}
	else
	{
		while (temp->next != cursor)
		{
			temp = temp->next;
			size++;
		}
	}
	if (size % 2 == 0) // checks if even or odd
	{
		even = true;
		cout << "Size of node is: " << size << ", and it is even!" << endl;
	} 
	else
	{
		even = false;
		cout << "Size of node is: " << size << ", and it is odd!" << endl;
	}
	half = size / 2;
	size = 1; //reinitialize size to restart counter
	//assume nodelist has more than 1 node
	if (even == true) //if the node has even number
	{
		while (temp->next != cursor)
		{
			temp = temp->next;
			size++;
			if (size == half)
			{
				list.cursor = temp->next;
				temp->next = cursor; //delinks and relinks the first node back to cursor
				return;
			}
		}
	}
	else if (even == false)
	{
		while (temp->next != cursor)
		{
			temp = temp->next;
			size++;
			if (size == half+1) //since its odd, first node gets 1 extra node
			{
				list.cursor = temp->next;
				temp->next = cursor; 
				return;
			}

		}
	}

}

[alex067]

help please!

[fg109]

Look at your loop conditions for lines 13, 34, and 48. After you use the first loop to count the size of your linked list, temp->next == cursor and you do not reset it. It'll never run the other loops.

Another problem:

		while (temp->next != cursor)
		{
			temp = temp->next;
			size++;
			if (size == half)
			{
				list.cursor = temp->next;
				temp->next = cursor; //delinks and relinks the first node back to cursor
				return;
			}
		}

So what happens after this? When it gets to line 41, temp->next == cursor. You head back to the top of the loop on line 34, and what happens? The program sees that the loop condition is no longer valid so it stops the loop. The function ends and returns to main. It does not run through the rest of the nodes and make sure that node 7 circles back to node 5 (for your second list).

I shortened your code and fixed a few minor problems (minus what I pointed out above):

void CLinkedList :: split(CLinkedList & list)
{
	int cutoff, size;
	NodeType *temp = cursor;
	if (IsEmpty() || cursor->next == cursor)
	{
		cout << "List has less than 2 nodes, cannot split!" << endl;
		return;
	}
	for (size = 0; temp->next != cursor; ++size)
		temp = temp->next;
	cout << "Size of node is: " << size << ", and it is" << (size % 2 ? "odd" : "even") << "!\n";
	cutoff = size / 2 + size % 2;
	size = 0; //reinitialize size to restart counter
	while (temp->next != cursor)
	{
		temp = temp->next;
		size++;
		if (size == cutoff)
		{
			list.cursor = temp->next;
			temp->next = cursor; //delinks and relinks the first node back to cursor
			return;
		}
	}
}

[alex067]

Thank you for the response!

Several questions:

What is the purpose of the for loop? Simply to traverse through the whole node list and calculate the size?

(size % 2 ? "odd" : "even"), is this saying: if size is divisible by 2, it is odd else it is even? Shouldn't it be the other way around?

What is the purpose of cutoff? I do not understand the initialization of size/2 then you add size mod 2

[fg109]

What is the purpose of the for loop? Simply to traverse through the whole node list and calculate the size?

Yes. The for loop is just like the first while loop you had. Is it more efficient? No, but it shortens the code (2 lines vs 5 lines).

(size % 2 ? "odd" : "even"), is this saying: if size is divisible by 2, it is odd else it is even? Shouldn't it be the other way around?

% is the modulo operator. That means if size % 2 is not 0, then "odd" otherwise "even".

cout << (size % 2 ? "odd" : "even");

is the same as

if (size % 2)
    cout << "odd";
else
    cout << "even";

The efficiency is probably the same, but it shortens the code.

What is the purpose of cutoff? I do not understand the initialization of size/2 then you add size mod 2

That's just your "half" variable. I renamed it because I think it makes more sense, but it really doesn't matter. As for the math, when size is 7:

cutoff = 7 / 2 + 7 % 2 = 3 + 1 = 4

When size is 8:
cutoff = 8 / 2 + 8 % 2 = 4 + 0 = 4

etc.

In other words, size / 2 rounded up.

[alex067]

Ah I see now, thank you!

However, the same problem persists. Nothing is getting printed for the second node! The first node still contains the exact same number of nodes and the second node is still empty!

I think the problem is when I reach the if statement

if (size == cutoff)
		{
			list.cursor = temp->next;
			temp->next = cursor; //delinks and relinks the first node back to cursor
			return;
		}

Does this correctly place the cursor of the second node and delinks/relinks the first node back to itself?

[fg109]

fg109 wrote:

Look at your loop conditions for lines 13, 34, and 48. After you use the first loop to count the size of your linked list, temp->next == cursor and you do not reset it. It'll never run the other loops.

fg109 wrote:

Another problem: (...) It does not run through the rest of the nodes and make sure that node 7 circles back to node 5 (for your second list).

fg109 wrote:

I shortened your code and fixed a few minor problems (minus what I pointed out above):

[alex067]

For the first problem, then to reset it I simply initiate temp to NULL, then reinitiate to cursor correct?

The second problem, would I have to construct another while loop for the second node to make sure it links back to itself?

[Gamer2015]

Okey so you have 7 Nodes stored in buffer A and you want to "split" the nodes in 2 buffers, A and B where A contains 4 and b 3 of the Nodes, right?

Which 4 should A contain and which 3 b?

I'll assume A should contain the first 4 elements for the time being (correct me if i am wrong!)

Ok now a quick look at your code:

void CLinkedList :: split(CLinkedList & list)
{
	int size, half;
	size = 1;
	NodeType *temp = cursor;
	bool even;

	if (IsEmpty())
	{
		cout << "List is empty, nothing to split!" << endl;
	}
	else
	{
		while (temp->next != cursor)
		{
			temp = temp->next;
			size++;
		}
	}

// Should't all of this be in the else statement?
// I mean, you don't want to do anything if the buffer is empty 
	if (size % 2 == 0) // checks if even or odd
	{
//... 
        }

okey, so now I'm going in more detail, I didn't take a look at the rest of your code, just noticed that this should be inside the else bracket.

I'd start by making a Method to get a node _position away from _startNode
Also I'd make a Method to count the nodes (maybe I'd even just have a variable that stores the amount of nodes in the buffer)
I don't know if I'll need it :b
and maybe I'll replace it because of performance issues

This is of course not tested :)

unsigned int CLinkedList::size() const
{
    NodeType* node = cursor;
    unsigned int _size = 0;

    do
    {
        size++;
        node = node->next
    } while(node != cursor);

    return size;
}
// could be implemented in many different ways
NodeType* CLinkedList :: get(NodeType* _startNode, unsigned int _position) const
{
    while(_position--)
    {
         _startNode = _startNode->next;
    }
    return _startNode;
}

// ...

// somewhere in split()
if(!isEmpty())
{
    // size = 7
    // nodes_for_a = 4
    // nodes[0] - [3] are for a -> nodes[3]'s next is nodes[0] which is cursor
    // nodes[4] - [6] are for b -> nodes[6]'s next is nodes[4]

    unsigned int size = this->size();
    if(size < 2) // only work if 2 or more nodes are available
        return;

    unsigned int nodes_for_a = size/2 + size%2;
    
    // get nodes[3] and nodes[6]
    NodeType* last_in_a = this->get(cursor, nodes_for_a - 1);
    NodeType* last_in_b = this->get(last_in_a, size - nodes_for_a);

    // nodex[6]->next = nodes[3]->next = nodes[4]
    last_in_b->next = last_in_a->next;

    // nodes[3]->next = nodes[0] = cursor
    last_in_a->next = cursor;

    // set lists cursot to first_in_b (which is last_in_b->next)
    list.cursor = last_in_b->next; // I'll just assume that's everything i have to do to tell b where the buffer is
}

[fg109]

For the first problem, then to reset it I simply initiate temp to NULL, then reinitiate to cursor correct?

Put temp = cursor; somewhere between the first and second loops.

The second problem, would I have to construct another while loop for the second node to make sure it links back to itself?

Yes, you need a third loop. Start with list.cursor and keep checking nodes until you get to the one that links to cursor. That one should be the last node and you should change it to link to list.cursor.

[keskiverto]

I see two approaches:

1. Do all the the low-level work in CLinkedList::split
2. Use the interface of CLinkedList in CLinkedList::split

Gamer2015's use of CLinkedList::size() and CLinkedList::get() is an example of the second approach.
Both "helper" functions are simple and each perform single, clear, easy to test operation.
Use of the existing interface does not merely simplify the code of split() but also prevents unnecessary code duplication.

You have not shown the current interface of CLinkedList, so we cannot know whether it offers anything useful.