Doubly Linked List split help!

[alex067]

I have to split a grocery list (nodes that takes 2 parameters, a string for the name of the item, and int for the quantity) and have every other node from the first list split into the second list.

So for example;

the first node contains:
1-2-3-4-5-6-7-8-9-NULL

then the split function would result in:

first node:
2-4-6-8-NULL

second node:
1-3-5-7-9-NULL


I am so confused as to how the node links and delinks work, like how do i have the second list head to point to the first node in the list and then have a loop which keeps linking the next node to the next and then eventually to NULL?

Basically, I am at a loss as to how to even start this

[alex067]

I have attempted to do this problem but my compiler breaks.

The first list looks like this:

M-> <- L -> <- A -> <- O -> <- E -> <- S-> <- A -> <- P -> <- Q

I need the second list to look like this:
L -> <- O -> <- S -> <- P

Which results in the first list to look like this:
M -> <- A -> <- E -> <- A -> <- Q

My compiler breaks when it reaches my while statement which traverses the list and at the same time links/delinks the nodes

void GroceryList::deal(GroceryList & secondList) //transfers every other node to a new list
{
	ItemType * current = head;
	ItemType *temp;
	ItemType *second = new ItemType;
	//intialize head for second list
	temp = current->next;
	
	secondList.head = temp;
	current->next = temp->next; //delink for first list
	temp->next->prev = current;
	temp->prev = NULL;
	second = secondList.head;
		
	current = temp->next; //start current at next node
	temp->next = current->next;
	while (temp->next->next != NULL)
	{
		temp = current->next;
		current->next = temp->next;
		temp->next->prev = current;
		second->next = temp;
		temp->prev = second;
		temp->next = NULL;
		second = current->next;
		current = temp->next;
	}
	second->next = NULL;
	current->next = NULL;
	secondList.tail = second;


	current = second = temp = NULL;

}

[Gamer2015]

Not tested.
I hope it works.
Both Nodes alternately set the next node.

void GroceryList::split(GroceryList* secondList)
{
    if(head == nullptr)
    {
        secondList == nullptr;
        return;
    }

    ItemType* temp1 = head; // i think that's the start of the list? // 1
    ItemType* temp2 = secondList->head = temp->next; // 2
    secondList->head->prev = nullptr;

// now, temp1 and temp2 alternately set the next and prev node
    while (temp1->next != nullptr || temp2->next != nullptr)
    {
        if(temp1->next != nullptr) // if the next node is not a nullpointer
        {
            temp1->next = temp1->next->next; // make the next note the second next one
            if(temp1->next != nullptr) // if that node is not a nullpointer
                temp1->next->prev = temp1; // set the prev of that node
            temp1 = temp1->next; // traverse
        }

// same comments for that part here
        if(temp2->next != nullptr)
        {
            temp2->next = temp2->next->next;
            if(temp2->next != nullptr)
                temp2->next->prev = temp1;
            temp2 = temp2->next;
        }
    }
}

[alex067]

I traced your code and it does link and delink the nodes correctly, but the compiler breaks down when it reaches the first while loop to begin the main purpose of this function.

Hmm, what is wrong??

[alex067]

this is giving me such a headache, help please!

[Gamer2015]

if there is only 1 node, secondList->head is a nullptr.
in the next line i set the prev of a nullptr.
Also, in that case temp2 is a nullptr as well, at the beginning of the while loop i use temp2->next even though temp2 is a nullptr :o

Here the corrected version, i used a little different algorithm which is in essence the same.
temp1->next is temp2 and temp2->next is temp1
(note: you need to start relinking with temp1 in this approach)

Note: untested

void GroceryList::split(GroceryList* secondList)
{
    if(head == nullptr)
    {
        secondList->head = nullptr;
        return;
    }

    ItemType* temp1 = head; // i think that's the start of the list? // 1
    ItemType* temp2 = secondList->head = temp->next; // 2

    if(secondList->head != nullptr)
        secondList->head->prev = nullptr;

    while (temp1 != nullptr || temp2 != nullptr)
    {
        if(temp2 != nullptr)
        {
            temp1->next = temp2->next;
            if(temp1->next != nullptr) 
                temp1->next->prev = temp1;
            temp1 = temp1->next;
        }
        if(temp1 != nullptr)
        {
            temp2->next = temp1->next;
            if(temp2->next != nullptr) 
                temp2->next->prev = temp2;
            temp2 = temp2->next;
        }
    }
}

edit: preventing code-duplication
hope that's not too confusing :o

Note: untested

void GroceryList::split(GroceryList* secondList)
{
    if(head == nullptr)
    {
        secondList->head = nullptr;
        return;
    }

    ItemType* temp1 = head; // i think that's the start of the list? // 1
    ItemType* temp2 = secondList->head = temp->next; // 2

    if(secondList->head != nullptr)
        secondList->head->prev = nullptr;

    ItemType** t1 = &temp1;
    ItemType** t2 = &temp2;

    while (*t1 != nullptr || *t2 != nullptr)
    {
        if(*t2 != nullptr)
        {
            *t1->next = *t2->next;
            if(*t1->next != nullptr) 
                *t1->next->prev = *t1;
            *t1= *t1->next;
        }
        std::swap(t1, t2);
    }
}

[alex067]

"if there is only 1 node, secondList->head is a nullptr.
in the next line i set the prev of a nullptr.
Also, in that case temp2 is a nullptr as well, at the beginning of the while loop i use temp2->next even though temp2 is a nullptr :o"

Are you saying that, because you initialized secondList.head-> prev to NULL, it made the while condition constantly false so it never iterates?

I changed the code once again, reversing the conditions like you did since temp 2 is always in front of temp 1.

But again the compiler breaks!

[alex067]

