Please help with C++ linked list

[strungoutfan78]

I really need help on my latest C++ assignment. The program was due a week ago and I'm still beating my head against a wall here. This is supposed to be a VERY SIMPLE linked list implementation. I have rewritten this dang thing countless times in as many different configurations as I can think of but I just can't get it. If someone could just shine a light for me I would be forever in debt.

That being said, after countless attempts I finally decided to use the code here: http://www.cprogramming.com/tutorial/lesson15.html
to start with. It works just fine without the modifications I made. The only thing I really did was move the bulk of the traversal into the ListNode::add() function. Now it goes through and places the values of the array into curNode->value, but once I move the pointer I can't access those values again. What I end up with is a 1 and a 9 printed in the terminal, it skips all the others. I guess my question is: How do I store the curNode->value values after the add() function handles them? I thought the linked list did this. Do I need another array to store the values? Sorry, I'm so confused...

I know I'm missing something very simple here, but my brain is just so burned out on this assignment I've got tunnel vision and I just can't see the forest through the trees.

The ultimate goal here is to assign doubles to the list, traverse & print the list, and, using the function isMember() (which I have not yet implemented), determine if a particular number is a member of said linked list. Oh, and to add a copy constructor, once I get this base portion complete.

Thanks in advance.:S

#include <iostream>
using namespace std;

struct ListNode {
  double value;
  ListNode *next;
  void add( double, ListNode* );
  bool isMember( double );
};

void ListNode::add( double x, ListNode *curNode ) {
	curNode->next = new ListNode;  // Creates a ListNode at the end of the list
	curNode = curNode->next; // Points to that ListNode
	curNode->next = 0;         // Prevents it from going any further
	curNode->value = x;
}

int main() {

	const int SIZE = 5;
	double testValue[SIZE] = { 1, 3, 5, 7, 9 };
	double* tv = testValue;

	ListNode *head;       
	ListNode *curNode;  

	
	head = new ListNode;  
	head->next = 0;   
	head->value = *tv;
	curNode = head;
	if ( curNode != 0 ) {
		while ( curNode->next != 0 ) 
		curNode = curNode->next;
	}

	cout << curNode->value << endl;

	for( int i = 1; i < SIZE; i++ ) {
		curNode->add( *( tv + i ), curNode );
	}

	//CURRENTLY I CANNOT MAKE THIS BLOCK WORK CORRECTLY.  IT ONLY PRINTS THE FIRST AND LAST VALUES OF THE ARRAY
	//ListNode::add() PERFORMS ALL OPERATIONS CORRECTLY AND I CAN PRINT AS I AM ASSIGNING THE NODE VALUES
	//BUT ONCE I GET PAST THEM I CANT GET BACK THROUGHT THE LIST. IT ONLY LEAVES ME WITH THE MOST RECENT value ENTRY
	//??????????????????????????????????????????????????????????????????????????????????????????????????????????????
	//if ( curNode->value != 0 ) { //Makes sure there is a place to start
	//  while ( curNode->next != 0 ) {
	//	cout<< curNode->value << endl;
	//	curNode = curNode->next;
	//  }
	//  cout<< curNode->value << endl;;
	//}

	return 0;
}

[Topi Ojala]

First off, you shouldn't implement functionality in a struct. Call it a class if you want functions, besides construct/destructor.

The problem is with the add function. You always add a new node behind the head-node (line 40), you don't swap the curNode-variable to the new added node. You have one curNode-variable inside the struct and one in your main-function. Changing the curNode-variable to next node inside the struct namespace doesn't affect the variable in your main-function.

[thomas_naveen]

Use the following function

void ListNode::add( double x, ListNode **curNode )

use

(*curNode)

in the above function wherever you are using curNode

Use

curNode->add( *( tv + i ), &curNode );

at line 40.

Use

curNode = head;

at line 42 to reinitialize your curNode to the head pointer.

[strungoutfan78]

First off, you shouldn't implement functionality in a struct. Call it a class if you want functions, besides construct/destructor.

The problem is with the add function. You always add a new node behind the head-node (line 40), you don't swap the curNode-variable to the new added node. You have one curNode-variable inside the struct and one in your main-function. Changing the curNode-variable to next node inside the struct namespace doesn't affect the variable in your main-function.

OK so what, I guess, is the new added node here in my code then? I thought that the statement:

curNode = curNode->next;

moved the pointer to the next placeholder, ready to store a new value. Am I missing something here?

@thomas_naveen
I implemented the changes you suggested. You can see the new code down below. I changed the struct to a class (made everything public for now, just for simplicity for the time being). I understand the need to change to **curNode in the function call, so I have a pointer to my pointer. That makes sense to me. What I don't understand now is why it has effectively changed nothing in my end result. Still just getting 1 and 9 in my output.

Sorry for being dim, I'm new to this and for some reason ListNodes just seem very abstract to me. Thanks for your help.

#include <iostream>

using namespace std;



class ListNode {

public:

  double value;

  ListNode *next;

  void add( double, ListNode** );

  bool isMember( double );

};



void ListNode::add( double x, ListNode **curNode ) {

	(*curNode)->next = new ListNode;  // Creates a ListNode at the end of the list

	(*curNode) = (*curNode)->next; // Points to that ListNode

	(*curNode)->next = 0;         // Prevents it from going any further

	(*curNode)->value = x;

	//cout << (*curNode)->value << endl;

}



