Linked List Question

[termin8tor]

Hey all! I'm new to the forum and a little wet around the programming ears so to speak.

Anyway I have a question regarding Linked Lists.
I know that typically a linked list looks like this:

struct Node
{
   dataType varName; //data type and variable name
   Node *next; //points to next node in list
};

Now I know I can use standard datatypes such as char, int, string and so on so forth quite easily in a linked list, but what I want to do is use my own data type. In this case I have created a simple class structure similar to:

class Book
{
   protected:
          string _title;
          int _isbn;
   public:
          Book(string title, int isbn);
          ~Book();
          void setTitle(string title);
          string getTitle();
          void setIsbn(int isbn);
          int getIsbn();
}

class Magazine : Book
{
   protected:
          string _magazineType;
   public:
          Magazine(string title, int isbn, string magType);
          ~Magazine();
          void setType(string type);
          string getType();
}

Don't take that code too literally, I'm going off of the top of my head. What I'm trying to ask however is in my linked list, how do I get it so that I can create a node that contains a data member of type Book that includes all 'Book' derived classes?

Additionally when adding book objects to the list, what would the syntax be for doing so?

I realise that with a linked list I'm using pointers and and to create a new node is something like:

Node *newNode;
Node *Node_ptr;

newNode = new Node;

Of course if I do this with my custom data class I'm going to get a 'no valid constructor' compile error. What syntax would I need use to pass arguments to the Book constructor? normarily I'd simply do:

Book book1("A Brave New World", 124321);

I don't know how to set a new object using pointers and the like.

I'm a little confused by this and any help is really appreciated!

[jinhao]

The node should like this

struct Node
{
    Book * book;
    Node * next;
};

And create a class as a manipulator for the list.

class book_list
{
public:
	book_list()
		:head_(0), tail_(0)
	{}
	
	template<typename _Book>
	void push_back(const _Book & book)
	{
		Node * pn = new Node;
		pn->book = new _Book(book);
		pn->next = 0;
		
		if(tail_)
			tail_->next = pn;
		else
			head_ = pn;
		tail_ = pn;
	}
	
	void erase(unsigned index)
	{
		Node * pn = node at index;
		detach the pn from list.
		
		delete pn->book;
		delete pn;	
	}
private:
    Node * head_;
    Node * tail_;
};

book_list list;
//insert a book and a magazine
list.insert(Book(title, isbn));
list.insert(Magazine(title, isbn, type));

One important thing: declare the destructor of book with virtual keyword.

After you know how the list data structure works, please use std::list when you need a list.

[termin8tor]

Ah I see, you made that a little clearer. So by creating a pointer to the base class of book within a node, I gain access to all of its derived classes aswell.

Just another quick question about the example you've provided, on line 37 and 38 you're calling an insert function, I take it you mean a hypothetical insert function I'd write to insert a new node to the list right?

so

list.insertFunctionName(Datatype(arguments));
list.addNode(Book("a book title", 12345));

OH! One last thing! You stated I should make sure the destructor is virtual, just curious as to why?

Anyway I really appreciate the response you've given me regardless. That helped a ton.

I haven't learned about templates so that's probably a source of a little of my confusion hehe.

[jinhao]

On line 37 and 38, insert two objects whose types are different, and this is why I give a function template here. Otherwise, two insert functions should be implemented for Book and Magazine.

Declare Book's destructor virtual, becuase Book is used for a base class and a Magazine object is deleted by using its base class pointer, see Line 27.

delete pn->book;

if destructor of Book is not virtual, the destructor of Magazine will not be called when deleting pn->book that refers to a Magazine object, it causes memory leaks.