[stritone]

Hello,
I was wondering if someone could help me with a copy
constructor function for this linked list program. It's pretty
generic and just processes a name and age value.

Also, how would you invoke the copy constructor once it's
defined?

Any help with this would be great. Thanks for your time.

Here's the class definition:

class LL {
  protected:
	struct Node {
	  char * Name;
	  int Age;
	  Node * Next;
	  Node * Prev;
	};
	int Length;
	Node * Head;
	Node * Tail;

  public:
	LL();
	LL(const LL & obj);
	~LL();
	void Insert(char * Name, int Age);
	void InsertNode(Node * newNode);
	void Delete(char * Name, int Age);
	void DeleteNode(Node * delNode);
	void DisplayNodes() const;
	void DestroyList();
	void SortList_Ascend();
	void SortList_Descend();
	void ReverseList();
	void Search(char *Name, int Age);
	void SearchNode(Node * srchNode);
};

and here's my attempt with the copy constructor...
I pretty sure this is incorrect.

LL::LL()
{
  Length = 0;
  Head = NULL;
  Tail = NULL;
}


LL::LL(const LL & obj)
{
  if ((Length = obj.Length) == 0)
  {
	Head = 0;
	return;
  }
  Node * o = obj.Head;
  Head = new Node;
  Node * n = Head;
  Node * n_prev;

  n->Name = new char[strlen(o->Name) + 1];
  strcpy(n->Name, o->Name);
  n->Age = o->Age;
  while((o = o->Next) != 0)
  {
	n_prev = n;
	n = new Node;
	n->Name = new char[strlen(o->Name) + 1];
	strcpy(n->Name, o->Name);
	n->Age = o->Age;
	n_prev->Next = n;
  }
}

[baavgai]

Note, I don't really trust the Length attribute. I'd rather just have it as a method and count the list.

If your Insert method is working properly, this should be fine. Think of it as just starting with an empty list and adding nodes in sequence, which is just what we're doing.

// this bit looks fine
LL::LL() {
	Length = 0;
	Head = NULL;
	Tail = NULL;
}


LL::LL(const LL & obj) {
	// start with blank, just like in the empty constructor
	Length = 0;
	Head = NULL;
	Tail = NULL;
	
	// Now you should just be able to use 
	// your list's methods
	Node *p = obj.Head;
	while(p!=NULL)  {
		Insert(p->Name, p->Age);
		p = p->Next;
	}
}

The copy constructor is easy, it's the Insert and InsertNode that's the challenge. Also, since you're using C++, you might consider the string class if you're allowed.

Hope this helps.

This post has been edited by baavgai: 03 September 2008 - 12:48 PM

[stritone]

Baavgai,
Thanks so much for your response! Your explanation made perfect sense. I tested it out and worked great.

I managed to come up with this other one while waiting to see if anyone would reply from the first post. I contrasted the two of them below:

Here's what I tried on my second attempt. It was kind of like fusing the Insert() function and the copy constructor into one. The new one you described is much more slick and makes use of the already defined Insert() function.

Thanks again!

Contrasted this...