int main() {



	const int SIZE = 5;

	double testValue[SIZE] = { 1, 3, 5, 7, 9 };

	double* tv = testValue;



	ListNode *head;       

	ListNode *curNode;  



	

	head = new ListNode;  

	head->next = 0;   

	head->value = *tv;

	curNode = head;

	if ( curNode != 0 ) {

		while ( curNode->next != 0 ) 

		curNode = curNode->next;

	}



	for( int i = 1; i < SIZE; i++ ) {

		curNode->add( *( tv + i ), &curNode );

		curNode = head;

	}



	
	if ( curNode->value != 0 ) { //Makes sure there is a place to start

	  while ( curNode->next != 0 ) {

		cout<< curNode->value << endl;

		curNode = curNode->next;

	  }

	  cout<< curNode->value << endl;;

	}



	return 0;

}

[Topi Ojala]

Okay, I think I can explain it now!

A linked list consists of multiple nodes. One ListNode ( in a traditional linked list ) contains a value ( in your case a double ) and a pointer to ONE NEXT NODE. For a single ListNode there is only one next node.

Your logic of adding an add function to a single node is a bit off. You can not logically add multiple new node elements in to a single node. This is what you are trying to do in your for-loop in lines 77-83.

So in brief:
- ListNode contains a double and a pointer to next ListNode.
- You can create the new next node inside the ListNode if you want, but you should only call the function if you know it's the last node in your linked list so the next-pointer doesnt get overwritten.
- You can move your node indexpointer curNode in your list with a while loop, accessing next nodes starting from the head node. ( like you have done in lines 69-71: you move the curNode-pointer to the last element in the list )

[img]https://wiki.cs.auckland.ac.nz/compsci105ss/images/8/8c/Tail-linked-list.PNG[/img]

[rubberman]

This may be a bit better (warning! untested code!)

#include <iostream>
 
using namespace std;
 
class ListNode {
 
public:
 
  double value;
  ListNode *next;
 
  ListNode* add( double );
 
  bool isMember( double );

};

// Add new member and return a pointer to it. 
ListNode* ListNode::add( double x )
{
    ListNode* newNode = new ListNode;  // Creates a new ListNode
    ListNode* pNext = 0;

    newNode->value = x; // Set value and clear next
    newNode->next = 0;

    // Seek end of list if this node is not there.
    for (pNext = this; pNext->next != 0; pNext = next)
    {
        // This loop only seeks to end of list.
    }
    pNext->next = newNode; // Now, link new element to end of list.
    return newNode;  // Finally, return new end node.
}
 
int main(void)
{
    const int SIZE = 5;

    double testValue[SIZE] = { 1, 3, 5, 7, 9 };

    ListNode *head;
    ListNode *curNode;

    head = new ListNode;  
    head->next = 0;
    head->value = testValue[0];
    curNode = head;

    for( int i = 1; i < SIZE; i++ )
    {
        curNode = curNode->add( testValue[i] );
    }

    // Walk the list, and print the values.
    for (curNode = head; curNode != 0; curNode = curNode->next)
    {
        cout<< curNode->value << endl;
    }
    return 0;
}

Just remember the KISS principle! :-)

[strungoutfan78]

@Topi Ojala:
Thank you for the explanation in laymen's terms. The documentation and textbooks I have read regarding linked lists are so technical it makes my head hurt. I'm just driving the car. I don't need to know what's under the hood... yet.

@rubberman:
That code does exactly what I was trying to do. The only difference, however, is that the textbook this challenge has come from requests three specific items:

1. A member function named "void add(double x)"
2. a function named "bool isMember(double x)"
3. and a default constructor "LinkedList( )"

I should have mentioned that before. I like what you did with the add function but it doesn't fit the criteria I've been given. That's another thing that's giving me a headache: trying to fit the lousy criteria the textbook is giving me. I can't figure out how to accomplish what I need to accomplish with a "void add(double)" function. Also, every time that add function is called it is returning a new node named newNode. So I end up with multiple instance of newNode, all with a different value? I'm not totally understanding the logic there. And in the for loop in ListNode::add, what exactly is the assignment of pNext = this doing? I'm familiar with using this for objects, like this->value and so on, but not the way it's being used there.

[rubberman]

Well, the hard part is done. bool isMember(double x) should just iterate over the list from head to tail (we did that when printing the values). So, just call "head->isMember(x)", and isMember() will iterate, comparing each member's value with x. The default constructor only needs to set next and value to 0, which we were doing directly. So, once you have the initializers in the constructor fixed, you can leave off the default initialization that we were doing, such as

ListNode *newNode = new ListNode;

With the appropriate default constructor, you won't have to do this:

newNode->next = 0;
newNode->value = 0;

So, consider that your part of this exercise! :-)
Post your code here when done and we'll make some sarcastic comments about it... :-)

[thomas_naveen]

OK so what, I guess, is the new added node here in my code then? I thought that the statement:

curNode = curNode->next;

moved the pointer to the next placeholder, ready to store a new value. Am I missing something here?

@thomas_naveen
I implemented the changes you suggested. You can see the new code down below. I changed the struct to a class (made everything public for now, just for simplicity for the time being). I understand the need to change to **curNode in the function call, so I have a pointer to my pointer. That makes sense to me. What I don't understand now is why it has effectively changed nothing in my end result. Still just getting 1 and 9 in my output.