void GroceryList::deal(GroceryList & secondList) //transfers every other node to a new list
{

	if (head == NULL)// if list is empty
	{
		secondList.head = NULL;
		return;
	}

	ItemType *temp1 = head; //travserse for the first list
	ItemType *temp2 = secondList.head = temp1->next; //traverse for second list, start at next node from head
	
	if (secondList.head != NULL)
	{
		secondList.head->prev = NULL;
	}

	while (temp1 != NULL || temp2 != NULL) //begin traversing, have temp2 node ahead of temp1 node 
	{
		if (temp2 != NULL) //condition for first node 
		//reversed conditions because temp2 pointer is always ahead of temp1
		{
			temp1->next = temp2->next; //link to next
			if (temp1->next != NULL) //as long as the next node after temp2 node is not null
			{
				temp1->next->prev = temp1; //link from next to present node
			}
			goNext(temp1); //traverse 
		}
		if (temp1 != NULL) //condition for first node
		{
			temp2->next = temp1->next; //link to next
			if (temp2->next != NULL) //as long as the next node after temp2 node is not null
			{
				temp2->next->prev = temp2; //link from next to present node
			}
			goNext(temp2); //traverse 
		}

	}
	temp1 = temp2 = NULL;



}

int main()
{
	
	
	//showing the split function
	//populating new list
	GroceryList Betty;
	GroceryList Nicholas; //new list to transfer data
	Betty.addToFront("Milk", 1);
	Betty.addToBack("Lime", 2);
	Betty.addToBack("Apples", 6);
	Betty.add("Oatmeal", 3, 4);
	Betty.addToBack("Eggs", 12);
	Betty.addToBack("Salsa", 1);
	Betty.addToBack("Avocado", 5);
	Betty.addToBack("Pepper", 1);
	Betty.addToBack("Quinoa", 1);
	cout << "Printing Betty's list:" << endl;
	Betty.printForward();
	cout << "Printing Nichola's list:" << endl;
	Nicholas.printForward();
	//call split function
	cout << "Caling deal..." << endl;
	Betty.deal(Nicholas);
	Nicholas.printForward();



	
	
	
	system("PAUSE");
	return 0;
}

[alex067]

need help please! can't seem to find the problem

[Gamer2015]

Are you saying that, because you initialized secondList.head-> prev to NULL, it made the while condition constantly false so it never iterates?

No, in case there is no second element in the list, secondList.head is a nullptr.
then i set secondList.head->prev to null.
Remember, secondList.head is a nullptr so it is not in my memory space.
Since i try to reassign data that's outside of my memory space the program crashes

But again the compiler breaks!

What do you mean by that?
Does the compiler give you errors or does the program just stop executing suddenly?

need help please! can't seem to find the problem

This will not help you to get an answer faster

[alex067]

What is the difference then of assigning it to NULL instead of nullptr?


The compiler breaks when it reaches

if (temp1 != NULL) //condition for first node
		{
			temp2->next = temp1->next; //link to next
			if (temp2->next != NULL) //as long as the next node after temp2 node is not null
			{
				temp2->next->prev = temp2; //link from next to present node
			}
			goNext(temp2); //traverse 
		}

a window pops up saying, unhandled exception at 0x00188EDO in

[Gamer2015]

What is the difference then of assigning it to NULL instead of nullptr?

basically nothing.
nullptr is just a c++11 feature which is to be prefered over NULL
The thing you said just differs from what i said.

The compiler breaks when it reaches

The compiler doesn't break, the compiler compiles.
The compiler may give you warnings or error when compiling but when running the Programm the compiler has nothing to do with it.

a window pops up saying, unhandled exception at 0x00188EDO in

in?
Now, this could be everything so... yeah... it sucks.
Try debugging and tell me where it crashes

[alex067]

Ok then the compiler compiles but during runtime the program crashes.

The exact error it states is: Unhandled exception at 0x00D68ED0 in GroceryBuddy.exe: Access violation writing location

"'GroceryBuddy.exe' (Win32): Loaded 'C:\Windows\SysWOW64\msvcr120d.dll'. Cannot find or open the PDB file.
First-chance exception at 0x00D68ED0 in GroceryBuddy.exe: 0xC0000005: Access violation writing location 0x00000028.
Unhandled exception at 0x00D68ED0 in GroceryBuddy.exe: 0xC0000005: Access violation writing location 0x00000028.

The thread 0x12c0 has exited with code -1073741510 (0xc000013a).
The program '[6872] GroceryBuddy.exe' has exited with code -1073741510 (0xc000013a).
"

The compiler specifically points to this line:

temp2->next = temp1->next; //link to next 

This line is found right after the second if statement, if(temp1 != NULL


I know that it could not be everything, as my program contains a lot of functions with different operations and they all work fine, up until I call upon this function of splitting the list :/

[Gamer2015]

oh, that might happen if temp2->next is a nullptr :o

try changing the while statement from or to and

[alex067]

Ah that fixed everything, thank you for your help gamer2015! appreciate it big time man

[Gamer2015]

sure, no problem! :)
Could you please try the pointer-to-pointer version of this and tell me if it works?

void GroceryList::split(GroceryList* secondList)
{
    if(head == nullptr)
    {
        secondList->head = nullptr;
        return;
    }

    ItemType* temp1 = head; // i think that's the start of the list? // 1
    ItemType* temp2 = secondList->head = temp->next; // 2

    if(secondList->head != nullptr)
        secondList->head->prev = nullptr;

    ItemType** t1 = &temp1;
    ItemType** t2 = &temp2;

    while (*t1 != nullptr && *t2 != nullptr)
    {
        *t1->next = *t2->next;
        if(*t1->next != nullptr) 
            *t1->next->prev = *t1;

        *t1= *t1->next;

        std::swap(t1, t2);
    }
}