Problem with linked list class

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »

48 Replies - 2234 Views - Last Post: 28 March 2013 - 11:19 PM Rate Topic: -----

#1 jayburn00  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 118
  • Joined: 05-July 12

Problem with linked list class

Posted 24 March 2013 - 11:52 PM

I have been working on a program for homework assignment involving a sorted doubly linked list. Unfortunately, I was very constrained in what I could actually do by the teachers instructions, so bare with anything you find odd but works. Anyway, the difficulty I am having is setting up the assignment operator and copy constructor, because for the assignment operator I haven't even understood what that is in this case, and for the copy constructor, though I understand what I want it to do, and how it would go about it from an algorithm perspective, I am having trouble translating it into C++. It needs to be able to do a deep copy of the linked list and create a new list with the same data, and still be a sorted doubly linked list. The only coding the teacher did by the way for us (though really just constraining) was naming the functions and most of the variables. Anyway, here is what I have so far and if you see any mistakes, let me know(I haven't been able to parse it or check for errors using IDE for some reason):

#include <iostream>
#include <string>

using namespace std;

/* ============= FOR YOUR ANALYSIS ================= 
You need to analyze the following functionalities:
1.	Copy constructor or assignment operator
2.	Insert method
3.	All 3 remove methods
====================================================*/

/**
Item 1 of hw#3 goes here - you  should add any data and functionality as needed 
but do not change the interface of the given methods and attributes 
*/

//utility class to represent a node of the list
template <class Obj>
class Node 
{
public:
	//constructor
	Node(): next(NULL), prev(NULL){} //default constructor
	Node(Obj data):next(NULL), prev(NULL){ this->data = data; }

	//public for efficient access
	Obj data; //the stored
	Node<Obj> * next; //point to next node
	Node<Obj> * prev; //point to previous node
};

/* THE SORTED DOUBLY LINKED LIST */

template<class T>
class SortedList
{
	public:

	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here Jason:  I didn't do this in my assignment 3, bu'st this would make a head node and tail node,
	// head's next pointing to the tail initially, and 
	///////////////////////////////////////////////////////////////////
	//default constructor
	//set next pointer on head to point to tail, and set prev on tail to point to head.


	SortedList():head(NULL), tail(NULL), current(NULL), count(0)
	{
		head = new Node<Obj>;
		tail = new Node<Obj>;
		tail = head->next;
		head = tail->prev;
	}


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//copy constructor
	// copy the content of the given list rhs into a new list
	// + O(n)t.