Sorry for being dim, I'm new to this and for some reason ListNodes just seem very abstract to me. Thanks for your help.

#include <iostream>

using namespace std;



class ListNode {

public:

  double value;

  ListNode *next;

  void add( double, ListNode** );

  bool isMember( double );

};



void ListNode::add( double x, ListNode **curNode ) {

	(*curNode)->next = new ListNode;  // Creates a ListNode at the end of the list

	(*curNode) = (*curNode)->next; // Points to that ListNode

	(*curNode)->next = 0;         // Prevents it from going any further

	(*curNode)->value = x;

	//cout << (*curNode)->value << endl;

}



int main() {



	const int SIZE = 5;

	double testValue[SIZE] = { 1, 3, 5, 7, 9 };

	double* tv = testValue;



	ListNode *head;       

	ListNode *curNode;  



	

	head = new ListNode;  

	head->next = 0;   

	head->value = *tv;

	curNode = head;

	if ( curNode != 0 ) {

		while ( curNode->next != 0 ) 

		curNode = curNode->next;

	}



	for( int i = 1; i < SIZE; i++ ) {

		curNode->add( *( tv + i ), &curNode );

		
	}


          curNode = head;

	
	if ( curNode->value != 0 ) { //Makes sure there is a place to start

	  while ( curNode->next != 0 ) {

		cout<< curNode->value << endl;

		curNode = curNode->next;

	  }

	  cout<< curNode->value << endl;;

	}



	return 0;

}

Try the above corrected code. You will have to expand the quoted text to see the code.

[strungoutfan78]

Been out of comission due to nasty cold. I'll get back on this as soon as I'm functioning again. Thanks for the help.

[strungoutfan78]

OK, so I'm back in action (sort of). This cold is really nasty. Anyway, thanks for everyone's assistance with this. I've been pouring over this code and I think I get it finally. Below is what I've assembled to achieve the results I'm looking for. I'm sure the code could be cleaned up a great deal, and I should probably move a lot of the stuff from the do-while loop to the isMember() function, but I'm pressed for time ( about 6 more challenges to submit by Monday ), so my instructor may just have to settle for the quick, dirty version. :icon_neutral:
Always open to criticism and/or

some sarcastic comments about it... :-)

:P

#include <iostream>
using namespace std;

class ListNode {
public:
  double value;
  ListNode *next;

  void add( double, ListNode** );

  bool isMember( double, double );
};

void ListNode::add( double x, ListNode **curNode ) {
	(*curNode)->next = new ListNode;  // Creates a ListNode at the end of the list
	(*curNode) = (*curNode)->next; // Points to that ListNode
	(*curNode)->next = 0;         // Prevents it from going any further
	(*curNode)->value = x;
}

bool ListNode::isMember( double tv, double y ) {
		if( tv == y )
			return true;
		else
			return false;
}

int main() {
	const int SIZE = 5;
	double testValue[SIZE] = { 1, 3, 5, 7, 9 };
	double* tv = testValue;
	double userInput;
	char again;
	bool loop = true;

	ListNode *head;       
	ListNode *curNode;  

	head = new ListNode;  
	head->next = 0;   
	head->value = *tv;

	curNode = head;

	if ( curNode != 0 ) {
		while ( curNode->next != 0 ) 
			curNode = curNode->next;
	}

	for( int i = 1; i < SIZE; i++ ) {
		curNode->add( *( tv + i ), &curNode );
	}

	curNode = head;
	
	if ( curNode->value != 0 ) { //Makes sure there is a place to start
	  while ( curNode->next != 0 ) {
		cout << curNode->value << endl;
		curNode = curNode->next;
	  }
	  cout<< curNode->value << endl;
	}

	do {
		cout << "Enter a number to check if it is a member of this linked list: ";
		cin >> userInput;

		curNode = head;
	
		for( int i = 0; i < SIZE; i++ ) {
			if( curNode->isMember( *( tv + i ), userInput ) ) {
				cout << userInput << " is a member." << endl;
				break;
			}
			else if ( !curNode->isMember( *( tv + i ), userInput ) ) {
				if( curNode->next != 0 ) {
					curNode = curNode->next;
					continue;
				}
				else
					cout << userInput << " is not a member." << endl;
			}
		}

		cout << "again? (y/n): ";
		cin >> again;
		if( again == 'y' || again == 'Y' )
			loop = true;
		else if ( again == 'n' || again == 'N' )
			loop = false;

	}while( loop );

	return 0;
}

[strungoutfan78]

Also, just for S&G's, if I were to include a constructor, what would I pass to it? I'm not too sure.

[Nick Evan]

One of the more obvious things I spot is that you allocate memory with new , but you newer delete it. == memory-leak

[strungoutfan78]

Good point. I shall fix that. I know I should have a deconstructor in there too.

[packetpirate]

Since you seem to have figured it out, take a look at the header file I'm working on.
It isn't, by any means, complete, but it should help you a little bit to understand how it should be structured.

/**
* This header file was designed to make creation and modification of linked lists easier.
* Author - packetpirate
* Last Update - 05/18/2011  11:19 PM
**/

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
using std::cout;
using std::endl;

