Hello,

I created a linked list and implemented a deep copy function. However, the copied list skips the head node in the source list for some reason.

So assume source list contains the following data in their respective nodes:
1 3 6 7 10 312

The copied linked list will be:
3 6 7 10 312

Please tell me what's wrong with it. This is the definition of the deep copy function: OrderedSListT(const OrderedSListT<T>& Source). Its towards the end.

I appreciate any help.


Below is my code:

#ifndef ORDEREDSLISTT_H_
#define ORDEREDSLISTT_H_
#include <new>

template <typename T> class OrderedSListT {
public:
   // Give the test harness privileged access:
   friend class SListTAuditor;
   
   // Create an empty list object.
   OrderedSListT() {
	   mHead = NULL;
	   mTail = NULL;
   }
	   
   // Add the value Data to the list, placing it in the correct location
   // relative to the other values in the list (if any).  Return true if the
   // insertion succeeds (which it will).
   bool Insert(const T& Data) {

		/*
		 * Insertion if list is empty
		 */
		if (mHead == NULL && mTail == NULL) {
			SNode* node = new SNode(Data, NULL);
			mHead = node;
			mTail = node;

			return true;
		}

		else {
			/*
			 * Insertion if new node is before head
			 */
			if (mHead->mData > Data) {
				SNode* node = new SNode(Data, mHead);
				mHead = node;

				return true;
			}

			SNode *temp;
			temp = mHead;

			while (temp->mNext != NULL) {
				/*
				 * Move temporary pointer if data is larger than current pointer
				 * data
				 */
				if (temp->mNext->mData < Data) {
					temp = temp->mNext;
				}

				/*
				 * Insert node in the middle of the list
				 */
				else if (temp->mNext->mData >= Data) {
					SNode* node = new SNode(Data, temp->mNext);
					temp->mNext = node;

					return true;
				}
			}

			/*
			 * Insert node at the tail of the list
			 */
			if (temp->mNext == NULL) {
				SNode* node = new SNode(Data, NULL);
				temp->mNext = node;
				mTail = node;

				return true;
			}
		}

		return false;
   }
   
   // Delete all values from the list, and restore it to its empty state.
   void Clear() {

	   while (mHead != NULL && mTail != NULL) {
		   SNode *temp = mHead;
		   mHead = mHead->mNext;
		   delete temp;
		   temp = NULL;
	   }

	   if (mHead == NULL) {
		   mTail = NULL;
	   }
   }
	   
   // Provide deep copy support:
   OrderedSListT(const OrderedSListT<T>& Source) {

	   if (Source.mHead != NULL) {

		   // Source Pointer
		   SNode *p1 = Source.mHead;
		   SNode *p2;

		   SNode *headNode = new SNode(p1->mData, NULL);
		   p1 = p1->mNext;
		   bool firstCount = false;

		   while (p1 != NULL) {
			   SNode *node = new SNode(p1->mData, NULL);

			   if (!firstCount) {
				   headNode->mNext = node;
				   firstCount = true;
				   p2 = node;
			   }

			   else {
				   p2->mNext = node;
				   p2 = p2->mNext;
			   }

			   p1 = p1->mNext;
		   }

		   p1 = NULL;
		   p2 = NULL;
	   }
   }

   // Destroy all the list nodes.
   ~OrderedSListT() {
	   this->Clear();
   }
private:
   class SNode {
   public:
      T      mData;
      // Points to next node in list, if any; otherwise NULL.
      SNode* mNext;
	   
      // Initialize the node in the obvious way.
      SNode(const T& Data, SNode* Next = NULL) {
	      mData = Data;
	      mNext = Next;
      }
   };
	
   // Point to first and last nodes in non-empty list; otherwise NULL.
   SNode* mHead;
   SNode* mTail;
};

// Implementations of list member functions should go here:


// End of member implementations
#endif

How about something like this:

//create a new list by deep copying data in source list to new list 
//keeping the source list intact
OrderedSListT newList;  //declare the new list
SNode * temp = Source.mHead; //start at the first node in the source list
while there's a node to copy from Source
  insert data in temp to newList //using the insert function you already wrote
  go to next list in Source

That way you maximize reuse of code.

Your code is organized a little strange so I'm having a hard time wading through this.

It looks like the problem is that you are using local variables incorrectly and not storing anything to the appropriate member variables. I don't see any instance where you access this->mHead or this->mTail ...

Edited 6 Years Ago by Fbody: n/a

I do not want to reuse my insert method, so therefore I do not have to create a new list, OrderedSListT newlist;

The reason being is I want it to copy any linked list, and not sort it the way my insert function does.


Why would I have to use this->mHead if I have put temporary pointers on both the source and the target list?

Are you saying you want to copy any list into an OrderedSListT without ordering the new data in the OrderedSList used as the target? Doesn't that defeat the purpose of copying the random list into an OrderedSList?

To copy one list, say aList, into another, say bList, you have to know what you want to do. Do you want to replace whatever is in bList with what's in aList or do you want to merge aList and bList together in some fashion (there are many ways to merge lists)? Then you have to decide whether you do a shallow copy or a deep copy of the list that's being copied. You've apparently chosen the deep copy part but it's not clear to me what you want to do with the other part.

Sorry for the confusion,

I want to replace whatever is in bList with what's in aList.

As pointed out by Fbody, your copy-constructor has not a single statement that sets the mHead and mTail pointer to anything. The fact that the copied list outputs the list without the head node, is pure luck, it should just output random shit or simply crash on a segmentation fault.

So, your deep-copy is perfectly fine, it works... except that the list is copied into the head pointer "headNode" which is thrown away after the constructors body has finished executing (which is a memory leak, btw). Now, all you need to do is replace all references to "headNode" for "this->mHead". Then, you will have to add a bit of code to keep track of mTail too.

I am creating a headNode because copying the first node is an exception. After creating the headNode, I run a loop to copy the rest (SNode node).

I only use headNode twice - once to create the header node of the new list, and another to connect it to the second node that is created.


So I dont understand why I am supposed to use this->mHead, and where to use it. I am only using it to create a node and link it to the next one (which this->mHead does not do).

You have to use this->mHead because without it the node that is created as your list head gets destroyed at the end of the constructor and you lose your list head. What you should have is something like:

SNode *p1 = Source.mHead;
this->mHead = new SNode(p1->mData, NULL);
//instead of SNode *headNode = new SNode(p1->mData, NULL);

//... other required steps...

this->mHead->mNext = node;
//instead of headNode->mNext = node;

Edited 6 Years Ago by Fbody: n/a

Comments
Solved my problem - great help

Works!!! Wow....


Totally missed that the header node will get destroyed..


Thank you very much.

So the following shouldn't segfault/memoryleak?

OrderedSListT(const OrderedSListT<T>& Source) {

	  if (Source.mHead != NULL) {

		   // Source Pointer
		   SNode *p1 = Source.mHead;
		   SNode *p2;

		   this->mHead = new SNode(p1->mData, NULL);
		   p1 = p1->mNext;
		   bool firstCount = true;

		   while (p1 != NULL) {
			   SNode *node = new SNode(p1->mData, NULL);

			   if (firstCount) {
				   this->mHead->mNext = node;
				   firstCount = false;
				   p2 = node;
			   }

			   else {
				   p2->mNext = node;
				   p2 = p2->mNext;
			   }

			   p1 = p1->mNext;
		   }

		   p1 = NULL;
		   p2 = NULL;
	   }
   }

It looks like it will be okay. If there are memory problems, it doesn't look like they should be caused by anything here. Just make sure your destructor(s) clean things up properly.

This article has been dead for over six months. Start a new discussion instead.