Copy Constructor Help - for a simple linked list

Need help with copying an entire linked list into a new one...

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 9910 Views - Last Post: 07 September 2008 - 09:15 AM Rate Topic: -----

#16 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5833
  • View blog
  • Posts: 12,688
  • Joined: 16-October 07

Re: Copy Constructor Help - for a simple linked list

Posted 06 September 2008 - 12:58 PM

First, curr != NULL should be meaningless. If the head isn't null, nothing is; it's doubly linked, after all.

While loops are usually easier for traversing nodes. Here's the while of your outer loop.
Node * curr = Head;
while (curr->Next != Head) {
	// inner loop
	curr = curr->Next;
}



The problem: you're always going to miss the last one. You should loop until curr==Head, but then you'll never actually enter the loop. Think of it as a challenge.
Was This Post Helpful? 0
  • +
  • -

#17 stritone  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 37
  • Joined: 07-August 08

Re: Copy Constructor Help - for a simple linked list

Posted 07 September 2008 - 12:38 AM

Hi Baavgai,
Well, it's 12:30am and I think I managed to make the sort functions work.
I attempted to code a simple reverse list function just to try out and
wanted to double check both of these with you to see if I was on the right
track. I'm hoping this implementation is near completion. I've learned a ton from attempting to put this together. I drew some pictures of how the
loops in these functions should be operating and this was the best I could
come up with.

Here's the new sort_ascending function:

void LL::SortList_Ascend(){
  Node * curr, * save;
  curr = save = Head;
  if(Head == NULL){
	cout << "List is empty\n";
	return;
  } else {
	while(curr->Next != Head){
	  save = curr->Next;
	  while(save != Head){
		if(strcmp(curr->Item->Name, save->Item->Name) > 0){
		  Swap(save, curr);
		}
		save = save->Next;
	  }
	  curr = curr->Next;
	}
  }
}



Here's the reverse list function:

void LL::ReverseList(){
  Node * curr, * save;
  curr = save = Head;
  if(Head == NULL){
	cout << "The list is empty.\n";
	return;
  } else {
	while(curr->Next != Head){
	  save = curr->Next;
	  while(save != Head){
		Swap(save, curr);
		save = save->Next;
	  }
	  curr = curr->Next;
	}
  }
}


Was This Post Helpful? 0
  • +
  • -

#18 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5833
  • View blog
  • Posts: 12,688
  • Joined: 16-October 07

Re: Copy Constructor Help - for a simple linked list

Posted 07 September 2008 - 02:19 AM

You used the while, but you didn't fix the problem! You're still not processing the last node. Until you do, nothing will work right.

If it wasn't clear, here's what's going on:
Assume, circular list of nodes A,B,C:

A -> B -> C -> Head

Head = A
curr = Head ( A )

begin loop
(curr->Next != Head) : B!=A : true
process A
curr = B

(curr->Next != Head) : C!=A : true
process B
curr = C

(curr->Next != Head) : A!=A : false
exit loop



C is never processed! Fix that.
Was This Post Helpful? 0
  • +
  • -

#19 stritone  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 37
  • Joined: 07-August 08

Re: Copy Constructor Help - for a simple linked list

Posted 07 September 2008 - 09:15 AM

Hi Baavgai,
I've been musing about this sort function for the last 2 hours and I can't seem to figure it out. If Head or Head->Next can't be used as a stopping
point then I'm at a loss of ideas for how the loops will be able to finish up
whilst still being able to process all the data.

Looking at your logic diagram has helped though. Let me walk through
it again.

Assume, circular list of nodes A,B,C:

A -> B -> C -> Head

Head = A
curr = Head ( A )

begin loop
(curr->Next != Head) : B!=A : true
process A
curr = B

(curr->Next != Head) : C!=A : true
process B
curr = C

(curr->Next != Head) : A!=A : false
In this case curr->Next DOES EQUAL Head and A obviously equals A.
This is a serious flaw since C won't ever be processed.
So, since there needs to be a stopping point somewhere centered around
Head, how is this function going to know when it has processed all the
list items and exit?

It would seem that once the traversal does come to this
point in the sorting process, it needs to check against something centered
around Head, and, if the tests fail, it breaks out of the loop and double
checks the current and save situation for one final check and swap?

Ugh, I'm just not seeing how this can be taken care of using loop
conditions.

I tried adding a couple if statements to allow for curr->Next and
save->Next to equal Head so that the last item could be dealt with but
I'm guessing this is fallacious. I apologize for the redundancy.

void LL::SortList_Ascend(){
  Node * curr, * save;
  curr = save = Head;
  if(Head == NULL){
	cout << "List is empty\n";
	return;
  } else {
	while(curr->Next != Head){
	  save = curr->Next;
	  while(save != Head){
		if(strcmp(curr->Item->Name, save->Item->Name) > 0){
		  Swap(save, curr);
		}
		save = save->Next;
	  }
	  curr = curr->Next;
	}
	//at this point the list should have traversed to the end node
	if((curr->Next == Head) && (save->Next == Head)){
	  if(strcmp(curr->Item->Name, save->Item->Name) > 0){
		Swap(save, curr);
	  }
	}
  }
}


Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2