// Begin linklist namespace.
namespace linklist
{
	// Begin node structure.
	template< typename T >
	struct node {
		T data; // Contains data of specified type.
		node<T> *link; // Contains link to next node. NULL if this node is last in the list.
	};
	// End node structure.

	// Begin LinkedList class declaration.
	template< typename T >
	class LinkedList {
		public:
			LinkedList(); // Creates a new blank list.
			LinkedList(node<T> *start); // Creates a new list with a specified first node.
			~LinkedList();

			// Functions for appending the list.
			void add(node<T> *next); // Adds a node to the list.
			void add(T nextData); // Adds a new node to the list.

			// Get and Set functions for the list.
			T get(int pos);
			void set(int pos, T newData);

			// Size-based functions.
			int length();
			bool isEmpty();

			// Position-based functions.
			T begin(); // Returns the data of the first node in the list.
			T end(); // Returns the data of the last node in the list.

			// Sort function/s.
			void sort(bool asc);
			void swap(node<T> *i, node<T> *j);

			// Print functions.
			void printList();
			void printElem(int pos);
		private:
			node<T> *first; // The first node in the list.
			node<T> *last; // The last node in the list.
			int size; // Size of the list.
	};
	// End LinkedList class declaration.

	// Begin LinkedList class definitions.
	// Begin Constructors & Destructors
	template< typename T >
	LinkedList<T>::LinkedList() {
		first = NULL;
		last = NULL;
		size = 0;
	}
	template< typename T >
	LinkedList<T>::LinkedList(node<T> *start) {
		first = start;
		last = start;
		size = 1;
	}
	template< typename T >
	LinkedList<T>::~LinkedList() {

	}
	// End Constructors & Destructors

	// Begin list modifying functions.
	template< typename T >
	void LinkedList<T>::add(node<T> *next) {
		if(first == NULL) {
			first = next;
			last = next;
			size++;
		} else {
			last->link = next;
			last = next;
			last->link = NULL;
			size++;
		}
	}
	template< typename T >
	void LinkedList<T>::add(T nextData) {
		node<T> *next = new node<T>;
		next->data = nextData;
		next->link = NULL;
		
		if(first == NULL) {
			first = next;
			last = next;
			size++;
		} else {
			last->link = next;
			last = next;
			last->link = NULL;
			size++;
		}
	}
	// End list modifying functions.

	// Begin get/set functions.
	template< typename T >
	T LinkedList<T>::get(int pos) {
		if(pos > size) {
			cout << "That position is out of bounds." << endl;
		} else {
			int i = 0;
			node<T> *current;

			for(current = first;current != NULL;current = current->link) {
				if(i == pos) {
					return current->data;
				}
				i++;
			}
		}
		return 0;
	}
	template< typename T >
	void LinkedList<T>::set(int pos, T newData) {
		if(pos > size) {
			cout << "That position is out of bounds." << endl;
		} else {
			int i = 0;
			node<T> *current;

			for(current = first;current != NULL;current = current->link) {
				if(i == pos) {
					current->data = newData;
				}
				i++;
			}
		}
	}
	// End get/set functions.

	// Begin size-based functions.
	template< typename T >
	int LinkedList<T>::length() {
		return size;
	}
	template< typename T >
	bool LinkedList<T>::isEmpty() {
		return (first == NULL);
	}
	// End size-based functions.

	// Begin position-based functions.
	template< typename T >
	T LinkedList<T>::begin() {
		if(!isEmpty()) {
			return first->data;
		} else {
			return NULL;
		}
	}
	template< typename T >
	T LinkedList<T>::end() {
		if(!isEmpty()) {
			return last->data;
		} else {
			return NULL;
		}
	}
	// End position-based functions.

	// Begin sort function/s.
	template< typename T >
	void LinkedList<T>::sort(bool asc) {
		if(!isEmpty()) {
			node<T> *i;
			node<T> *j;

			for(i = first;i != NULL;i = i->link) {
				for(j = i->link;j != NULL;j = j->link) {
					if(asc) {
						if(j->data < i->data) {
							swap(i, j);
						}
					} else {
						if(j->data > i->data) {
							swap(i,j);
						}
					}
				}
			}
		}
	}
	template< typename T >
	void LinkedList<T>::swap(node<T> *i, node<T> *j) {
		T tempData = i->data;
		i->data = j->data;
		j->data = tempData;
	}
	// End sort function/s.

	// Begin print functions.
	template< typename T >
	void LinkedList<T>::printList() {
		if(!isEmpty()) {
			node<T> *current;

			for(current = first;current != NULL;current = current->link) {
				cout << current->data << " ";
			}
			cout << endl;
		} else {
			cout << "The list is empty." << endl;
		}
	}
	template< typename T >
	void LinkedList<T>::printElem(int pos) {
		if(pos > size) {
			cout << "That position is out of bounds." << endl;
		} else {
			int i = 0;
			node<T> *current;

			for(current = first;current != NULL;current = current->link) {
				if(i == pos) {
					cout << current->data << endl;
					break;
				}
				i++;
			}
		}
	}
	// End print functions.
	// End LinkedList class definitions.
}
// End linklist namespace.

#endif

[strungoutfan78]

Since you seem to have figured it out, take a look at the header file I'm working on.
It isn't, by any means, complete, but it should help you a little bit to understand how it should be structured.

/**
* This header file was designed to make creation and modification of linked lists easier.
* Author - packetpirate
* Last Update - 05/18/2011  11:19 PM
**/

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
using std::cout;
using std::endl;

// Begin linklist namespace.
namespace linklist
{
	// Begin node structure.
	template< typename T >
	struct node {
		T data; // Contains data of specified type.
		node<T> *link; // Contains link to next node. NULL if this node is last in the list.
	};
	// End node structure.

	// Begin LinkedList class declaration.
	template< typename T >
	class LinkedList {
		public:
			LinkedList(); // Creates a new blank list.
			LinkedList(node<T> *start); // Creates a new list with a specified first node.
			~LinkedList();

			// Functions for appending the list.
			void add(node<T> *next); // Adds a node to the list.
			void add(T nextData); // Adds a new node to the list.

			// Get and Set functions for the list.
			T get(int pos);
			void set(int pos, T newData);

			// Size-based functions.
			int length();
			bool isEmpty();

			// Position-based functions.
			T begin(); // Returns the data of the first node in the list.
			T end(); // Returns the data of the last node in the list.

			// Sort function/s.
			void sort(bool asc);
			void swap(node<T> *i, node<T> *j);

			// Print functions.
			void printList();
			void printElem(int pos);
		private:
			node<T> *first; // The first node in the list.
			node<T> *last; // The last node in the list.
			int size; // Size of the list.
	};
	// End LinkedList class declaration.

	// Begin LinkedList class definitions.
	// Begin Constructors & Destructors
	template< typename T >
	LinkedList<T>::LinkedList() {
		first = NULL;
		last = NULL;
		size = 0;
	}
	template< typename T >
	LinkedList<T>::LinkedList(node<T> *start) {
		first = start;
		last = start;
		size = 1;
	}
	template< typename T >
	LinkedList<T>::~LinkedList() {

	}
	// End Constructors & Destructors

	// Begin list modifying functions.
	template< typename T >
	void LinkedList<T>::add(node<T> *next) {
		if(first == NULL) {
			first = next;
			last = next;
			size++;
		} else {
			last->link = next;
			last = next;
			last->link = NULL;
			size++;
		}
	}
	template< typename T >
	void LinkedList<T>::add(T nextData) {
		node<T> *next = new node<T>;
		next->data = nextData;
		next->link = NULL;
		
		if(first == NULL) {
			first = next;
			last = next;
			size++;
		} else {
			last->link = next;
			last = next;
			last->link = NULL;
			size++;
		}
	}
	// End list modifying functions.

	// Begin get/set functions.
	template< typename T >
	T LinkedList<T>::get(int pos) {
		if(pos > size) {
			cout << "That position is out of bounds." << endl;
		} else {
			int i = 0;
			node<T> *current;

			for(current = first;current != NULL;current = current->link) {
				if(i == pos) {
					return current->data;
				}
				i++;
			}
		}
		return 0;
	}
	template< typename T >
	void LinkedList<T>::set(int pos, T newData) {
		if(pos > size) {
			cout << "That position is out of bounds." << endl;
		} else {
			int i = 0;
			node<T> *current;

			for(current = first;current != NULL;current = current->link) {
				if(i == pos) {
					current->data = newData;
				}
				i++;
			}
		}
	}
	// End get/set functions.

	// Begin size-based functions.
	template< typename T >
	int LinkedList<T>::length() {
		return size;
	}
	template< typename T >
	bool LinkedList<T>::isEmpty() {
		return (first == NULL);
	}
	// End size-based functions.

	// Begin position-based functions.
	template< typename T >
	T LinkedList<T>::begin() {
		if(!isEmpty()) {
			return first->data;
		} else {
			return NULL;
		}
	}
	template< typename T >
	T LinkedList<T>::end() {
		if(!isEmpty()) {
			return last->data;
		} else {
			return NULL;
		}
	}
	// End position-based functions.

	// Begin sort function/s.
	template< typename T >
	void LinkedList<T>::sort(bool asc) {
		if(!isEmpty()) {
			node<T> *i;
			node<T> *j;

			for(i = first;i != NULL;i = i->link) {
				for(j = i->link;j != NULL;j = j->link) {
					if(asc) {
						if(j->data < i->data) {
							swap(i, j);
						}
					} else {
						if(j->data > i->data) {
							swap(i,j);
						}
					}
				}
			}
		}
	}
	template< typename T >
	void LinkedList<T>::swap(node<T> *i, node<T> *j) {
		T tempData = i->data;
		i->data = j->data;
		j->data = tempData;
	}
	// End sort function/s.

	// Begin print functions.
	template< typename T >
	void LinkedList<T>::printList() {
		if(!isEmpty()) {
			node<T> *current;

			for(current = first;current != NULL;current = current->link) {
				cout << current->data << " ";
			}
			cout << endl;
		} else {
			cout << "The list is empty." << endl;
		}
	}
	template< typename T >
	void LinkedList<T>::printElem(int pos) {
		if(pos > size) {
			cout << "That position is out of bounds." << endl;
		} else {
			int i = 0;
			node<T> *current;

			for(current = first;current != NULL;current = current->link) {
				if(i == pos) {
					cout << current->data << endl;
					break;
				}
				i++;
			}
		}
	}
	// End print functions.
	// End LinkedList class definitions.
}
// End linklist namespace.