	//clone list
	SortedList(const SortedList<T> & rhs): head(NULL), tail(NULL)
	{


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//assignment operator
	// + O(n)

	//call copy constructor once.
	SortedList & operator=(const SortedList<T> & rhs) ;

	

	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here
	//Insertion procedure to make sure node is inserted in a way that keeps list sorted:  It iterates two variables simutanously, the pointer starting at the first node and the pointer starting at last node, comparing nodes using => =< operators.
/*Start at beginning, check to make sure beginning node is less than node to be inserted.  
If it is greater, insert new node at beginning.
If it is less than node to be inserted, check the last node, make sure last node is greater
than node to be inserted.  If not, than make node to be inserted last node.
If last node was greater than node to be inserted, go back to beginning and compare next node (2nd in this case)
Make sure next node is less than node to be inserted.  If it isn't, make node to be inserted the 2nd Node(in between the first node and former 2nd node)
If it is less, go to other side again and check the 2nd to last node.  Do similar comparisons until node is inserted, or the two ends of the comparing function meets in middle
In which case node to be inserted is at the median of the linked list.  This algorithm uses a single while statement, with each iteration looking at both ends of the list.
Is inefficient if the insertion point makes the node to be inserted the second node, but if it is at a later position, it is actually as efficient as O(n)=n, and can be more efficient than the regular sorted insert because it does not need to look at every node in sequence.
Only works with doubly linked list, not single linked list.  Uses 3 if statements, one if statement starts for loop (which itself contains an if statement), but if one of the other if statements are followed, loop isn't used saving time.  Best case scenario is if the node will be inserted at beginning or very end, worst case is if it is smack dab in the middle.
Decided that since I such limited amount of time, I would forgo using my above procedure and go with a regular sorted insertion(start at beginning, end at end.  Still tests fist and last nodes though.  Worst case scenario is if is inserted at second to last node position.
If I had more time, I would have used the idea I came up with.

When insert point found, use below function(may need to add it to a function):*/ 
	/*insertDLinkNode(Node *current) //public, used to insert a new node.
	{//Code to insert a node within Linked list
		newNode = new Node(x);
		newNode->prev = current;
		newNode->next = current->next;  
		newNode->prev->next = newNode;
		newNode->next->prev = newNode;
		current = newNode;
		return current;
	}*/
	///////////////////////////////////////////////////////////////////
	// + insert a value into the list in assending order
	// duplicated entry will be ordered by arrival order
	// + current pointer points at the new node
	// + list size must be updated
	// + return the pointer to the new node in the list 
	// + O(n)

	//Jason:  Can use a variation of my sorted insertion, need to add something to make sure duplicates ordered by arrival.
	Node<T> * insert(const T & value);
	{
		Node *firstNode, *lastNode, *nextNode, *prevNode; // nextNode and prevNode are for if the nodes are not at the beginning or end.
		firstNode=head->next;
		lastNode=tail->prev;
		if (value < (firstNode->data))
		{
			newNode = new Node(x);
			newNode -> prev = head;
			newNode -> next = firstNode;
			head->next = newNode;
			firstNode = newNode;
			current = firstNode;
			return current;
		}
		else if (value > (lastNode->data))
		{
			newNode = new Node(x);
			newNode -> next = head;
			newNode -> prev = lastNode;
			tail -> prev = newNode;
			lastNode = newNode;
			current = lastNode;
			return current;
		}
		else
		{
			for (current = firstNode -> next; (current == lastNode -> prev) || ((current -> data == value) && (current->next->data > value); current = current -> next;)
			{
				if (((current-> data) <= value) && ((current -> next -> data) > value))
				{
					newNode = new Node(x);
					newNode->prev = current;
					newNode->next = current->next;  
					newNode->prev->next = newNode;
					newNode->next->prev = newNode;
					current = newNode;
					return current;
				}
			}
		}
	}
			

		/*insertDLinkNode(Node *current) //public, used to insert a new node. insert function followed this general form.
	{//Code to insert a node within Linked list
		newNode = new Node(x);
		newNode->prev = current;
		newNode->next = current->next;  
		newNode->prev->next = newNode;
		newNode->next->prev = newNode;
		current = newNode;
		return current;
	}*/
			
			
		
	 

		
	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//+ check the node at all three internal pointers: head, tail, current
	//  to find the range in which the node is in; then scan the range to 
	// find the node with given value
	// + if found the node in the list, the current pointer points at the first 
	// found node
	// + return NULL if not found or the pointer to the first matching
	// + O(n)

	//Jason: Search function.  Return pointer.  
	Node<T> * find(const T & value) const
	{
		if(((head->next->data) > search_term) || ((tail->prev->data) < (search_term)))
		{
			return null;
		}
		else //if (current->data != value)
		{
			Node<Obj> * p = head-> next;
			while (p != NULL && p != value)
			{
					p = p->next;
					if (p > data)
						return NULL;
			}
				
			current = p;
			return Node<T>(p);
		}
	}
		

		


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + remove all nodes with the given value
	// + current pointer points at the node immediately after the removing nodes
	// + list size must be updated (use size function)
	// + return number of removed nodes Jason:  (perhaps create variable of size before removal-size after removal)
	// + O(n)

	//Jason:  will have to go through whole list to remove nodes with a specific value.
	//Jason:  can use a variant on the removal algorithm that I came up with for assignment 3.
	//algorithm needs to be altered so that instead of simply removing the first node it comes across that has the specified value,
	//(c)it will remove all nodes in the list with the specified value.  Will need to reassign 2 pointers, delete all others.
	int remove(const T & value);


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//+ remove node pointed by the pointer 
	//+ current pointer point at the node immediately after the removed node
	// + list size must be updated
	//+ return the current pointer
	//+ O(1)
	
	//Jason:  This can use an almost exact duplicate of the algorithm from assignment 3 that I came up with.  Unless this isn't the file I'm supposed to insert that code in.
	//Jason:  Will have to create and attach code that makes current pointer point at node that comes after removed node (if mine does not already).
	//Jason:  move current pointer to next node.  
	Node<T> * remove(Node<T> * node); //public function, returns current.  Needed to delete nodes without compromising the whole list.  Frees up memory when node removed.
	{
		node->prev->next = node->next;
		node->next->prev = node->prev;
		current = node->next;
		delete node;
		count--;
		return current;
	}


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + remove all nodes, inclusively, between the two given pointers
	// + current pointer point at the node immediately after the removing nodes
	// + return number of nodes removed
	// + list size must be updated
	// + O(n)

	//Jason:  will be similar to other multiple delete, but instead of looking at duplicates, it simply deletes everything between plus given pointers.
	int remove(Node<T> * from, Node<T> * to)
	{
		int originalSize = size();
		while (current = from; current == to;)
		{
			remove(Node<T> current);
		}
		remove(Node<T> current);
		return (originalSize-size());
	}

	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here
	//uses a loop that calls my single node remove function, until the list is empty.  Use the count variable to track to see if size equals zero.  Afterward, may need to put in a delete head and tail outside of loop.
	///////////////////////////////////////////////////////////////////
	// destructor: remove all the nodes
	//O(n)

	
	~SortedList()
	{
		current = head -> next;
		while(current -> next != null)
		{
			remove(Node<T> current);
		}
		delete head;
		delete tail;

	}
 
	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + return the number of node in the list
	//O(1)
	int size() const 
	{

		return this->count;
	}

	private:
	//data members
	Node<T>*current; //point at the last access node.  Create a constructor for current.  In linked list class.
	Node<T>*head;    //points at the head of the list.  Create a constructor for head.
	Node<T> *tail;   //points at the tail of the list.  Create a constructor for tail.
	int count;       // the total number of nodes in the list
}; //end of SortedList class




Is This A Good Question/Topic? 0
  • +

Replies To: Problem with linked list class

#2 jimblumberg  Icon User is offline

  • member icon


Reputation: 4003
  • View blog
  • Posts: 12,351
  • Joined: 25-December 09

Re: Problem with linked list class

Posted 25 March 2013 - 03:30 AM

Quote

I haven't been able to parse it or check for errors using IDE for some reason

Usually error messages are a good indication of problems. You should be compiling often and fixing the errors as you go, not compiling after writing everything.

The first thing I notice is this:
	SortedList(const SortedList<T> & rhs): head(NULL), tail(NULL)
	{


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here
	///////////////////////////////////////////////////////////////////
	//assignment operator
	// + O(n)

	//call copy constructor once.
	SortedList & operator=(const SortedList<T> & rhs) ;


You seem to be missing a closing brace for the constructor.

Next this:
	Node<T> * insert(const T & value);
	{


Here you seem to have an errant semicolon. You do this several places.

So before you even worry about adding anything else fix these and any other errors you find before moving on.

Once you have the errors fixed you will need to create your main and actually try to use this class, because you are using templates, then recompile. Templates are not actually created until they are used so create a function that actually tries to declare and use the class.

I also edited your title to be more accurate.


Jim

This post has been edited by jimblumberg: 25 March 2013 - 03:31 AM

Was This Post Helpful? 0
  • +
  • -

#3 jayburn00  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 118
  • Joined: 05-July 12

Re: Problem with linked list class

Posted 25 March 2013 - 06:10 AM

The reason some of the functions have semicolons there is because this was originally meant to be a header file I think (teacher made this), and all he did was declare the functions (I think, could also be the teacher made a lot of mistakes, wouldn't be the first time his own code was incorrect). Wouldn't it be hard to test my code without the copy constructor and assignment operator? Those were the parts by the way that had the mismatched brackets and the semicolon I think, because I don't know what to do.

This post has been edited by jayburn00: 25 March 2013 - 06:12 AM

Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is offline

  • member icon


Reputation: 4003
  • View blog
  • Posts: 12,351
  • Joined: 25-December 09

Re: Problem with linked list class

Posted 25 March 2013 - 06:53 AM

Quote

The reason some of the functions have semicolons there is because this was originally meant to be a header file I think (teacher made this), and all he did was declare the functions

The problem is that when you went to implement the functions you tried to implement them inside the class definition, instead of placing them outside the class definition, therefore you need to remove the semicolons. This is not a mistake by your instructor, it is your mistake. Normally the definition of the class is separated from the implementation:

class Test
{
   public:
      void someFunction();
   private:
      int someVariable;
};

void Test::someFunction()
{
   someVariable = 10;
}



Quote

Wouldn't it be hard to test my code without the copy constructor and assignment operator? Those were the parts by the way that had the mismatched brackets and the semicolon I think,


No, you should be able to test most of the class without the copy constructor and assignment operator. There are "extra" semicolons several places in your code not just the assignment and assignment operator. Like I said before you go any further get the program to compile without warnings or errors.

Jim

This post has been edited by jimblumberg: 25 March 2013 - 06:54 AM

Was This Post Helpful? 0
  • +
  • -

#5 jayburn00  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 118
  • Joined: 05-July 12

Re: Problem with linked list class

Posted 25 March 2013 - 07:28 AM

I'm just trying to say, that the part that is so obviously incorrect in the way you are describing was not written by me, the code I wrote I had someone else look at and they found it good, and they did it on their IDE too.
Was This Post Helpful? 0
  • +
  • -

#6 jimblumberg  Icon User is offline

  • member icon


Reputation: 4003
  • View blog
  • Posts: 12,351
  • Joined: 25-December 09

Re: Problem with linked list class

Posted 25 March 2013 - 07:40 AM

Well then if you won't fix the obvious problems I've pointed out then there is no reason for me to continue trying to help. Good luck on your project.

Jim
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3534
  • View blog
  • Posts: 10,941
  • Joined: 05-May 12

Re: Problem with linked list class

Posted 25 March 2013 - 07:49 AM

I'm trying to not go down the rabbit hole of "he wrote, she wrote", but I'm dying of curiosity as to what IDE you are using versus the IDE that the other person who you mentioned on post #5 was using. Some IDE's do syntax highlight on a purely lexical parsing without actually doing any deep syntactic parsing. (eg. The code highlighter used by DIC simply keys off keywords and substrings. Compare that to the code highlighter in VS2008 or VS2013 which actually runs the front end of the C++ compiler to get it's syntax highlighting to work.) If the other person was using a simplistic IDE, then that is not a valid test. It's like saying that you got flying colors for your eye exam from the Department of Motor Vehicles.
Was This Post Helpful? 0
  • +
  • -

#8 jayburn00  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 118
  • Joined: 05-July 12

Re: Problem with linked list class

Posted 25 March 2013 - 08:29 AM

Well, I fixed the semicolon issues I think, and also added more code, I was missing a component that I thought I had done already. I am using VS2013, I think its not error checking because I currently don't have this as a project, just a cpp file (there are some IDE's that don't need you to make a project to check the cpp file for errors, but it looks like VS2013 is not one of them.) I know I need to make a main (probably a separate file and make the one I'm working on a header file, or do I keep this a cpp file and put the main in this file, the way the teacher set it up really confused me, since he said he was giving a header file. I will post the original file as it was when he gave it out, but in the context of a header file, might help a little.
Anyway, the file the teacher gave out without any changes from me:
SortedList.h:
#include <iostream>
#include <string>

using namespace std;

/* ============= FOR YOUR ANALYSIS ================= 
You need to analyze the following functionalities:
1.	Copy constructor or assignment operator
2.	Insert method
3.	All 3 remove methods
====================================================*/

/**
Item 1 of hw#3 goes here - you  should add any data and functionality as needed
but do not change the interface of the given methods and attributes
*/

//utility class to represent a node of the list
template <class Obj>
class Node {
public:
	//constructor
	Node(): next(NULL), prev(NULL){} //default constructor
	Node(Obj data):next(NULL), prev(NULL){ this->data = data; }

	//public for efficient access
	Obj data; //the stored
	Node<Obj> * next; //point to next node
	Node<Obj> * prev; //point to previous node
};

/* THE SORTED DOUBLY LINKED LIST */

template<class T>
class SortedList{
	public:

	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//default constructor
	SortedList():head(NULL), tail(NULL), current(NULL), count(0){}


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//copy constructor
	// copy the content of the given list rhs into a new list
	// + O(n)
	SortedList(const SortedList<T> & rhs);

	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//assignment operator
	// + O(n)
	SortedList & operator=(const SortedList<T> & rhs) ;

	

	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + insert a value into the list in assending order
	// duplicated entry will be ordered by arrival order
	// + current pointer points at the new node
	// + list size must be updated
	// + return the pointer to the new node in the list 
	// + O(n)
	Node<T> * insert(const T & value);
	 


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//+ check the node at all three internal pointers: head, tail, current
	//  to find the range in which the node is in; then scan the range to 
	// find the node with given value
	// + if found the node in the list, the current pointer points at the first 
	// found node
	// + return NULL if not found or the pointer to the first matching
	// + O(n)
	Node<T> * find(const T & value) const;


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + remove all nodes with the given value
	// + current pointer points at the node immediately after the removing nodes
	// + list size must be updated
	// + return number of removed nodes
	// + O(n)
	int remove(const T & value);


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//+ remove node pointed by the pointer 
	//+ current pointer point at the node immediately after the removed node
	// + list size must be updated
	//+ return the current pointer
	//+ O(1)
	Node<T> * remove(Node<T> * node);


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + remove all nodes, inclusively, between the two given pointers
	// + current pointer point at the node immediately after the removing nodes
	// + return number of nodes removed
	// + list size must be updated
	// + O(n)
	int remove(Node<T> * from, Node<T> * to);

	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// destructor: remove all the nodes
	//O(n)
	~SortedList(){}
 
	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + return the number of node in the list
	//O(1)
	int size() const { return this->count;}

	private:
	//data members
	Node<T>*current; //point at the last access node
	Node<T>*head;    //points at the head of the list
	Node<T> *tail;   //points at the tail of the list
	int count;       // the total number of nodes in the list
}; //end of SortedList class






The class functions, constructors, etc. etc. that I have coded, copy constructor and assignment operator still missing:
#include <iostream>
#include <string>//Jason:  why is string needed in include statements?

using namespace std;

/* ============= FOR YOUR ANALYSIS ================= 
You need to analyze the following functionalities:
1.	Copy constructor or assignment operator
2.	Insert method
3.	All 3 remove methods
====================================================*/

/**
Item 1 of hw#3 goes here - you  should add any data and functionality as needed 
but do not change the interface of the given methods and attributes 
*/

//utility class to represent a node of the list
template <class Obj>
class Node 
{
public:
	//constructor
	Node(): next(NULL), prev(NULL){} //default constructor
	Node(Obj data):next(NULL), prev(NULL){ this->data = data; }

	//public for efficient access
	Obj data; //the stored
	Node<Obj> * next; //point to next node
	Node<Obj> * prev; //point to previous node
};

/* THE SORTED DOUBLY LINKED LIST */

template<class T>
class SortedList
{
	public:

	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here Jason:  I didn't do this in my assignment 3, but this would make a head node and tail node,
	// head's next pointing to the tail initially, and tail prev pointer initially pointing to head.
	///////////////////////////////////////////////////////////////////
	//default constructor
	//set next pointer on head to point to tail, and set prev on tail to point to head.


	SortedList():head(NULL), tail(NULL), current(NULL), count(0)
	{
		head = new Node<Obj>;
		tail = new Node<Obj>;
		tail = head->next;
		head = tail->prev;
	}


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//copy constructor
	// copy the content of the given list rhs into a new list
	// + O(n)t.

	//clone list
	SortedList(const SortedList<T> & rhs): head(NULL), tail(NULL)
	{


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//assignment operator
	// + O(n)

	//call copy constructor once.
	SortedList & operator=(const SortedList<T> & rhs) ;

	

	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here
	//Insertion procedure to make sure node is inserted in a way that keeps list sorted:  It iterates two variables simutanously, the pointer starting at the first node and the pointer starting at last node, comparing nodes using => =< operators.
/*Start at beginning, check to make sure beginning node is less than node to be inserted.  
If it is greater, insert new node at beginning.
If it is less than node to be inserted, check the last node, make sure last node is greater
than node to be inserted.  If not, than make node to be inserted last node.
If last node was greater than node to be inserted, go back to beginning and compare next node (2nd in this case)
Make sure next node is less than node to be inserted.  If it isn't, make node to be inserted the 2nd Node(in between the first node and former 2nd node)
If it is less, go to other side again and check the 2nd to last node.  Do similar comparisons until node is inserted, or the two ends of the comparing function meets in middle
In which case node to be inserted is at the median of the linked list.  This algorithm uses a single while statement, with each iteration looking at both ends of the list.
Is inefficient if the insertion point makes the node to be inserted the second node, but if it is at a later position, it is actually as efficient as O(n)=n, and can be more efficient than the regular sorted insert because it does not need to look at every node in sequence.
Only works with doubly linked list, not single linked list.  Uses 3 if statements, one if statement starts for loop (which itself contains an if statement), but if one of the other if statements are followed, loop isn't used saving time.  Best case scenario is if the node will be inserted at beginning or very end, worst case is if it is smack dab in the middle.
Decided that since I such limited amount of time, I would forgo using my above procedure and go with a regular sorted insertion(start at beginning, end at end.  Still tests fist and last nodes though.  Worst case scenario is if is inserted at second to last node position.
If I had more time, I would have used the idea I came up with.

When insert point found, use below function(may need to add it to a function):*/ 
	/*insertDLinkNode(Node *current) //public, used to insert a new node.
	{//Code to insert a node within Linked list
		newNode = new Node(x);
		newNode->prev = current;
		newNode->next = current->next;  
		newNode->prev->next = newNode;
		newNode->next->prev = newNode;
		current = newNode;
		return current;
	}*/
	///////////////////////////////////////////////////////////////////
	// + insert a value into the list in assending order
	// duplicated entry will be ordered by arrival order
	// + current pointer points at the new node
	// + list size must be updated
	// + return the pointer to the new node in the list 
	// + O(n)

	//Jason:  Can use a variation of my sorted insertion, need to add something to make sure duplicates ordered by arrival.
	Node<T> * insert(const T & value)
	{
		Node *firstNode, *lastNode, *nextNode, *prevNode; // nextNode and prevNode are for if the nodes are not at the beginning or end.
		firstNode=head->next;
		lastNode=tail->prev;
		if (value < (firstNode->data))
		{
			newNode = new Node(x);
			newNode -> prev = head;
			newNode -> next = firstNode;
			head->next = newNode;
			firstNode = newNode;
			current = firstNode;
			return current;
		}
		else if (value > (lastNode->data))
		{
			newNode = new Node(x);
			newNode -> next = head;
			newNode -> prev = lastNode;
			tail -> prev = newNode;
			lastNode = newNode;
			current = lastNode;
			return current;
		}
		else
		{
			for (current = firstNode -> next; (current == lastNode -> prev) || ((current -> data == value) && (current->next->data > value); current = current -> next;)
			{
				if (((current-> data) <= value) && ((current -> next -> data) > value))
				{
					newNode = new Node(x);
					newNode->prev = current;
					newNode->next = current->next;  
					newNode->prev->next = newNode;
					newNode->next->prev = newNode;
					current = newNode;
					return current;
				}
			}
		}
	}
			

		/*insertDLinkNode(Node *current) //public, used to insert a new node. insert function followed this general form.
	{//Code to insert a node within Linked list
		newNode = new Node(x);
		newNode->prev = current;
		newNode->next = current->next;  
		newNode->prev->next = newNode;
		newNode->next->prev = newNode;
		current = newNode;
		return current;
	}*/
			
			
		
	 

		
	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	//this will be a sort of search function that returns a pointer to the first node found with the desired value.
	//If the value is not found in list, it returns NULL.
	///////////////////////////////////////////////////////////////////
	//+ check the node at all three internal pointers: head, tail, current
	//  to find the range in which the node is in; then scan the range to 
	// find the node with given value
	// + if found the node in the list, the current pointer points at the first 
	// found node
	// + return NULL if not found or the pointer to the first matching
	// + O(n)

	//Jason: Search function.  Return pointer.  
	Node<T> * find(const T & value) const
	{
		if(((head->next->data) > search_term) || ((tail->prev->data) < (search_term)))
		{
			return null;
		}
		else //if (current->data != value)
		{
			Node<Obj> * p = head-> next;
			while (p != NULL && p != value)
			{
					p = p->next;
					if (p > data)
						return NULL;
			}
				
			current = p;
			return Node<T>(p);
		}
	}
		

		


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + remove all nodes with the given value
	// + current pointer points at the node immediately after the removing nodes
	// + list size must be updated (use size function)
	// + return number of removed nodes Jason:  (perhaps create variable of size before removal-size after removal)
	// + O(n)

	//Jason:  will have to go through whole list to remove nodes with a specific value.
	//Jason:  can use a variant on the removal algorithm that I came up with for assignment 3.
	//algorithm needs to be altered so that instead of simply removing the first node it comes across that has the specified value,
	//(c)it will remove all nodes in the list with the specified value.  Will need to reassign 2 pointers, delete all others.
	int remove(const T & value)
	{
		originalSize = size();
		for (find(const T & value) const; ((current->data) != value); remove(current))//since the find function returns current as being equal to the current pointer to the value sought, I put that as the start condition.  This will be an empty for loop, since the single remove function removes a single node and then moves current to next.
		{//leave empty;
		}
		return (originalSize - size());
	}
		
		
		


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//+ remove node pointed by the pointer 
	//+ current pointer point at the node immediately after the removed node
	// + list size must be updated
	//+ return the current pointer
	//+ O(1)
	
	//Jason:  This can use an almost exact duplicate of the algorithm from assignment 3 that I came up with.  Unless this isn't the file I'm supposed to insert that code in.
	//Jason:  Will have to create and attach code that makes current pointer point at node that comes after removed node (if mine does not already).
	//Jason:  move current pointer to next node.  
	Node<T> * remove(Node<T> * node); //public function, returns current.  Needed to delete nodes without compromising the whole list.  Frees up memory when node removed.
	{
		node->prev->next = node->next;
		node->next->prev = node->prev;
		current = node->next;
		delete node;
		count--;
		return current;
	}


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + remove all nodes, inclusively, between the two given pointers
	// + current pointer point at the node immediately after the removing nodes
	// + return number of nodes removed
	// + list size must be updated
	// + O(n)

	//Jason:  will be similar to other multiple delete, but instead of looking at duplicates, it simply deletes everything between plus given pointers.
	int remove(Node<T> * from, Node<T> * to)
	{
		int originalSize = size();
		while (current = from; current == to;)
		{
			remove(Node<T> current);
		}
		remove(Node<T> current);
		return (originalSize-size());
	}

	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here
	//uses a loop that calls my single node remove function, until the list is empty.  Use the count variable to track to see if size equals zero.  Afterward, may need to put in a delete head and tail outside of loop.
	///////////////////////////////////////////////////////////////////
	// destructor: remove all the nodes
	//O(n)

	
	~SortedList()
	{
		current = head -> next;
		while(current -> next != null)
		{
			remove(Node current);
		}
		delete head;
		delete tail;

	}
 
	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + return the number of node in the list
	//O(1)
	int size() const 
	{

		return this->count;
	}

	private:
	//data members
	Node<T>*current; //point at the last access node.  Create a constructor for current.  In linked list class.
	Node<T>*head;    //points at the head of the list.  Create a constructor for head.
	Node<T> *tail;   //points at the tail of the list.  Create a constructor for tail.
	int count;       // the total number of nodes in the list
}; //end of SortedList class




One reason I haven't gone and created a main yet is because the way the teacher set this up, is that the teacher doesn't give us much time on the assignment and the main he wants is complicated to set up (it has to test 15 different list creations, each one 100 times, find average run time completion, and then we graph it. Since it is difficult to run a test 1500 times manually, he says to make main do it. I will have enough debugging as is with that monstrosity(not that familiar with creating a program like that), prefer not to add more to it. All I want is tips on how to create the copy constructor for this this and the assignment operator, unless you see other errors I am currently unable to detect, again I fixed the semicolon issue I think.)
Edit: just realized, I think I may be missing an awful lot of include statements, as to which ones, not sure.

This post has been edited by jayburn00: 25 March 2013 - 08:31 AM

Was This Post Helpful? 0
  • +
  • -

#9 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3534
  • View blog
  • Posts: 10,941
  • Joined: 05-May 12

Re: Problem with linked list class

Posted 25 March 2013 - 08:47 AM

By not writing even a minimal main() function, you are delaying all your problems until later which will be one giant snowball. For a minimal main() all you need is is to simply have something that instantiates the list, inserts 5 items, and removes 5 items. You can do the more comprehensive test that your teach wants later. By doing this now, you can test your code as you go along versus having to test everything later in one big chunk and having to take account your timing code, graphing code, etc.
Was This Post Helpful? 0
  • +
  • -

#10 jayburn00  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 118
  • Joined: 05-July 12

Re: Problem with linked list class

Posted 25 March 2013 - 10:47 AM

Ok, did as you suggested and created a main. I filled a list with 5 integers in sequence (either 1-5 or 0-5). I got 6 errors, but they are mostly the same errors, have something to do with the default constructor. What have I done wrong?
#include <iostream>
#include <string>//Jason:  why is string needed in include statements?

using namespace std;

/* ============= FOR YOUR ANALYSIS ================= 
You need to analyze the following functionalities:
1.	Copy constructor or assignment operator
2.	Insert method
3.	All 3 remove methods
====================================================*/

/**
Item 1 of hw#3 goes here - you  should add any data and functionality as needed 
but do not change the interface of the given methods and attributes 
*/

//utility class to represent a node of the list
template <class Obj>
class Node 
{
public:
	//constructor
	Node(): next(NULL), prev(NULL){}; //default constructor
	Node(Obj data):next(NULL), prev(NULL){ this->data = data; }

	//public for efficient access
	Obj data; //the stored
	Node<Obj> * next; //point to next node
	Node<Obj> * prev; //point to previous node
};

/* THE SORTED DOUBLY LINKED LIST */

template<class T>
class SortedList
{
	public:

	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here Jason:  I didn't do this in my assignment 3, but this would make a head node and tail node,
	// head's next pointing to the tail initially, and tail prev pointer initially pointing to head.
	///////////////////////////////////////////////////////////////////
	//default constructor
	//set next pointer on head to point to tail, and set prev on tail to point to head.


	SortedList():head(NULL), tail(NULL), current(NULL), count(0)
	{
		head = new Node<Obj>;
		tail = new Node<Obj>;
		tail = head->next;
		head = tail->prev;
	}


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//copy constructor
	// copy the content of the given list rhs into a new list
	// + O(n)t.

	//clone list
	SortedList(const SortedList<T> & rhs): head(NULL), tail(NULL)
	{
	}


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//assignment operator
	// + O(n)

	//call copy constructor once.
	SortedList & operator=(const SortedList<T> & rhs) ;

	

	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here
	//Insertion procedure to make sure node is inserted in a way that keeps list sorted:  It iterates two variables simutanously, the pointer starting at the first node and the pointer starting at last node, comparing nodes using => =< operators.
/*Start at beginning, check to make sure beginning node is less than node to be inserted.  
If it is greater, insert new node at beginning.
If it is less than node to be inserted, check the last node, make sure last node is greater
than node to be inserted.  If not, than make node to be inserted last node.
If last node was greater than node to be inserted, go back to beginning and compare next node (2nd in this case)
Make sure next node is less than node to be inserted.  If it isn't, make node to be inserted the 2nd Node(in between the first node and former 2nd node)
If it is less, go to other side again and check the 2nd to last node.  Do similar comparisons until node is inserted, or the two ends of the comparing function meets in middle
In which case node to be inserted is at the median of the linked list.  This algorithm uses a single while statement, with each iteration looking at both ends of the list.
Is inefficient if the insertion point makes the node to be inserted the second node, but if it is at a later position, it is actually as efficient as O(n)=n, and can be more efficient than the regular sorted insert because it does not need to look at every node in sequence.
Only works with doubly linked list, not single linked list.  Uses 3 if statements, one if statement starts for loop (which itself contains an if statement), but if one of the other if statements are followed, loop isn't used saving time.  Best case scenario is if the node will be inserted at beginning or very end, worst case is if it is smack dab in the middle.
Decided that since I such limited amount of time, I would forgo using my above procedure and go with a regular sorted insertion(start at beginning, end at end.  Still tests fist and last nodes though.  Worst case scenario is if is inserted at second to last node position.
If I had more time, I would have used the idea I came up with.

When insert point found, use below function(may need to add it to a function):*/ 
	/*insertDLinkNode(Node *current) //public, used to insert a new node.
	{//Code to insert a node within Linked list
		newNode = new Node(x);
		newNode->prev = current;
		newNode->next = current->next;  
		newNode->prev->next = newNode;
		newNode->next->prev = newNode;
		current = newNode;
		return current;
	}*/
	///////////////////////////////////////////////////////////////////
	// + insert a value into the list in assending order
	// duplicated entry will be ordered by arrival order
	// + current pointer points at the new node
	// + list size must be updated
	// + return the pointer to the new node in the list 
	// + O(n)

	//Jason:  Can use a variation of my sorted insertion, need to add something to make sure duplicates ordered by arrival.
	Node<T> * insert(const T & value)
	{
		Node *firstNode, *lastNode, *nextNode, *prevNode; // nextNode and prevNode are for if the nodes are not at the beginning or end.
		firstNode=head->next;
		lastNode=tail->prev;
		if (value < (firstNode->data))
		{
			newNode = new Node(x);
			newNode -> prev = head;
			newNode -> next = firstNode;
			head->next = newNode;
			firstNode = newNode;
			current = firstNode;
			return current;
		}
		else if (value > (lastNode->data))
		{
			newNode = new Node(x);
			newNode -> next = head;
			newNode -> prev = lastNode;
			tail -> prev = newNode;
			lastNode = newNode;
			current = lastNode;
			return current;
		}
		else
		{
			for ((current = firstNode -> next); (current == lastNode -> prev) || ((current -> data == value) && (current->next->data > value); current = current -> next;))
			{
				if (((current-> data) <= value) && ((current -> next -> data) > value))
				{
					newNode = new Node(x);
					newNode->prev = current;
					newNode->next = current->next;  
					newNode->prev->next = newNode;
					newNode->next->prev = newNode;
					current = newNode;
					return current;
				}
			}
		}
	}
			

		/*insertDLinkNode(Node *current) //public, used to insert a new node. insert function followed this general form.
	{//Code to insert a node within Linked list
		newNode = new Node(x);
		newNode->prev = current;
		newNode->next = current->next;  
		newNode->prev->next = newNode;
		newNode->next->prev = newNode;
		current = newNode;
		return current;
	}*/
			
			
		
	 

		
	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	//this will be a sort of search function that returns a pointer to the first node found with the desired value.
	//If the value is not found in list, it returns NULL.
	///////////////////////////////////////////////////////////////////
	//+ check the node at all three internal pointers: head, tail, current
	//  to find the range in which the node is in; then scan the range to 
	// find the node with given value
	// + if found the node in the list, the current pointer points at the first 
	// found node
	// + return NULL if not found or the pointer to the first matching
	// + O(n)

	//Jason: Search function.  Return pointer.  
	Node<T> * find(const T & value) const
	{
		if(((head->next->data) > search_term) || ((tail->prev->data) < (search_term)))
		{
			return null;
		}
		else //if (current->data != value)
		{
			Node<Obj> * p = head-> next;
			while (p != NULL && p != value)
			{
					p = p->next;
					if (p > data)
						return NULL;
			}
				
			current = p;
			return Node<T>(p);
		}
	}
		

		


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + remove all nodes with the given value
	// + current pointer points at the node immediately after the removing nodes
	// + list size must be updated (use size function)
	// + return number of removed nodes Jason:  (perhaps create variable of size before removal-size after removal)
	// + O(n)

	//Jason:  will have to go through whole list to remove nodes with a specific value.
	//Jason:  can use a variant on the removal algorithm that I came up with for assignment 3.
	//algorithm needs to be altered so that instead of simply removing the first node it comes across that has the specified value,
	//(c)it will remove all nodes in the list with the specified value.  Will need to reassign 2 pointers, delete all others.
	int remove(const T & value)
	{
		originalSize = size();
		for (find(const T & value) const; ((current->data) != value); remove(current))//since the find function returns current as being equal to the current pointer to the value sought, I put that as the start condition.  This will be an empty for loop, since the single remove function removes a single node and then moves current to next.
		{//leave empty;
		}
		return (originalSize - size());
	}
		
		
		


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	//+ remove node pointed by the pointer 
	//+ current pointer point at the node immediately after the removed node
	// + list size must be updated
	//+ return the current pointer
	//+ O(1)
	
	//Jason:  This can use an almost exact duplicate of the algorithm from assignment 3 that I came up with.  Unless this isn't the file I'm supposed to insert that code in.
	//Jason:  Will have to create and attach code that makes current pointer point at node that comes after removed node (if mine does not already).
	//Jason:  move current pointer to next node.  
	Node<T> * remove(Node<T> * node)//public function, returns current.  Needed to delete nodes without compromising the whole list.  Frees up memory when node removed.
	{
		node->prev->next = node->next;
		node->next->prev = node->prev;
		current = node->next;
		delete node;
		count--;
		return current;
	}


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + remove all nodes, inclusively, between the two given pointers
	// + current pointer point at the node immediately after the removing nodes
	// + return number of nodes removed
	// + list size must be updated
	// + O(n)

	//Jason:  will be similar to other multiple delete, but instead of looking at duplicates, it simply deletes everything between plus given pointers.
	int remove(Node<T> * from, Node<T> * to)
	{
		int originalSize = size();
		while (current = from; current == to;)
		{
			remove(Node<T> current);
		}
		remove(Node<T> current);
		return (originalSize-size());
	}



	//for testing I have made a cycle through function, simply cycles through the list, printing data.
	void printList()
	{
		current = head -> next;
		while(current != tail)
		{
			cout << (current -> data);
			current = current -> next;
		}
	}


	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here
	//uses a loop that calls my single node remove function, until the list is empty.  Use the count variable to track to see if size equals zero.  Afterward, may need to put in a delete head and tail outside of loop.
	///////////////////////////////////////////////////////////////////
	// destructor: remove all the nodes
	//O(n)

	
	~SortedList()
	{
		current = head -> next;
		while(current -> next != null)
		{
			remove(Node current);
		}
		delete head;
		delete tail;

	}
 
	////////////////////////////////////////////////////////////////////
	// Put your hw#3 coresponding item here 
	///////////////////////////////////////////////////////////////////
	// + return the number of node in the list
	//O(1)
	int size() const 
	{

		return this->count;
	}

	private:
	//data members
	Node<T>*current; //point at the last access node.  Create a constructor for current.  In linked list class.
	Node<T>*head;    //points at the head of the list.  Create a constructor for head.
	Node<T> *tail;   //points at the tail of the list.  Create a constructor for tail.
	int count;       // the total number of nodes in the list
}; //end of SortedList class

int main()
{
	SortedList<int>(testList1);
	for(int i = 0; i == 5; i++)
	{
		testList1.insert(i);
	}
	testList1.printList();
	return 0;
}





errors:
Error 1 error C2065: 'Obj' : undeclared identifier c:\users\jason burn\desktop\compsci class\hw3and4\sortedlist.cpp 50

Error 2 error C2923: 'Node' : 'Obj' is not a valid template type argument for parameter 'Obj' c:\users\jason burn\desktop\compsci class\hw3and4\sortedlist.cpp 50

Error 3 error C2512: 'Node' : no appropriate default constructor available c:\users\jason burn\desktop\compsci class\hw3and4\sortedlist.cpp 50

And for the next 3 errors, its a repeat of above, but on line 51 instead of line 50.
Was This Post Helpful? 0
  • +
  • -

#11 jayburn00  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 118
  • Joined: 05-July 12

Re: Problem with linked list class

Posted 25 March 2013 - 12:45 PM

I think I'm making syntax errors in regards to this using templates. I am somehow not defining obj, or somehow not calling the constructor.
Was This Post Helpful? 0
  • +
  • -

#12 jimblumberg  Icon User is offline

  • member icon


Reputation: 4003
  • View blog
  • Posts: 12,351
  • Joined: 25-December 09

Re: Problem with linked list class

Posted 25 March 2013 - 01:00 PM

Quote

I am somehow not defining obj

So what is an obj? Shouldn't it be the same Type as your template class Type?

Jim
Was This Post Helpful? 0
  • +
  • -

#13 jayburn00  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 118
  • Joined: 05-July 12

Re: Problem with linked list class

Posted 25 March 2013 - 01:06 PM

Afraid I don't understand what you are saying there.
Edit: Obj is supposed to be a generic type, to be replaced by int in the case of my main. That is what I am trying anyway.

This post has been edited by jayburn00: 25 March 2013 - 01:08 PM

Was This Post Helpful? 0
  • +
  • -

#14 jimblumberg  Icon User is offline

  • member icon


Reputation: 4003
  • View blog
  • Posts: 12,351
  • Joined: 25-December 09

Re: Problem with linked list class

Posted 25 March 2013 - 01:25 PM

In the following snippet:
template<class T>
class SortedList
{
	public:

	SortedList():head(NULL), tail(NULL), current(NULL), count(0)
	{
		head = new Node<Obj>;
		tail = new Node<Obj>;

Look closely at your class definition, what "generic type" is this class using? Hint: It's not "Obj".

Jim
Was This Post Helpful? 0
  • +
  • -

#15 jayburn00  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 118
  • Joined: 05-July 12

Re: Problem with linked list class

Posted 25 March 2013 - 01:28 PM

T? Do I replace all the Obj with T? Or replace all the T with Obj? Or replace some of the main, or somehow change main?

This post has been edited by jayburn00: 25 March 2013 - 01:30 PM

Was This Post Helpful? 0
  • +
  • -

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »