Linked List of Pointers

[Kanvas]

how do you make a node of pointer of a device? (device is just a class that i made up, i need to use pointers in LL so i can "share" one object with multiple LLs)

struct node
{
  device * devicePtr;
  node * left, * right, * next;
  node(const device * dvptr)               {
              dvptr = NULL;
              left = right = next = NULL;                          }
}

then how can i access to the pointer? such as when i do a copy constructor

const list& list::operator= (const list& aList)
{
	//if self copy, don't do anything
	if(this == &aList)
		return *this;

	//release exist memory , if there's any
	if (head)
	{
		destroyList();
	}
	//make *this a deep copy of "aList"
	if(!aList.head)
		head = NULL;
	else
	{
		//copy the first node
		head = new node(aList.head->dvptr);

		node * currSrc = aList.head->dvptr;
		node * currDes = head;

		while(currSrc)
		{
			currDes->next = new node(currSrc->dvptr);
			currDes = currDes->next;

			currSrc = currSrc->next;
		}

		currDes->next = NULL;
	}
	return *this;
}

I know that aList.head->dvptr and currSrc->dvptr are wrong but i don't know how else
Can anyone point it out for me?
Thanks

[kux]

how do you make a node of pointer of a device? (device is just a class that i made up, i need to use pointers in LL so i can "share" one object with multiple LLs)

struct node
{
  device * devicePtr;
  node * left, * right, * next;
  node(const device * dvptr)               {
              dvptr = NULL;
              left = right = next = NULL;                          }
}

then how can i access to the pointer? such as when i do a copy constructor

const list& list::operator= (const list& aList)
{
	//if self copy, don't do anything
	if(this == &aList)
		return *this;

	//release exist memory , if there's any
	if (head)
	{
		destroyList();
	}
	//make *this a deep copy of "aList"
	if(!aList.head)
		head = NULL;
	else
	{
		//copy the first node
		head = new node(aList.head->dvptr);

		node * currSrc = aList.head->dvptr;
		node * currDes = head;

		while(currSrc)
		{
			currDes->next = new node(currSrc->dvptr);
			currDes = currDes->next;

			currSrc = currSrc->next;
		}

		currDes->next = NULL;
	}
	return *this;
}

I know that aList.head->dvptr and currSrc->dvptr are wrong but i don't know how else
Can anyone point it out for me?
Thanks

there are a lot of things I don't understand in your code, or that seem wrong

struct node
{
  device * devicePtr;
  node * left, * right, * next;
  node(const device * dvptr)               {
              dvptr = NULL;
              left = right = next = NULL;                          }
}

i don't understand the node's constructor. I mean u pass to it a pointer to a device and put that pointer to NULL, why? I mean, no initzialization is done here. I think you wanted to write devicePtr = dvptr... makes more sense

//copy the first node
head = new node(aList.head->dvptr);

this doesn't look like a deep copy, I mean, it doesn't copy the devices !!, if you do it this way the new list nodes will point to the same devices as the old one and then you'll don't know what list is responsible for the object destruction. If you still want to have shared devices between two linked lists you should replace the device* with shared_ptr<device>

[Kanvas]

ahhh....that was a typo it's supposed to be

struct node
{
  device * dvptr;
  node * left, * right, * next;
  node(const device * dvptr)               
{
              dvptr = NULL;
              left = right = next = NULL;                          
}
}

Can you explain how do you use share_ptr<device> in this? I just don't want ended up with 50 copies of the same object in 50 different LLs. Also is there a way without using share_ptr? I don't think my class cover that yet.

Sorry, i'm so clueless right now

[kux]

http://www.onlamp.com/pub/a/onlamp/2006/05/04/smart-pointers.html?page=1

try reading this... it's kind of long, but it also explains the RAII idiom and a large variety of smart pointers.
If your STL version doesn't have std::tr1 you will probably have to install boost in order to have access to the shared_ptr, or you could just implement it yourself ( a trivial implementation is quite easy once you understand how a shared_ptr works: u just have to increase the reference count when you copy and assign the shared_ptr, decrease it in the destructor if count>1 or permanentrly destroy the pointed resource in the destructor if count = 1. )