#endif

The first thing that hits me is these two lines:

using std::cout;
using std::endl;

What exactly is that doing? I know when using namespace std it's making it so that I don't have to include "std::" attached to everything, but I'm not really sure what this is doing. Is it kind of like using namespace std, but rather just those specific objects instead of the entire namespace?

[packetpirate]

Why would you use the entire namespace? It's not needed. I only needed two things from <iostream>.

[packetpirate]

using std::cout is like using namespace std;, except that instead of the entire namespace, you're just including cout.

[raptr_dflo]

hey strungoutfan78,

Despite all the intervening help, I think your original add() function was fine as written, and all you needed to do is, after calling "curNode->add( *( tv + i ), curNode );" (originally at line 40), to advance curNode:

curNode->add( *( tv + i ), curNode );
    curNode = curNode->next;

so that the add after that would be adding to the -new- end of the list. Also, since "add" is a method ("member function") of ListNode (and a struct in C++ is just a class where the data members are public by default), implicit variable "this" is a pointer to the ListNode instance in question. So you don't need to pass curNode, and change add to read:

void ListNode::add( double x ) {
    this->next = new ListNode; // Creates a ListNode at the end of the list
    this = this->next; // Points to that ListNode
    this->next = 0; // Prevents it from going any further
    this->value = x;
}

The only usefully-variable part of a ListNode is the value, so that's sufficient to pass in a constructor:

ListNode::ListNode( double val ) {
    this->value = val;
    this->next = 0;
}

Since nothing is dynamically allocated -within- a ListNode, it doesn't need a destructor, you just need to delete any nodes you new.

[strungoutfan78]

hey strungoutfan78,

Despite all the intervening help, I think your original add() function was fine as written, and all you needed to do is, after calling "curNode->add( *( tv + i ), curNode );" (originally at line 40), to advance curNode:

curNode->add( *( tv + i ), curNode );
    curNode = curNode->next;

so that the add after that would be adding to the -new- end of the list. Also, since "add" is a method ("member function") of ListNode (and a struct in C++ is just a class where the data members are public by default), implicit variable "this" is a pointer to the ListNode instance in question. So you don't need to pass curNode, and change add to read:

void ListNode::add( double x ) {
    this->next = new ListNode; // Creates a ListNode at the end of the list
    this = this->next; // Points to that ListNode
    this->next = 0; // Prevents it from going any further
    this->value = x;
}

The only usefully-variable part of a ListNode is the value, so that's sufficient to pass in a constructor:

ListNode::ListNode( double val ) {
    this->value = val;
    this->next = 0;
}

Since nothing is dynamically allocated -within- a ListNode, it doesn't need a destructor, you just need to delete any nodes you new.

OK that makes sense. I couldn't really figure out how I was supposed to do that with a destructor. God, that constructor is so simple. That really is all I need to do. I tend to make things like this so much more complicated in my mind than they need to be. Thank you.

@packetpirate:
yeah that's what I thought. I've just never seen it before. It does seem overkill to include the entire namespace, but is there a substantial degradation in performance by including the entire namespace if unneccessary? seems like it's just easier to include the whole thing and forget about it. but I'm new to this so I don't know a lot of these things.

[packetpirate]

It won't affect performance unless it's a really large program, but I'm writing this header file to be as efficient as I can. And besides, it's good practice to include only what you're using. If you REALLY wanted to increase performance, you could include only certain parts of the namespace in the scope of the functions you're using the members in.

[strungoutfan78]

OK so here's the latest. I've added a basic constructor and copy constructor and deleted any new's. Everything seems to work OK. Now just have to move all the display stuff to a display() function, so as to avoid the double do-while loop, and that will meet all the requirements for this assignment, but the more feedback the better. I'll try to clean this up once I get the rest of my assignments finished.

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

class ListNode {
public:
	double value;
	ListNode *next;

	void add( double, ListNode** );

	bool isMember( double, double );

	// constructor
	ListNode( double x ) {
		this->value = x;
		this->next = 0;
	}//end constructor

	// copy constructor
	ListNode( ListNode& LN ) {
		this->value = LN.value;
		this->next = 0;
	}// end copy constructor

};

// member function to add values to the current list
void ListNode::add( double x, ListNode **curNode ) {
	(*curNode)->next = new ListNode( x );  // Creates a ListNode at the end of the list
	(*curNode) = (*curNode)->next; // Points to that ListNode
}// end function add

//member function to determine if user input value is a member of current list
bool ListNode::isMember( double tv, double y ) {
		if( tv == y )
			return true;
		else
			return false;
}// end function isMember

