3
\$\begingroup\$

I'm working on building understanding of data structures in general, and specifically linked lists in this example. I'm also trying to increase my ability with templates.

In cross-referencing dozens of examples, I've blended what I've seen into the following node template "Node.h" file:

/*
11 May 2015
VS 2015 Community
Author: Diche Bach
Node template header file.
*/
#ifndef NODE_H
#define NODE_H

#include<iostream>

template<class tNode>
class Node
{
    friend std::istream& operator>>(std::istream& str, tNode& data)
    {
        return str >> data_;
    }
    friend std::ostream& operator<<(std::ostream& str, tNode const& data)
    {
        return str << data_ << " ";
    }
    public:
      Node(tNode data, tNode *link);

    private:
      tNode data;
      tNode *next;
};

#endif /* NODE_H */

The goal is that this Node template be as modular and 'resusable' as possible. Thus, the same node template could be used with a LinkedList template, a DoubleLinked List template, a Stack template, etc.

With only two semesters of C++ under my belt, I'm pushing my envelope, and I appreciate suggestions and comments.

The use of the friend mechanism is something I've never done before, but it seems salient to the goals, so I particularly appreciate comments on that portion.

\$\endgroup\$
4
\$\begingroup\$

In the case of linked lists, the pointer to the next value should be a pointer to another Node instance, not a pointer to another data entry. This would allow you to walk the entire list node-by-node.

You have defined methods for using a stream to read/write the node's value, but what if I just want to access the value do something else with it that doesn't involve a stream? A getter like T& getValue(); and/or const T& getValue() const should be mandatory. This will also allow you to extract the stream operators outside of the class and be able to implement them without friend.

When it comes to templates T is preferred as the typename insteam of tNode which can be easily mistaken for a specific class instead of a template.

\$\endgroup\$
  • \$\begingroup\$ 'tNode data; tNode next;' should be: 'tNode data; data next;' Reflects my lack of understanding of the template syntax. As far as the get and set functions, my inclination was that those sorts of things would be handled by the List class, but perhaps that is not good design? \$\endgroup\$ – Diche Bach May 11 '16 at 16:11
  • \$\begingroup\$ It would be tNode data; Node *next; in your case. \$\endgroup\$ – D. Jurcau May 11 '16 at 16:21
  • \$\begingroup\$ Great, thanks folks! The issue of template naming: I have no experience, but it seems that 'tNode' for the Node template (although based on Loki's comments the whole idea of a generic node template might be a bad idea), 'tList' for a list template, 'tStack' for a stack template . . . isn't thay "less" not more confusing than "T" for all templates? \$\endgroup\$ – Diche Bach May 11 '16 at 16:24
  • \$\begingroup\$ The template argument is the type of the payload you are carrying (it will be specialized to int, string, whatever). It doesn't have anything to say in the way you store the data (as a linked list), so it's name can simply be T. You start to use different names for template arguments the moment your class/function starts to require multiple different template arguments. \$\endgroup\$ – D. Jurcau May 11 '16 at 16:28
4
\$\begingroup\$
template<class tNode>

Looks slightly wierd (especially with the initial lowercase letter). Keep template type short.

template<class T>

Nearly every template class I create uses just T or I.

T:       Generic Type
I:       Iterator

You have the copy constructor. But the link value looks strange.

Node(tNode data, tNode *link);

Should this not be:

Node(tNode data, Node<T>* link); // link to the next node in the chain.
                                 // Though you would have to change your
                                 // next type to match.

I would also add a move constructor and emplace constructor.

Node(Node<T>* next, T const& copy);   // copy
Node(Node<T>* next, T&& move);        // move
template<typename... Args>
Node(Node<T>* next, Args... args);    // emplace data

Since we are taking generic nodes. You may need to look at assignment operators (both copy and move). Your class contains a raw pointer.

Your only problem at the moment is that the data is private. So there is no way to extract the data from the node and give it back to the user. If this is a generic node you will need getter functions (A private node class can just leave the data public).

I don't think the goal of a generic Node class is a good idea. I think each class you describe has different requirements for a Node class and a generic one will get overcomplex to handle all situations.

Also you will be exposing your internal structure to people that do not need to know. I would prefer to make a private Node class internal to each of the data structures. You can then make assumptions (as long as they are documented) as the classes will never be exposed eternally.

Take a look at: LinkedList with Node implementation

\$\endgroup\$
  • \$\begingroup\$ The fact you say a generic node might not be a good idea is very instructive! \$\endgroup\$ – Diche Bach May 11 '16 at 16:20
2
\$\begingroup\$

In addition to the points raised by other answers ...

You seem to have the wrong types in operator>> and operator<< functions. I think you meant to use Node, not tNode.

friend std::istream& operator>>(std::istream& str, Node& node)
{
    return str >> node.data;
}
friend std::ostream& operator<<(std::ostream& str, Node const& node)
{
    return str << node.data << " ";
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.