LL::LL(const LL & obj)
{
  Node * o = obj.Head;

  if (obj.Head == NULL)
  {
	cout << "List is empty...\n";
	Head = NULL;
  }
  else
  {
	Head = new Node;
	assert(Head != NULL);
	Head->Name = new char[strlen(o->Name) + 1];
	strcpy(Head->Name, o->Name);
	Head->Age = o->Age;

	Node * newPtr = Head;
	for (Node * origPtr = obj.Head->Next;
				origPtr != NULL;
				origPtr = origPtr->Next )
	{
	  newPtr->Next = new Node;
	  assert(newPtr->Next != NULL);
	  newPtr = newPtr->Next;
	  newPtr->Name = new char[strlen(origPtr->Name) + 1];
	  strcpy(newPtr->Name, origPtr->Name);
	  newPtr->Age = origPtr->Age;
	}
	newPtr->Next = NULL;
  }

with this...

LL::LL(const LL & obj)
{
  Length = 0;
  Head = NULL;
  Tail = NULL;

  Node * p = obj.Head;
  while(p != NULL){
	Insert(p->Name, p->Age);
	p = p->Next;
  }
}

The Insert() and InsertNode() functions looked like this...

void LL::Insert(char * Name, int Age)
{
  Node * newNode = new Node;
  newNode->Name = new char[strlen(Name) + 1];
  strcpy(newNode->Name, Name);
  newNode->Age = Age;
  newNode->Next = NULL;
  newNode->Prev = NULL;
  InsertNode(newNode);
}

void LL::InsertNode(Node * newNode)
{
  if (Head == NULL)
  {
	cout << "inserting at front...\n";
	Head = newNode;
	Tail = newNode;
	Head->Next = NULL;
	Head->Prev = NULL;
  }
  else
  {
	Node * curr;
	Node * prev;
	curr = Head;
	prev = NULL;
	while (curr != NULL)
	{
	  prev = curr;
	  curr = curr->Next;
	}
	newNode->Next = curr;
	prev->Next = newNode;
	newNode->Prev = prev;
	Tail = newNode;
  }
}

[baavgai]

Your InsertNode is traveling to the end to add something new. Why?

Your LL is holding a Head and a Tail. Again, why. You only need the head. But, if you want both, take advantage of it.

Insert at the beginning, no tail needed.

void LL::InsertNode(Node * newNode) {
	newNode->Prev = NULL;
	newNode->Next = NULL;
	if (Head == NULL) {
		Head = newNode;
		Tail = newNode;
	} else {
		newNode->Next = Head;
		Head->Prev = newNode;
		Head = newNode;
	}
}

Adding to the end, because we have a Tail.

void LL::InsertNode(Node * newNode) {
	newNode->Prev = NULL;
	newNode->Next = NULL;
	if (Head == NULL) {
		Head = newNode;
		Tail = newNode;
	} else {
		newNode->Prev = Tail;
		Tail->Next = newNode;
		Tail = newNode;
	}
}

( Um, I didn't test this code. It's perfect, in theory only. )

Most Linked List implementations only need a Next pointer in the node to do their thing. Your class need only hold the top. For a doubly linked list, like this one, there's usually a reason. A search requirement, most likely.

Hope this helps.

[stritone]

Hi Baavgai,
Thanks again for looking at my code. I've been trying to compile a set of
data structure programs and have been more or less reusing the LL class
for the circular, doubly linked, stack, and queue structures. I added
functions for inserting at the front and at the end using your suggestions.

I've been getting a seg fault on my Delete function and would like to clean
it up a bit and make it as slick as the insertion functions. This is pretty
pretty ugly but what could I do to clean this function up? The seg fault is
occurring at the end.

Thanks again for your help with this.

void LL::DeleteNode(Node * delNode)
{
 if(Head)
 {
  Node * curr;

  if((strcmp(Head->Name, delNode->Name) == 0) && 
				(Head->Age == delNode->Age))
  {
	cout << "info is in the Head node...deleting...\n";
	curr = Head;
	Head = Head->Next;
	if(Head->Next == NULL)
	{
	  Tail = Head;
	}
	delete curr;
  }
  else
  {
	cout << "deleting from node other than Head...\n";
	Node * prev = NULL;
	curr = Head;
	while(curr != NULL)
	{
	  if((strcmp(curr->Name, delNode->Name) == 0) &&
		 (curr->Age == delNode->Age))
	  {
		cout << "found the info...\n";
		break;
	  }
	  prev = curr;
	  curr = curr->Next;
	}

	cout << "deleting...\n";
	prev->Next = curr->Next;
	curr->Next->Prev = prev;
	if(curr->Next == NULL)
	{
	  Tail = prev;
	}
	delete curr;
	curr = NULL;
  }
 }
}

[baavgai]

At this point:

prev->Next = curr->Next;

You are assuming that curr is not null. That's not a valid assumption, if you didn't find the node, it could be null.

If you did find it, you have a prev and a next in the node itself, you really shouldn't need any other pointers to delete it. You have a search function? void Search(char *Name, int Age); What does it do, exactly? Make a useful one, like Node* Search(char *Name, int Age);.

Also, you're doing a lot of mucking about data in your nodes. You might do well have have the data be class:

class ItemType {
public:
	char * Name;
	int Age;

	ItemType(char * Name, int Age) {
		this->Name = new char[strlen(Name) + 1];
		strcpy(this->Name, Name);
		this->Age = Age;
	}
	~ItemType() { delete this->Name; }
	
	bool operator==(const ItemType& other) const {
		return ((strcmp(this->Name, other.Name) == 0) && (this->Age == other->Age));
	}
}

//...
class LL {
protected:
	struct Node {
		ItemType *Item
		Node *Next;
	};
	Node *head;
//...

For linked lists, or similar constructs, I prefer to never expose the node type. The rest of the program shouldn't really know or care about it.

[stritone]

Hi Baavgai,
Thanks for your further suggestions and I totally revamped the whole
linked list program/class. I'm still having trouble with the Delete function
though. I'm trying to figure out how to clean up the pointers when the
deletion is made and I keep getting seg faults. Can you suggest anything?

I'm going to need to revamp all the other programs as well. Is this class
definition type the best way to implement a linked list or binary search
tree? Does the ItemType class need to have more operator overloading?

Here's my new class definition:

#include <iostream>
#include <cstring>
using namespace std;

class ItemType {
  public:
	friend class LL;

	char * Name;
	int Age;

	ItemType(char *Name, int Age){
	  this->Name = new char[strlen(Name) + 1];
	  strcpy(this->Name, Name);
	  this->Age = Age;
	}
	~ItemType(){ delete this->Name; }

	bool operator==(const ItemType & obj) const{
	  return ((strcmp(this->Name, obj.Name)==0) &&
			  (this->Age == obj.Age));
	}
};

class LL {
  protected:
	struct Node {
	  ItemType * Item;
	  Node * Next;
	  Node * Prev;
	};
	Node * Head;
	Node * Tail;

  public:
	LL();
	LL(const LL & obj);
	~LL();
	void InsertAtFront(char * Name, int Age);
	void InsertNodeAtFront(Node * newNode);
	void InsertAtEnd(char * Name, int Age);
	void InsertNodeAtEnd(Node * newNode);
	void Delete(char * Name, int Age);
	void DeleteNode(Node * delNode);
	void DisplayNodes() const;
	void DestroyList();
	void SortList_Ascend();
	void SortList_Descend();
	void ReverseList();
	Node * Search(char *Name, int Age);
	Node * SearchNode(Node * srchNode);
};

Here's my SearchNode function...

LL::Node * LL::SearchNode(Node * srchNode)
{
  Node * curr;
  if(Head == NULL)
  {
	cout << "The list is empty\n";
  }
  else
  {
	cout << "head is not NULL...searching...\n";
	curr = Head;
	while(curr != NULL)
	{
	  if(curr = srchNode)
	  {
		cout << "Found the info in the list...\n";
		break;
	  }
	  curr = curr->Next;
	}

	if(curr != NULL)
	{
	  return curr;
	}
	else
	{
	  return NULL;
	}
  }
}

Here's the Delete function...

void LL::DeleteNode(Node * delNode)
{
 if(Head)
 {
  Node * curr = SearchNode(delNode);

  if(curr == NULL)
  {
	cout << "Didn't find the info to delete from the list.\n";
  }
  else
  {
	if (curr->Next = NULL)
	{
	  cout << "node to delete was at the end of the list.\n";
	  curr->Prev->Next = NULL;
	  Tail = curr->Prev;

	}
	else
	{
	  cout << "node to delete was in the middle of the list somewhere.\n";
	  curr->Prev->Next = curr->Next;
	  curr->Next->Prev = curr->Prev;

	}
	delete curr;
	curr = NULL;
  }
 }
}

[baavgai]

This is wrong:

if(curr = srchNode)

For a comparison, you'd want this:

if(curr == srchNode)

However, that's still wrong, because you probably want to be comparing the Item values.


Delete looks ok, if a little busy. Make sure you delete the payload. Here's a shorter version.

void LL::DeleteNode(Node * delNode) {
	Node * curr = SearchNode(delNode);
	
	if(curr == NULL) { return; }
	
	curr->Prev->Next = curr->Next;
	curr->Next->Prev = curr->Prev;
	delete curr->Item;
	delete curr;
}

[stritone]

Hi Baavgai,
Thanks again for all your help with this. I've been working on this project
all day for the most part and it seems close to being completed. I was
able to get the Delete function working with the help of the Search
function and it is now much shorter. It still looks a bit busy though.

I'm now having some interesting errors that I can't quite pinpoint. To add
some completenes to the program I tried to add file I/O capability.
Now, when the program is run and I read in data to the list from a file
and try to use one of the sort ascending or descending functions, the
program seg faults.

If I don't read in anything from the file to initialize the list and just input
the list node information manually, the sort functions work fine. Client
information can be added and then sorted without problems (so it seems).

There may be something wrong with my SaveList or OpenFile functions.

Is there any apparent code problems with the sort functions?

Thanks again for all your help. I included the entire program files if it helps any.

void LL::SaveList(char * defFile)
{
  ofstream write;
  Node * curr = Head;
  write.open(defFile);
  if(!write)
  {
	cerr << "Error opening file...\n";
	return;
  }

  while (curr != NULL)
  {
	write << curr->Item->Name << "|" << curr->Item->Age << endl;
	curr = curr->Next;
  }
  write.close();
}

void LL::OpenFile(char * File)
{

  ifstream read;
  read.open(File);
  if(!read)
  {
	cerr << "Couldn't find the file.\n";
	return;
  }

  Node * temp;
  char * Name;
  int Age;

  while(read.peek() != EOF)
  {
	temp = new Node;
	Name = new char[35];
	read.get(Name, 35, '|');
	read.get();
	read >> Age;

	temp->Item = new ItemType(Name, Age);
	InsertNodeAtEnd(temp);
	read.ignore(100, '\n');
  }
  read.close();
}

Here are the sort functions that are problematic:

void LL::SortList_Ascend()
{
  Node * temp;
  Node * curr, * save;
  curr = save = Head;
  if (Head == NULL)
  {
	cout << "Linked list is empty\n";
	return;
  }
  else
  {
	for (curr = Head; (curr != NULL); curr = curr->Next)
	{
	  for (save = curr->Next; (save != NULL); save = save->Next)
	  {
		if (strcmp(curr->Item->Name, save->Item->Name) > 0)
		{
		  temp = new Node;
		  temp->Item = new ItemType(save->Item->Name, save->Item->Age);
		  strcpy(save->Item->Name, curr->Item->Name);
		  save->Item->Age = curr->Item->Age;
		  strcpy(curr->Item->Name, temp->Item->Name);
		  curr->Item->Age = temp->Item->Age;
		}
	  }
	}
	cout << "The linked list is now sorted in ascending order!\n";
  }
}

/*--------------------------------------------------------------------------*/
void LL::SortList_Descend()
{
  Node * temp;
  Node * curr, * save;
  curr = save = Head;
  if (Head == NULL)
  {
	cout << "Linked list is empty\n";
	return;
  }
  else
  {
	for (curr = Head; (curr != NULL); curr = curr->Next)
	{
	  for (save = curr->Next; (save != NULL); save = save->Next)
	  {
		if (strcmp(curr->Item->Name, save->Item->Name) < 0)
		{
		  temp = new Node;
		  temp->Item = new ItemType(save->Item->Name, save->Item->Age);
		  strcpy(save->Item->Name, curr->Item->Name);
		  save->Item->Age = curr->Item->Age;
		  strcpy(curr->Item->Name, temp->Item->Name);
		  curr->Item->Age = temp->Item->Age;
		}
	  }
	}
	cout << "The linked list is now sorted in descending order!\n";
  }
}

Attached File(s)

•  LL2_h.txt (1.23K)
  Number of downloads: 63
•  LL2_cpp.txt (6.46K)
  Number of downloads: 69
•  main_cpp.txt (2.8K)
  Number of downloads: 76
•  list.txt (129bytes)
  Number of downloads: 56

[baavgai]

You need to write a functional swap method. Once it works, call that from each of your sorts.

You should not be doing this:

strcpy(save->Item->Name, curr->Item->Name);

Because you define the name like this:

this->Name = new char[strlen(Name) + 1];

Doing what you're doing, if one name "Fred" and the other is "Alexander" you will crash when you try to stuff a nine character name into a four character hole.

There's a really, really easy way to do this. Because your node simply holds a pointer to it's payload, why don't you just swap those pointers? There is no need for new anything.

[stritone]

Hi Baavgai,
It took me awhile to figure out how to implement what you were talking
about but I think I managed to make it work. I shifted gears to look at a
circular doubly linked list implementation this afternoon and tried to modify
the doubly linked list from before to avoid rewriting.

I've been struggling with the Delete function with this as well. I'm having
trouble with the special cases: inserting at front, inserting in middle, and at the end. Can you see any immediate flaws? The code is somewhat messy
but I'm striving for really understanding the concepts and getting the
functionality down. Thanks again for everything!

I'm not sure if this was correct but here's the Swap function I tried coding:

void LL::Swap(Node * save, Node * curr)
{
  Node * temp = new Node;
  temp->Item = new ItemType(save->Item->Name, save->Item->Age);
  save->Item->Name = curr->Item->Name;
  save->Item->Age = curr->Item->Age;
  curr->Item->Name = temp->Item->Name;
  curr->Item->Age = temp->Item->Age;
}

Here's the InsertNodeAtFront function:

void LL::InsertNodeAtFront(Node * newNode)
{
  newNode->Next = NULL;
  newNode->Prev = NULL;
  if (Head == NULL)
  {
	Head = newNode;
	Head->Next = Head;
	Head->Prev = NULL;
  }
  else
  {
	newNode->Next = Head;
	Head->Prev = newNode;
	Head = newNode;
  }
}

Here's the InsertNodeAtEnd function:

void LL::InsertNodeAtEnd(Node * newNode)
{
  newNode->Next = NULL;
  newNode->Prev = NULL;

  if (Head == NULL)
  {
	cout << "Inserting first node in Head node...\n";
	Head = newNode;
	Head->Next = NULL;
	Head->Prev = NULL;
  }
  else
  {
	cout << "Inserting after the Head node somewhere...\n";
	Node * curr = Head;
	Node * prev = NULL;
	while(curr != NULL)
	{
	  prev = curr;
	  curr = curr->Next;
	  if(curr == Head)
	  {
		cout << "Circular.\n";
		break;
	  }
	}
	newNode->Next = curr;
	newNode->Prev = prev;
	prev->Next = newNode;
  }
}

Here's the Delete function:

void LL::DeleteNode(Node * delNode)
{
	Node * curr = SearchNode(delNode);

	if(curr == NULL)
	{
	  cout << "Didn't find the info in the list.\n";
	  return;
	}
	else
	{
	  if(curr == Head)
	  {
		cout << "Node info to delete was in the Head node.\n";
		Head = Head->Next;
		delete curr->Item->Name;
		delete curr;
	  }
	  else if(curr->Next == NULL)
	  {				  
		cout << "Node info to delete was in the last node in the list.\n";
		curr->Prev->Next = Head;
		Head->Prev = curr->Prev;
		delete curr->Item->Name;
		delete curr;
	  }
	  else
	  {
		cout << "Node info to delete was in the middle of the list.\n";
		curr->Prev->Next = curr->Next;
		curr->Next->Prev = curr->Prev;
		delete curr->Item->Name;
		delete curr;
	  }
	}
}

The Search function looks like this:

LL::Node * LL::SearchNode(Node * srchNode)
{
  Node * curr;
  if(Head == NULL)
  {
	cout << "The list is empty\n";
  }
  else
  {
	cout << "head is not NULL...searching...\n";
	curr = Head;
	while(curr != NULL)
	{
	  if((strcmp(curr->Item->Name, srchNode->Item->Name)==0) &&
				(curr->Item->Age == srchNode->Item->Age))
	  {
		cout << "Found the info in the list...\n";
		break;
	  }
	  curr = curr->Next;
	  if(curr == Head)
	  {
		cout << "Circular.\n";
		break;
	  }
	}

	if(curr != NULL)
	{
	  return curr;
	}
	else
	{
	  cout << "Info not in the list.\n";
	  return NULL;
	}
  }
}

[baavgai]

Did you say "circular doubly linked list"? If so, none of your node pointers should ever be NULL. Before you could ignore one side if you added at top or bottom, now you can't.

Inserting a node is the same, no matter where you do it. You just need to know who you're next to. I'll give you this one.

void LL::InsertNodePrior(Node * newNode, Node * nextNode) {
	if (priorNode == NULL) {
		newNode->Prev = newNode;
		newNode->Next = newNode;
	} else {
		newNode->Prev = nextNode->Prev;
		newNode->Next = nextNode;
		// note, you'll always be doing this little attach dance
		// tell the neighbors to point to you
		newNode->Prev->Next = newNode;
		newNode->Next->Prev = newNode;
	}
}

void LL::InsertNodeAtFront(Node * newNode) {
	InsertNodePrior(newNode, Head);
	Head = newNode;
}

void LL::InsertNodeAtEnd(Node * newNode) {
	InsertNodeAtFront(newNode);
	// think about it.
}

I'm just going to have to give the swap, you're not seeing it. You are swaping pointers! It's just like swapping ints. This is the point of having an ItemType, it can be anything and your code needn't worry about it.

void LL::Swap(Node * save, Node * curr) {
	ItemType * temp = save->Item;
	save->Item = curr->Item;
	curr->Item = temp;
}

Now, since you're doing a circular list, go back and make sure nothing has "!=NULL" as a stopper. Otherwise, you'll spin a long time. Remember, your logic is this:

Head==NULL // empty list
Head==Head->Next // list has one value
Node *node = Head;
while(node!=Head) // oops, this doesn't work.  You'll have to figure it out.

Hope this helps.

[stritone]

Hi Baavgai,
Wow, I've got so much to learn about this stuff. The swap function now
makes a lot more sense. I'm still getting used to dealing with multiple
objects. After drawing about 6 or 7 pictures of how the circular doubly
linked list worked and going through step by step how the insertion and
deletion should work I came up with this for deletion:

Is this correct?

void LL::DeleteNode(Node * delNode)
{
	Node * curr = SearchNode(delNode);

	if(curr->Next == curr){
	  cout << "one node in this list.\n";
	  delete curr->Item->Name;
	  delete curr;
	  Head = NULL;
	} else {
	  curr->Prev->Next = curr->Next;
	  curr->Next->Prev = curr->Prev;
	  if(curr == Head){
		Head = curr->Next;
	  }
	  delete curr->Item->Name;
	  delete curr;
	}
}

Thanks again!

[baavgai]

Looks fine from here.

Yes, pointers to pointers can be confusing as hell. I often have to count on my compiler to warn me with the more crazy constructs. In C++, references were supposed to make life easier, but I'm not really sure that's true. Pointers are simply unavoidable, so you're kind of stuck with them.

[stritone]

Hi Baavgai,
Thanks for guidance on this implementation. I'm trying to wrap up the member
functions and wanted to double check the Sort functions before I consider the
program completed. Can you give my Sorting functions a quick glance?
They look real ugly and I'm not sure about the
'curr->Next != Head' or 'save->Next != Head' bit in the 'for' loops.

void LL::SortList_Ascend(){
  Node * temp;
  Node * curr, * save;
  curr = save = Head;
  if (Head == NULL){
	cout << "Linked list is empty\n";
	return;
  } else {
	for(curr = Head; ((curr != NULL)&&(curr->Next != Head)); curr = curr->Next){
	  for(save = curr->Next; ((save != NULL) && (save->Next != Head)); save = save->Next){
		if (strcmp(curr->Item->Name, save->Item->Name) > 0){
		  Swap(save, curr);
		}
	  }
	}
	cout << "The linked list is now sorted in ascending order!\n";
  }
}