int main() {
	const int SIZE = 5;
	double testValue[SIZE] = { 1, 3, 5, 7, 9 };
	double* tv = testValue;
	double userInput;
	char again;
	bool loop = true;

	ListNode *head;       
	ListNode *curNode;  

	head = new ListNode( *tv );  

	curNode = head;

	if ( curNode != 0 ) {
		while ( curNode->next != 0 ) 
			curNode = curNode->next;
	}

	for( int i = 1; i < SIZE; i++ ) {
		curNode->add( *( tv + i ), &curNode );
	}

	curNode = head;
	cout << "Original values:" << endl;
	if ( curNode->value != 0 ) { //Makes sure there is a place to start
	  while ( curNode->next != 0 ) {
		   cout << curNode->value << endl;
		   curNode = curNode->next;
	  }
	  cout<< curNode->value << endl;
	}


	//Display original constructor values
	do {
		cout << "Enter a number to check if it is a member of this linked list: ";
		cin >> userInput;

		curNode = head;
	
		for( int i = 0; i < SIZE; i++ ) {
			if( curNode->isMember( *( tv + i ), userInput ) ) {
				cout << userInput << " is a member." << endl;
				break;
			}
			else if ( !curNode->isMember( *( tv + i ), userInput ) ) {
				if( curNode->next != 0 ) {
					curNode = curNode->next;
					continue;
				}
				else
					cout << userInput << " is not a member." << endl;
			}
		}

		cout << "again? (y/n): ";
		cin >> again;
		if( again == 'y' || again == 'Y' )
			loop = true;
		else if ( again == 'n' || again == 'N' )
			loop = false;

	}while( loop );//end original constructor

	// create new copy constructor object
	ListNode *myCopy( curNode );
	// end new copy constructor object

	// reset place for sorting & print copied values
	myCopy = head;
	cout << "These are the values of the copy constructor:" << endl;
	if ( myCopy->value != 0 ) { //Makes sure there is a place to start
	  while ( myCopy->next != 0 ) {
		cout << myCopy->value << endl;
		myCopy = myCopy->next;
	  }
	  cout<< myCopy->value << endl;
	}// end place setting & printing

	//search copy constructor values
	do {
		cout << "Enter a number to check if it is a member of this linked list: ";
		cin >> userInput;

		myCopy = head;
	
		for( int i = 0; i < SIZE; i++ ) {
			if( myCopy->isMember( *( tv + i ), userInput ) ) {
				cout << userInput << " is a member." << endl;
				break;
			}
			else if ( !myCopy->isMember( *( tv + i ), userInput ) ) {
				if( myCopy->next != 0 ) {
					myCopy = myCopy->next;
					continue;
				}
				else
					cout << userInput << " is not a member." << endl;
			}
		}

		cout << "again? (y/n): ";
		cin >> again;
		if( again == 'y' || again == 'Y' )
			loop = true;
		else if ( again == 'n' || again == 'N' )
			loop = false;

	}while( loop );//end original constructor

	delete [] head;
	head = 0;

	return 0;
}

@packetpirate:
really well organized header file. Templates are still very foreign to me, but I think I get the basic concept. I really need to work on better comments in my files. I notice really good coders almost have more lines of comments than actual code. I've also rid the file of the "using namespace std". Thanks for that.

You'll have to excuse the poor formatting. I'm cutting and pasting from a virtual machine and it's losing something in translation. My file does not look like this.

[packetpirate]

Templates are really simple. The gist of it is that a template identifier can stand in for any data type. Here's a simple example with comments:

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

template< typename T > // T is an identifier for the specified data type.
struct test {
    T data;
};

int main(int argc, char** argv) {
    test<int> *myData; // The data field within this test struct becomes an integer...
    cout << "Enter an integer: ";
    cin >> myData->data; // Enters the input into the data field.
    cout << "You input: " << myData->data << endl; // Prints the data field.

    return 0;
}

You may have noticed that the vector class has the <> after the word vector when you create a new vector. That's because vectors are templates. I'm pretty sure a vector is just a linked list, also.

[strungoutfan78]

Templates are really simple. The gist of it is that a template identifier can stand in for any data type. Here's a simple example with comments:

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

template< typename T > // T is an identifier for the specified data type.
struct test {
    T data;
};

int main(int argc, char** argv) {
    test<int> *myData; // The data field within this test struct becomes an integer...
    cout << "Enter an integer: ";
    cin >> myData->data; // Enters the input into the data field.
    cout << "You input: " << myData->data << endl; // Prints the data field.

    return 0;
}

You may have noticed that the vector class has the <> after the word vector when you create a new vector. That's because vectors are templates. I'm pretty sure a vector is just a linked list, also.

That's a good explanation. Thanks for that. I get the principle, I guess, it's just learning when and how to implement this stuff that I have a hard time with. That'll come though, I'm sure.

[strungoutfan78]

OK so here is the last version I'm gonna post for a while until I get the rest of my work done. I'll revisit it sometime soon, but for now please criticize it.

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

class ListNode {
public:
	double value;
	double userInput;

	double* tv;
	ListNode *next;

	void add( double, ListNode** );

	bool isMember( double, double );

	void print( ListNode*, ListNode*, const int&, const double* );

	// constructor
	ListNode( double x ) {
		this->value = x;
		this->next = 0;
	}//end constructor

	// copy constructor
	ListNode( ListNode& LN ) {
		this->value = LN.value;
		this->next = 0;
	}// end copy constructor


};

// member function to add values to the current list
void ListNode::add( double x, ListNode **curNode ) {
	(*curNode)->next = new ListNode( x );  // Creates a ListNode at the end of the list
	(*curNode) = (*curNode)->next; // Points to that ListNode
}// end function add

//member function to determine if user input value is a member of current list
bool ListNode::isMember( double tv, double y ) {
		if( tv == y )
			return true;
		else
			return false;
}// end function isMember

