Hello,

I am trying to write a templated linked list, and I am having some difficulties with the add() function. It seems like different behavior occurs depending on how I add to my list, but my two test cases don't seem that different to me. I'll post the list.h, and main.cpp. I snipped a bunch of code out of list.h that didn't seem relevant. Also, if you need to see the "position" class, just let me know (just trying to keep the code down to a minimum).

//list.h

///////////////////////////////////////////////////
// List Template
template <class Type>
class List {
			
	public:
		// Constructor
		List(): head(0), size(0) { }

		// Add an element to the list
		void add( const Type &element );

		// Returns the head of the list
		ListNode<Type>* getHead() const { return head; }

		// Returns the current size of the list
		int getListSize() const { return size; }

	private:
		ListNode<Type> 	*head;
		int				size;
	
};

//////////////////////////////////////////////////
// ListNode Template
template <class Type>
class ListNode {
	public:
		// Constructor
		ListNode( const Type &element ): data(element), next(0) { }

		// Get the node's data
		const Type getData() const { return data; }

		// Get the next node
		ListNode<Type>* getNext() const { return next; }

		// Set the next node 
		void setNext( ListNode<Type> *nextNode ) { next = nextNode; }

	private:
		const Type		&data;
		ListNode<Type>	*next;	
};

///////////////////////////////////////////////////
// '<<' Operator for the list
template <class Type> 
 ostream& operator<<( ostream &os, const List<Type> & aList) {
	ListNode<Type> *currNode;
	currNode = aList.getHead();

	while(currNode != 0){
		os << *(currNode->getData()) << endl;
		currNode = currNode->getNext();
	}
	return os;
}


//////////////////////////////////////////////////////////////////////
// Adds an element to a list. New element becomes the head of the list
template <class Type>
 void List<Type>::add(const Type &element) {
	ListNode<Type> *newNode = new ListNode<Type>(element);
	newNode->setNext(head);
	head = newNode;
	++size;
}
//main.cpp

#include <iostream>
#include "list.h"
#include "position.h"

using namespace std;

int main(){

	////////////
	//Case 1
	List<Position *> *posListA = new List<Position *>();

	posListA->add(new Position(1,1));
	posListA->add(new Position(2,2));
	posListA->add(new Position(3,3));
	
	cout << "Printing final list: \n" << *posListA << endl;

	///////////
	//Case 2
	List<Position *> *posListB = new List<Position *>();

	for(int i = 1; i < 4; i++){
		posListB->add(new Position(i,i)); 	
	}
	
	cout << "Printing final list: \n" << *posListB << endl;


	return 0;
}

And the output I'm getting:

mike@mike-Lenovo-G550:~/School/comp_2404/templateTestTwo$ ./main
Printing final list:
(3,3)
(2,2)
(1,1)

Printing final list:
(3,3)
(3,3)
(3,3)


I tried my best to debug it, but I'm still not sure why it's happening. In the second 'case', I checked the memory locations associated with each node. It seemed that each node had it's own space in memory. However, every time it the program entered the add function inside the list (around the first line), it would change all the data values to refer to the new 'element' (as in the same memory location).

My main concern/worry is that the first and second cases look identical to me with the exception of a 'for' loop, so I really don't understand why they are producing different outputs.

I'd be appreciative of any help or even reference to literature that could guide me in the right direction.

Thank you.

It looks like it's related to your definition of Position. How is it defined?

EDIT:
Oops, Narue beat me to it...

Edited 5 Years Ago by Fbody: n/a

It looks like it's related to your definition of Position. How is it defined?

EDIT:
Oops, Narue beat me to it...

// position.h
class Position
{
friend ostream &operator<<(ostream &, const Position &);

public:	
	Position(int = 0, int = 0);	// Default constructor
	Position(Position &); // Copy constructor
	~Position();	// Destructor
	
	int getXpos() const;
	int getYpos() const;
	
	int posToInt() const;	
	void setPosition(int, int);	
private:
	int 	xpos;
	int 	ypos;
};

// Comparison Operators
bool operator==(Position &, const Position &);
bool operator!=(Position &, const Position &);
#endif
//position.cpp

ostream &operator<<(ostream &output, const Position &position) {
	output << "(" << position.xpos << "," << position.ypos << ")";
	return output;
}

Position::Position(int x, int y) {	
	setPosition(x,y);
}
Position::Position(Position &posToCopy) // Copy constructor
	: xpos(posToCopy.getXpos()), ypos(posToCopy.getYpos()) { cout << "IN POSITION CCTOR" <<endl; }

Position::~Position() {}

int Position::getXpos() const { return xpos; }
int Position::getYpos() const { return ypos; }

void Position::setPosition(int x, int y) {
	xpos = x;
	ypos = y;
}

bool operator==(Position &p1, const Position &p2) {	
	return((p1.getXpos() == p2.getXpos()) && (p1.getYpos() == p2.getYpos()));
}
bool operator!=(Position &p1, const Position &p2) {
	return !(p1 == p2);
}

P.S. Thanks for replying so fast.

Hey Narue and FBody,
Thanks for giving the code a shot. I showed it to a friend of mine, and he thinks the problem had to do with the way I was combining pointers and references:

///////////
//Case 2
List<Position *> *posListB = new List<Position *>();
 
for(int i = 1; i < 4; i++){
	posListB->add(new Position(i,i)); 	
}
 
cout << "Printing final list: \n" << *posListB << endl;

Since my node constructor takes a reference, the "new Position(i,i)" is somehow put into a variable behind the scenes before it is passed to the function. So each time through the loop, the "new" is placed in that SAME variable. Each node is referencing that variable, so ta-da! I changed to just pointers, and it seems to be working.

If you guys know more details about this behaviour (or the actual details, since I probably explained it inaccurately), please let me know. I'd like to learn from this mistake, even if my code seems to be working for the time being.

Thank you for taking the time to look at my code too. I don't know how you guys are able to answer all these questions, but I am thankful that you do. So know that when I say "Thank you", I mean it sincerely. Until the next headache!
- Mike

This question has already been answered. Start a new discussion instead.