Thread: class template question

background: I have a linked list assignment to complete.

I have a node class:

Code:

template <typename T>
class Node
{
    ...
};

and a linked list class, from which my question stems:

Code:

template <what goes here?>
class LinkedList
{
    ...
};

I want my LinkedList class to work with Node<T> objects. I can't figure out the template syntax for the linked list class. How would I write this?

Thanks.

Typically, the template parameter will reflect what you want the nodes to to contain. So

Code:

template<typename T> class Node
{
    // whatever
};

template<typename T> class LinkedList
{
     // whatever
};

Implementation wise, presumably a LinkedList<T> will make use of one or more instances of Node<T>. One design choice you'll need to make is in how the list is traversed by a user of the LinkedList - will the user interact with the LinkedList object itself, or will the Node<T> include capability to find its companion "next" node without the user needing to go back to the containing LinkedList?

The LinkedList will be responsible for traversing the Node objects. The Node class is simply:

Code:

template <typename T> 
class Node
{
private:
    T data;
    Node* next;
public:
    //getters/setters
}

So, from what you are saying, my LinkedList should be implemented this way:

Code:

template <typename T> 
class LinkedList
{
// some code...
public:
    void add(Node<T>& node)
    {
         //add note to end of linked list
    }
// other code...
};

Actually, this way makes sense since I only want my LinkedList to work with Node types. The only 'issue' I have is in the readability of an instantiated LinkedList. For example,

LinkedList<string> list;
vs
LinkedList<Node<string>> list;

the first one seems to read "instantiate a LinkedList of type string" even though it's actually working with type Node<string>.

The second one is clearer just by looking at it.

To you maybe, but that's because you care about how the LinkedList is implemented. Why should a user of your class need to know how it is implemented?

Does the user of the LinkedList class even need to know that the individual nodes are Node<T>'s?

For that matter, does the user of the class even need to know it is a linked list? There is a difference between "this container has these properties" and "this container is implemented in this manner". The user of a class cares about its properties (eg how quickly an element may be added or removed) not in how those properties are achieved.

Beginners often have a fetishist belief that, since they have implemented something as a linked list, that the user of the class needs to be exposed to the fact it is a linked list. That encourages them to take shortcuts in their design.

You're right. the user shouldn't know that the linkedlist is implemented with Node objects. All they need to know is that it is a linked list of type <T>, and who cared how LinkedList manages that. Plus, that leaves LinkedList to manage the memory allocation/deallocation of Nodes as well. The user shouldn't have to be responsible for creating new Nodes to pass into LinkedList.

Thanks grumpy.

Originally Posted by jrahhali

background: I have a linked list assignment to complete.

I have a node class:

Code:

template <typename T>
class Node
{
    ...
};

and a linked list class, from which my question stems:

Code:

template <what goes here?>
class LinkedList
{
    ...
};

I want my LinkedList class to work with Node<T> objects. I can't figure out the template syntax for the linked list class. How would I write this?

Thanks.

You might look at it this way:
You already realized that Node needs to have a template type T because the value we're storing in it should be able to be decided by the user.
What do we need to implement LinkedList, then? Well, eventually you will realize when coding it that you need a Node (that's why you made it, right?). But Node takes a type T. What should this type T be? Should be an int, or a string, or something else? Or should the user decide it?
Clearly, since you already made the choice that the user can select what the Node stores, LinkedList should honour that choice. So it must use what the user specifies and forward it, hence it must be a template type.

Although, this is kind of backwards.
Typically you would make the linked list class first, then say you want the user to choose what kind of elements it should store. Then you would make a template for the class, and then you realize you need a node, and it needs to store this type T, so it must also be a template class/struct, and LinkedList must forward T to the Node.