// member function to display output
void ListNode::print( ListNode *list, ListNode *head, const int &SIZE, const double* tv ) {
	bool loop = true;
	char again;
	do {
		cout << "Enter a number to check if it is a member of this linked list: ";
		cin >> this->userInput;

		list = head;
	
		for( int i = 0; i < SIZE; i++ ) {
			if( list->isMember( *( tv + i ), this->userInput ) ) {
				cout << this->userInput << " is a member." << endl;
				break;
			}
			else if ( !list->isMember( *( tv + i ), this->userInput ) ) {
				if( list->next != 0 ) {
					list = list->next;
					continue;
				}
				else
					cout << this->userInput << " is not a member." << endl;
			}
		}

		cout << "again? (y/n): ";
		cin >> again;
		if( again == 'y' || again == 'Y' )
			loop = true;
		else if ( again == 'n' || again == 'N' )
			loop = false;

	}while( loop );//end original constructor
}//end member function print()

int main() {
	const int SIZE = 5;
	const double testValue[SIZE] = { 1, 3, 5, 7, 9 };
	const double* tv = testValue;

	ListNode *head;       
	ListNode *curNode;  

	head = new ListNode( *tv );  

	curNode = head;

	if ( curNode != 0 ) {
		while ( curNode->next != 0 ) 
			curNode = curNode->next;
	}

	for( int i = 1; i < SIZE; i++ ) {
		curNode->add( *( tv + i ), &curNode );
	}

	curNode = head;
	cout << "Original values:" << endl;
	if ( curNode->value != 0 ) { //Makes sure there is a place to start
	  while ( curNode->next != 0 ) {
		cout << curNode->value << endl;
		curNode = curNode->next;
	  }
	  cout<< curNode->value << endl;
	}

	// call print() function to display output
	curNode->print( curNode, head, SIZE, tv );
	

	// create new copy constructor object
	ListNode *myCopy( curNode );
	// end new copy constructor object

	// reset place for sorting & print copied values
	myCopy = head;
	cout << "These are the values of the copy constructor:" << endl;
	if ( myCopy->value != 0 ) { //Makes sure there is a place to start
		while ( myCopy->next != 0 ) {
			cout << myCopy->value << endl;
			myCopy = myCopy->next;
		}
		cout<< myCopy->value << endl;
	}
	myCopy->print( myCopy, head, SIZE, tv );// end place setting & printing

	

	delete [] head;
	head = 0;

	return 0;
}

[raptr_dflo]

I've been thinking a bit about "big picture" here, and one of the difficulties stems from poor object-oriented analysis. Basically, add(), isMember() and print() are funtions of the list, not of an individual ListNode. You still need the node class/structure you already have, to store a value in it and to hook them together with the "next" pointer.

I'd recommend creating a new List class that includes the "head" pointer (NULL until the first value is added), and the three basic member functions asked for. Then you can initialize the list by calling list.add(value) with successive values, list.isMember(value) to look through the nodes to see if the value appears anywhere, and list.print() to go through the nodes in order, and print out the values.

Then the main() can do things like ask the user for values to add to the list, ask for a value to search for, and so on.

Starting at line 119 of your main(), I have no idea what you're doing with your copy-constructor. You use it to create a new node "myCopy" from the current node pointed to by "curNode", then you immediately lose the new node you just created (and leak memory in the process, since now -nothing- points to that new node, it's just stranded out there) by reassigning myCopy to point back to "head".

Instead, it might be worth adding a copy() method to your List class, which uses the ListNode copy constructor to make a copy of each node in the current list (starting from head), hooks them together (while keeping track of the first one), and returns the pointer to the first one as a new "head" node. This could form the basis of a copy-constructor for the List class. Fun? :)

[strungoutfan78]

I've been thinking a bit about "big picture" here, and one of the difficulties stems from poor object-oriented analysis. Basically, add(), isMember() and print() are funtions of the list, not of an individual ListNode. You still need the node class/structure you already have, to store a value in it and to hook them together with the "next" pointer.

I'd recommend creating a new List class that includes the "head" pointer (NULL until the first value is added), and the three basic member functions asked for. Then you can initialize the list by calling list.add(value) with successive values, list.isMember(value) to look through the nodes to see if the value appears anywhere, and list.print() to go through the nodes in order, and print out the values.

Then the main() can do things like ask the user for values to add to the list, ask for a value to search for, and so on.

Starting at line 119 of your main(), I have no idea what you're doing with your copy-constructor. You use it to create a new node "myCopy" from the current node pointed to by "curNode", then you immediately lose the new node you just created (and leak memory in the process, since now -nothing- points to that new node, it's just stranded out there) by reassigning myCopy to point back to "head".

Instead, it might be worth adding a copy() method to your List class, which uses the ListNode copy constructor to make a copy of each node in the current list (starting from head), hooks them together (while keeping track of the first one), and returns the pointer to the first one as a new "head" node. This could form the basis of a copy-constructor for the List class. Fun? :)

Geez. Thanks for the feedback. You make a good point about poor object-oriented analysis. This whole thing, from the beginning, has just had my head tweaked sideways to the point where I can't tell up from down. I have not struggled with anything regarding C++ like I have with Linked Lists. The concept seems so simple, yet the implementation just stews me. I'll definitely eat the feedback and repost something within the next week or so. Again, thanks.