[Kanvas]

http://www.onlamp.com/pub/a/onlamp/2006/05/04/smart-pointers.html?page=1

try reading this... it's kind of long, but it also explains the RAII idiom and a large variety of smart pointers.
If your STL version doesn't have std::tr1 you will probably have to install boost in order to have access to the shared_ptr, or you could just implement it yourself ( a trivial implementation is quite easy once you understand how a shared_ptr works: u just have to increase the reference count when you copy and assign the shared_ptr, decrease it in the destructor if count>1 or permanentrly destroy the pointed resource in the destructor if count = 1. )

Thanks for the hints. I kinda understand shared_ptr now but i think it's out of the scope of what i'm doing right now (a assignment for a CS class)

Can you think of any think else that allows LLs to share?

[kux]

well, this is the "good" way of doing it... of course... you could find a workarround that would kind of be based on the same principle... I'll try to make a short implementation.

[kux]

#include <iostream>
#include <algorithm>

using namespace std;

template<class T>
class myPointer
{
public:
	T* pT_;
	int *refcount_;

public:
	myPointer(): pT_(NULL), refcount_(NULL) {};
	
	myPointer ( T* objP )
	{
		pT_ = objP;
		refcount_ = new int(1);
	}
	myPointer( const myPointer& node )
	{
		pT_ = node.pT_;
		refcount_ = node.refcount_;
		*refcount_ = *refcount_ + 1;
	}

	myPointer & operator= ( const myPointer& node )
	{
		if( this != &node )
		{
			pT_ = node.pT_;
			refcount_ = node.refcount_;
			*refcount_ = *refcount_ + 1;
		}
		return *this;
	}

	~myPointer ()
	{
		if( refcount_ != NULL )
		{
			if ( *refcount_ == 1 )
			{
				delete pT_;
				delete refcount_;
			}
			else
				*refcount_ = *refcount_ - 1;		
		}
	}
};


template < class T >
class List
{
	struct Node
	{
		myPointer<T> p_;
		Node* next_;

		Node( const myPointer<T>& obj )
		{
			p_ = obj;
			next_ = NULL;
		}


	};

	Node *head_;
public:
	List( const myPointer<T>& obj )
	{
		head_ = new Node ( obj );
	}

	void addToList( const myPointer<T>& obj )
	{
		Node * newHead = new Node( obj );
		newHead->next_ = head_;
		head_ = newHead;
	}

	void printList()
	{
		Node *p = head_;
		while ( p != NULL )
		{
			cout<< *(p->p_.pT_) << endl;
			p = p->next_;
		}
	}
	~List()
	{
		Node * p = head_;
		while ( p != NULL )
		{
			Node *paux = p->next_;
			delete p;
			p = paux;
		}
	}
};


int main(int argc, char* argv[])
{
	{
		myPointer<int> x1( new int(5) );
		myPointer<int> x2( new int(7) );
		
		List<int> myList( x1 );
		myList.addToList( x2 );
		myList.addToList( x2 );
		myList.addToList( x1 );

		List<int> mySecondList( x1 );
		mySecondList.addToList( x1 );
		mySecondList.addToList( x2 );
		mySecondList.addToList( x2 );

		myPointer<int> x3( new int(9) );

		myList.addToList( x3 );
		mySecondList.addToList( x3 );

		myList.printList();
		cout<<endl;
		mySecondList.printList();
	}

	_CrtDumpMemoryLeaks();

}

well, this is what I did as fast as I could, maybe it still has bugs, but none that I could find right now :P . For the test i made it has no leaks.
As you can see you have only three objects ( x1, x2, x3 ) that are shared among 2 lists.
More over, you can have the same object more times in the same list ( x1 and x2 appear twice in both lists ).
Insted of the device class you have a template parameter to the myPointer and List classes that will be the contained type. The test provided uses int as the template parameter.