🔒 Locked

Copy Constructor in a Doubly Circular Linked List

Started by toogreat4u Feb 1, 2010 at 10:32 AM 1 replies 5.3k views

Original Post

Feb 1, 2010 at 10:32 AM

I am having trouble figuring out how to implement a copy constructor for a doubly circular linked list. I am writing this implementation as a personal exercise from a book I am reading. I am pretty confused on what I should be doing so I'll show what I am and doing and let any who wishes comment on it.


DoublyList::DoublyList(const DoublyList& aList)
{
	size = aList.size;

	if(aList.size == 0) // empyt list
	{
		// dummy points to itself
		dummyHead = new DoublyListNode;
		dummyHead->next = dummyHead;
		dummyHead->precede = dummyHead;

		// make sure the listHead points to dummy
		listHead = new DoublyListNode;
		listHead->next = dummyHead;
		listHead->precede = NULL; // not needed just null it
	}
	else
	{
		dummyHead = new DoublyListNode;
		
		listHead = new DoublyListNode;
		listHead->next = dummyHead;
		listHead->precede = NULL;

		// start getting a little lost here

		// grab head node
		DoublyListNode *newPtr = dummyHead;
		dummyHead->next = newPtr; // initially dummyHead->next should point to itself
		dummyHead->precede = newPtr; // initially dummyHead->precede should point to itself

		// travers through copy list from front to back
		for(DoublyListNode *origPtr = aList.dummyHead->next; origPtr != aList.dummyHead; origPtr = origPtr->next)
		{
			// allocate new memory for node copying
			newPtr->next = new DoublyListNode;
			newPtr->precede = newPtr; // precede points to previous node, which will be newPtr

			// having most trouble figuring out what to do with dummyHead if anything
			// 
			// what should happen to dummyHead at this point?
			// anything or is this ok?
			//

			newPtr = newPtr->next; // make newPtr the current ptr
			newPtr->item = origPtr->item; // assign the value of copy list into newPtr value
		}

		// I believe after the loop is done this is correct but unsure
		newPtr->next = dummyHead;
		
	}
}

Struct for the DoublyListNode are:


struct DoublyListNode
	{
		ListItemType item;
		DoublyListNode *next;
		DoublyListNode *precede;
	};

	DoublyListNode *listHead;
	DoublyListNode *dummyHead;
	int size;

Thanks for any help.

iMalc

Feb 1, 2010 at 11:58 AM

Quote:
Original post by toogreat4u
I am having trouble figuring out how to implement a copy constructor for a doubly circular linked list. I am writing this implementation as a personal exercise from a book I am reading. I am pretty confused on what I should be doing so I'll show what I am and doing and let any who wishes comment on it.

*** Source Snippet Removed ***

Struct for the DoublyListNode are:
*** Source Snippet Removed ***

Thanks for any help.

Don't overcomplicate things.
Both the 'if' and the 'else' brance contain the following code:

		dummyHead = new DoublyListNode;		dummyHead->next = dummyHead;		listHead = new DoublyListNode;		listHead->next = dummyHead;		listHead->precede = NULL;

So, how about putting that before the if-statement?

Now I have to ask though, why does it do two allocations regardless of whether there are any items in the list at all?

toogreat4u

Feb 1, 2010 at 5:00 PM

Quote:

Now I have to ask though, why does it do two allocations regardless of whether there are any items in the list at all?

The book uses a visual description showing listHead --> to dummyHead, I am not sure if this is just a visual representation of the listHead or an actual pointer that does nothing but point to dummy node. It looked silly to me but I thought maybe there is a reason for it, but I rarely/never use that pointer.

I did figure out what you were trying to tell me though. I was over complicating the insertion, I simply called a correct insert function just using the values from the aList. Here is my constructor followed by the insertion function.

DoublyList::DoublyList(const DoublyList& aList){	// dummy points to itself	dummyHead = new DoublyListNode;	dummyHead->next = dummyHead;	dummyHead->precede = dummyHead;	// make sure the listHead points to dummy	listHead = new DoublyListNode;	listHead->next = dummyHead;	listHead->precede = NULL; // not needed just null it	for(DoublyListNode *origPtr = aList.dummyHead->next; origPtr != aList.dummyHead; origPtr = origPtr->next)	{		insert(origPtr->item);	}}void DoublyList::insert(ListItemType newItem){	// find insertion point	DoublyListNode *cur = dummyHead->next;	// scan until you find the item that is bigger than newItem	while(cur != dummyHead && newItem > cur->item)	{		cur = cur->next;	}	// insert into correct position	DoublyListNode *newPtr = new DoublyListNode;	newPtr->item = newItem;	newPtr->next = cur;	newPtr->precede = cur->precede;	cur->precede = newPtr;	newPtr->precede->next = newPtr;		size++;}

Thanks for your comments iMalc, it helped me simplify what I was trying to do.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.