Implementation of LinkedList C++ using friend

Question

I am implementing my own linkedlist in C++ as part of a class assignment. My main concern isn't with the style of the code nor the pros/cons of including or not including certain features as I am still developing member functions.

I would mainly like to know if my approach of declaring LinkedList as a friend of Node is reasonable. My decision for doing this comes from the fact that there is absolutely no need for anything to access my Node class besides LinkedList (e.g. I don't want to be able to create a Node object in main). When I do this, however, I find myself no longer needing public and private access modifiers for Node. Furthermore, I don't particularly need getter/setter methods as I can just access Node's member variables directly from LinkedList (you can see below that I don't call Node::getVal() or Node::getNext() once).

Coming from the world of Java, it seems really strange to ever access an object's internal data directly without getters/setters. What do you guys think? Does this friend relation make sense?

template <typename T> class Node
{
    friend class LinkedList<T>;
    // private:
        Node<T>* next;  // CAN ACCESS MEMBERS DIRECTLY BECAUSE OF FRIEND DECLARATION
        T value;
    // public:
        Node<T>(T valuep)
        {
            value = valuep;
            next = NULL;
        }
        void insert(T valuep)
        {
            if(next == NULL)
            {
                next = new Node<T>(valuep);
                return;
            }
            else
            {
                next->insert(valuep);
            }
        }

        T getVal() // DON'T NEED BECAUSE OF FRIEND DECLARATION
        {
            return value;
        }
        Node<T>* getNext() // DON'T NEED BECAUSE OF FRIEND DECLARATION
        {
            return next;
        }
};

template <typename T> class LinkedList
{
    private:
        Node<T>* head;
    public:
        LinkedList<T>()
        {
            head = NULL;
        }
        ~LinkedList<T>()
        {
            Node<T>* currentNode = head;
            while(currentNode!=NULL)
            {
                Node<T>* next = currentNode->next;
                delete currentNode;
                currentNode = next;
            }
        }
        void insert(T valuep)
        {
            if (head == NULL)
            {
                head = new Node<T>(valuep);
                return;
            }
            else
            {
                head->insert(valuep);
            }
        }

        void print()
        {
            Node<T>* temp = head;
            while(temp!=NULL)
            {
               std::cout << temp->value << std::endl; // ACCESS Node's MEMBERS DIRECTLY
               temp = temp->next; // ACCESS Node's MEMBERS DIRECTLY
            }
        }

        void update(int indexp, T valuep)
        {
            if(indexp==0)
            {
                head->value = valuep; // ACCESS Node's MEMBERS DIRECTLY
            }
        }
};

Answer 1

You could do this:

template<typename T> class LinkedList {

    struct LinkedListNode {
        T m_element;
        LinkedListNode* m_next;

        LinkedListNode(T element)
        :
        m_element{element},
        m_next{nullptr}
        {}
    };

public:

    LinkedList()
    :
    m_head{nullptr},
    m_tail{nullptr}
    {}

    void add(T element) {
        LinkedListNode* node = new LinkedListNode(element);
    }

private:
    LinkedListNode* m_head;
    LinkedListNode* m_tail;
};

int main() {
    LinkedList<int> l;
}

That way, your LinkedListNode implementation is not available outside of your LinkedList.

Answer 2

I would mainly like to know if my approach of declaring LinkedList as a friend of Node is reasonable.

Who needs to know about Nodes existence? In this context, Node is purely an implementation detail of the LinkedList structure. Users do not need to know that Node exists, so like any good spy engineer, only expose information to collaborators users on a need-to-know basis. Make Node a private nested class of LinkedList.

template <typename T>
class LinkedList 
{
    struct Node               // No public exposure, only friends and
    {                         // nested classes of LinkedList know details.
        T value;              // Get/Set directly or enable access control.
        Node* next{nullptr};
    };
    Node* head;

    /* ... */
};

---

    friend class LinkedList<T>;

If you are using a pre-c++11 compiler, you will need to forward declare your LinkedList<T>.

---

    Node<T>(T valuep)
    {
        value = valuep;
        next = NULL;
    }

Prefer in-class initializers (c++11) for initializing constants. Prefer member initializers instead of assignment.

For parameters that are known and cheap to copy (integrals, floating points, pointers, references), you can't really beat passing by value. When working with anything else larger than 2-3 bytes or if working with templates, prefer to pass by reference (to const for in-only params).

With c++11, prefer nullptr to NULL. nullptr is now a well-specified (and restrictive) null type (std::nullptr_t) instead of macro representing an integer.

template <typename T> 
class Node
{
    Node<T>* next{nullptr};                     // in-class initialization
    T value;
public:
    Node<T>(T const& valuep) : value{valuep} {} // member initialization
};

---

else isn't needed after using a control flow interrupt (return, break, continue, etc). Help reduce indentation and limit the amount of code you ask readers to keep track of.

        if (head == nullptr)
        {
            head = new Node<T>(valuep);
            return;
        }
        head->insert(valuep);

---

getVal returns copies. Have you considered returning [const-]references? Consider providing const on member functions that do not mutate. See const-correctness.

---

Try to be descriptive with your naming. I shouldn't have to look through documentation, comments, or code to know that this is a Forward/Singly-Linked list.

---

Follow the Rule of Zero. If you define one of the special member functions (destructor, copy/move constructor, copy/move assignment operator), then explicitly define them all.

With in-class initializers, prefer letting the compiler implicitly generate a default constructor. If you require an explicit argument constructor or a conversion constructor, explicitly default the default constructor.

Your destructor could save on one pointer copy by using head directly instead of currentNode.

template <typename T>
struct LinkedList {
  private:
    struct Node { T value; Node* next; };
    Node* head{nullptr};
  public:
    // Rule of three
    LinkedList(LinkedList const& that) { /* copy that */ }
    LinkedList& operator=(LinkedList const& that) { /* copy that */ }
    ~LinkedList() { /* destroy this */ }

    // Rule of five - C++11
    LinkedList(LinkedList&& that) { /* move that */ }
    LinkedList& operator=(LinkedList&& that) { /* move that */ }
}

---

Do you always want to print to std::cout? Consider defining a std::ostream& parameter to take from the caller. Even better, provide an iterator interface and let the user access all or part of the list values.

Be aware of what std::endl does. If you just want a new line, prefer streaming the new-line character ('\n'). If you want to express to the reader you intended to flush a buffered stream, explicitly stream std::flush.

---

update is incomplete as it doesn't handle non-zero indices. If it's not ready to be reviewed, don't include it for code review.

---

Insertions at the back of the list are expensive. Consider a constant time approach by bookkeeping and inserting directly at the tail.

Answer 3

No, it cannot be reasonable for a Node to be a friend of the List

... even without looking at your code: For a Node within a Linked List be a friend of the Linked List structure/class implies the Node has members which act upon the containing Linked List structure. That should not happen: Other than in exceptional circumstances (which yours aren't), local, internal structures/classes within a larger data structure should be passive, acted upopn by that structure's methods (or by free-standing functions involving the outer and inner structures).