3
\$\begingroup\$

I implemented Linked List data structure in C++ for practice purpose. The LinkedList.h uses Node.h as nodes. Creates and insert nodes dynamically to the list. I included function descriptions as comments just above the functions.

I would like to receive comments and suggestions regarding the code, algorithms (although there aren't much), comment style (i suppose my comment style is a bit poor) and anything I missed.

I include a basic main function, if you would like to run the codes.

Node.h

template <class T>
class Node {
  public:
    Node(const T& item);
    Node(const T& item, Node<T>* nextNode);
    Node<T>* next(void) const;
    void insertNext(Node<T>* nextNode);
    Node<T>* removeNext(void);
    T getData(void) const;
    void changeData(T& item);
  private:
    T data;
    Node<T>* nextPtr;
};

/**
    *  @brief  Default constructor.
    *  @param  item  Data to be stored in the node.
    *  @return  void.
    *
    *  The constructor initializes variables.
    */
template <class T>
Node<T>::Node(const T& item) {
    data = item;
    nextPtr = nullptr;
}

/**
    *  @brief  Default constructor.
    *  @param  item  Data to be stored in the node.
    *  @param  nextNode   The next node of the node.
    *  @return  void.
    *
    *  The constructor initializes variables.
    */
template <class T>
Node<T>::Node(const T& item, Node<T>* nextNode) {
    data = item;
    nextPtr = nextNode;
}

/**
    *  @brief  Returns the next node of the node.
    *  @param  void.
    *  @return  Node pointer of type T.
    */
template <class T>
Node<T>* Node<T>::next(void) const {
    return nextPtr;
}

/**
    *  @brief  Inserts a node after the node.
    *  @param  nextNode  Pointer to the node to be inserted.
    *  @return  void.
    *
    *  Inserts the nextNode after the node and chains nextNode to the
    *  old next of the node.
    *
    */
template <class T>
void Node<T>::insertNext(Node<T>* nextNode) {
    nextNode->nextPtr = nextPtr;
    nextPtr = nextNode;
}

/**
    *  @brief  Removes the nextPtr field of the node.
    *  @param  void.
    *  @return  Node of type T.
    *
    *  Removes the nextPtr field and equates it to nullptr.
    *  Returns the removed pointer.
    *
    */
template <class T>
Node<T>* Node<T>::removeNext(void) {
    Node<T>* removedPtr = nextPtr;
    nextPtr = nullptr;
    return removedPtr;
}

/**
    *  @brief  Retrieves the node data.
    *  @param  void.
    *  @return  Data of type T.
    */
template <class T>
T Node<T>::getData(void) const {
    return data;
}

/**
    *  @brief  Changes the node data.
    *  @param  item  The new data of the node.
    *  @return  void.
    */
template <class T>
void Node<T>::changeData(T& item) {
    data = item;
}

LinkedList.h

#include "Node.h"

template<class T>
class LinkedList {
  public:
    LinkedList(void); //c'tor
    LinkedList(const LinkedList<T>& copyList); //copy c'tor
    ~LinkedList(void); //d'tor

    void insertAt(const T& item); //insert node at currPtr position
    void insertAfter(const T& item); //insert node after currPtr position
    void insertHead(const T& item); //insert node at headPtr position
    void insertTail(const T& item); //insert node at tailPtr position

    void removeAt(void); //remove the node at currPtr position
    void removeHead(void); // remove the head node

    void clear(void); //returns list to initial case
    void freeNode(Node<T>* node); //free dynamic memory of a node

    std::size_t size(void) const; //size of the list
    bool empty(void) const; //the list is empty or not
    T nodeData(Node<T>* node) const; //retrieve the input node data

    void moveToHead(void);//move currPtr to headPtr position
    void moveToTail(void); //move currPtr to tailPtr position
    void moveToPos(int n); //move currPtr to nth position
    int getPos(void) const; //the position of the currPtr

    void print(std::ostream& os); //prints the LinkedList and private variables

  private:
    void init(void); //initializes private variables
    Node<T>* headPtr; //ptr to head node
    Node<T>* tailPtr; //ptr to tail node
    Node<T>* currPtr; //ptr to current node
    Node<T>* prevPtr; //ptr to previous node
    std::size_t sizeL; //size of the linked list
    Node<T>* newNode(const T& item); //allocate dynamic node
    Node<T>* newNode(const T& item, Node<T>* nextNode); //allocate dynamic node
};

/**
    *  @brief  Initializes class variables.
    *  @param  void.
    *  @return  void.
    *
    *  The init function sets all pointer to nullptr and sizeL to 0.
    */
template <class T>
void LinkedList<T>::init(void) {
    //ptr init
    headPtr = nullptr;
    tailPtr = nullptr;
    currPtr = nullptr;
    prevPtr = nullptr;
    //sizeL init
    sizeL = 0;
}

/**
    *  @brief  Default constructor.
    *  @param  void.
    *  @return  void.
    *
    *  The constructor uses init function to initialize variables.
    */
template <class T>
LinkedList<T>::LinkedList(void) {
    init();
}

/**
    *  @brief  Copy constructor.
    *  @param  copyList  The list to be copied.
    *  @return  void.
    *
    *  The copy constructor deepcopies the copyList to the object.
    */
template <class T>
LinkedList<T>::LinkedList(const LinkedList<T>& copyList) {
    init();
    Node<T>* tempPtr = copyList.headPtr;
    for(std::size_t cnt=0; cnt<copyList.sizeL; cnt++) {
        insertAfter(copyList.nodeData(tempPtr));
        tempPtr = tempPtr->next();
    }
    moveToPos(copyList.getPos());
}

/**
    *  @brief  Default destructor.
    *  @param  void.
    *  @return  void.
    *
    *  The destructor uses clear function to release allocated memory.
    */
template <class T>
LinkedList<T>::~LinkedList(void) {
    clear();
}

/**
    *  @brief  Insert node to the LinkedList.
    *  @param  item  Data to be stored in the node.
    *  @return  void.
    *
    *  The insertAt function inserts a node to the location pointed by
    *  currPtr. The nodes following the currPtr are shifted whereas
    *  the nodes before the currPtr remain same.
    *
    *  If currPtr is pointing head or the LinkedList is empty,
    *  the function uses insertHead function.The LinkedList grows
    *  dynamically.
    *
    *  As a result of this function the currPtr points to the newly
    *  inserted node.
    */
template <class T>
void LinkedList<T>::insertAt(const T& item) {
    if((currPtr == headPtr) || empty()) {
        insertHead(item);
    } else {
        Node<T>* tempPtr = newNode(item); //get a new node
        prevPtr->insertNext(tempPtr); //insert it after prevPtr
        currPtr = tempPtr; //arrange currPtr
        sizeL += 1; //sizeL increments
    }
}

/**
    *  @brief  Insert node to the LinkedList.
    *  @param  item  Data to be stored in the node.
    *  @return  void.
    *
    *  The insertAfter function inserts a node to the next of location
    *  pointed by currPtr. The nodes following the currPtr are shifted
    *  whereas the node currPtr and preceding nodes remain same.
    *
    *  If currPtr is pointing tail, the function uses insertTail
    *  function. The LinkedList grows dynamically.
    *
    *  If the LinkedList is empty, the function uses insertHead
    *  function.
    *
    *  As a result of this function the currPtr points to the newly
    *  inserted node.
    */
template <class T>
void LinkedList<T>::insertAfter(const T& item) {
    if(empty()) {
        insertHead(item);
    } else if(currPtr == tailPtr) {
        insertTail(item);
    } else {
        Node<T>* tempPtr = newNode(item); //get a new node
        currPtr->insertNext(tempPtr); //insert it after prevPtr
        prevPtr = currPtr; //arrange prevPtr
        currPtr = tempPtr; //arrange currPtr
        sizeL += 1; //sizeL increments
    }
}

/**
    *  @brief  Insert node to the head of the LinkedList.
    *  @param  item  Data to be stored in the node.
    *  @return  void.
    *
    *  The insertHead function inserts a node to the head location
    *  of the LinkedList. The nodes following the headPtr are shifted.
    *
    *  As a result of this function the currPtr points to the newly
    *  inserted head node.
    */
template <class T>
void LinkedList<T>::insertHead(const T& item) {
    if(empty()) {
        Node<T>* tempPtr = newNode(item); //get a new node
        headPtr = currPtr = tailPtr = tempPtr; /* arrange headPtr, currPtr,
                                                tailPtr */
        sizeL = 1; //sizeL is 1
    } else {
        Node<T>* tempPtr = newNode(item, headPtr); //get a new node
        headPtr = currPtr = tempPtr; // arrange headPtr, currPtr
        prevPtr = nullptr; //arrange prevPtr
        sizeL += 1; //sizeL increments
    }
}

/**
    *  @brief  Insert node to the tail of the LinkedList.
    *  @param  item  Data to be stored in the node.
    *  @return  void.
    *
    *  The insertTail function inserts a node to the tail location
    *  of the LinkedList.
    *
    *  If the LinkedList empty, insertTail function uses insertHead function.
    *
    *  As a result of this function the currPtr points to the newly
    *  inserted tail node.
    */
template <class T>
void LinkedList<T>::insertTail(const T& item) {
    if(empty()) {
        insertHead(item);
    } else {
        Node<T>* tempPtr = newNode(item); //get a new node
        prevPtr = tailPtr;
        tailPtr->insertNext(tempPtr); //insert it after tailPtr
        currPtr = tailPtr = tempPtr; //arrange currPtr, tailPtr
        sizeL += 1; //sizeL increments
    }
}

/**
    *  @brief  Remove the node pointed by currPtr.
    *  @param  void.
    *  @return  void.
    *
    *  The removeAt function removes the node pointed by currPtr. The node
    *  following is the new currPtr and is chained to prevPtr.
    *
    *  If the currPtr points to head, removeAt function uses
    *  removeHead function.
    *
    *  If currPtr points to tail, the preceding node is the new currPtr.
    *
    *  If the LinkedList becomes empty after removal,
    *  the variables are reset to initial states.
    *
    *
    */
template <class T>
void LinkedList<T>::removeAt(void) {
    if(empty()) {
        std::cerr << "The LinkedList empty. Can't remove current node." << '\n';
    } else if(size() == 1) {
        clear();
    } else if(currPtr == headPtr) {
        removeHead();
    } else if(currPtr == tailPtr) {
        freeNode(currPtr); //delete currPtr
        tailPtr = prevPtr; //arrange tailPtr
        sizeL -= 1; // decrement sizeL
        moveToTail(); // move currPtr to tailPtr
    } else {
        Node<T>* tempPtr = currPtr->next(); //hold next of currPtr
        currPtr->insertNext(prevPtr); /* insert prevPtr to the next of currPtr.
                                        currPtr is out of list */
        freeNode(currPtr); //delete currPtr
        currPtr = tempPtr; //arrange currPtr
        sizeL -= 1;
    }

}

/**
    *  @brief  Remove the node pointed by headPtr.
    *  @param  void.
    *  @return  void.
    *
    *  The removeHead function removes the node pointed by headPtr. The node
    *  following is the new headPtr.
    *
    *  If the currPtr points to head, currPtr is updated to new headPtr.
    *
    *  If the prevPtr points to head, prevPtr is updated as nullptr.
    */
template <class T>
void LinkedList<T>::removeHead(void) {
    if(empty()) {
        std::cerr << "The LinkedList empty. Can't remove head  node." << '\n';
    } else if(size() == 1) {
        clear();
    } else if(currPtr == headPtr) {
        Node<T>* tempPtr = headPtr->next(); //hold next of headPtr
        freeNode(headPtr); //delete headPtr
        headPtr = tempPtr; //arrange headPtr
        sizeL -= 1; //decrements sizeL

        currPtr = headPtr; //arrange currPtr
    } else if (prevPtr == headPtr) {
        Node<T>* tempPtr = headPtr->next(); //hold next of headPtr
        freeNode(headPtr); //delete headPtr
        headPtr = tempPtr; //arrange headPtr
        sizeL -= 1; //decrements sizeL

        prevPtr = nullptr; //arrange currPtr
    } else {
        Node<T>* tempPtr = headPtr->next(); //hold next of headPtr
        freeNode(headPtr); //delete headPtr
        headPtr = tempPtr; //arrange headPtr
        sizeL -= 1; //decrements sizeL
    }
}

/**
    *  @brief  Returns the LinkedList to its initial state.
    *  @param  void.
    *  @return  void.
    *
    *  The clear function deletes all nodes in the LinkedList and returns
    *  all variables to their initial state.
    */
template <class T>
void LinkedList<T>::clear(void) {
    moveToHead();
    Node<T>* tempPtr;
    for(std::size_t cnt=0; cnt<sizeL; cnt++) {
        tempPtr = currPtr->next();  //hold next of currPtr
        freeNode(currPtr); //delete currPtr
        currPtr = tempPtr; //arrange currPtr
    }
    init();
}

/**
    *  @brief  Releases allocated dynamic memory of a node.
    *  @param  node  The pointer to the target node.
    *  @return  void.
    */
template <class T>
void LinkedList<T>::freeNode(Node<T>* node) {
    delete node;
}

/**
    *  @brief  Returns the LinkedList size.
    *  @param  void.
    *  @return  size
    */
template <class T>
std::size_t LinkedList<T>::size(void) const {
    return sizeL;
}

/**
    *  @brief  Returns true if the LinkedList empty,
    *  @brief  false otherwise.
    *  @param  void.
    *  @return  Boolean value true or false.
    */
template <class T>
bool LinkedList<T>::empty(void) const {
    return (sizeL == 0);
}

/**
    *  @brief  Returns the data stored in the specified node.
    *  @param  node  The target node.
    *  @return  The data stored in the node of type T.
    */
template <class T>
T LinkedList<T>::nodeData(Node<T>* node) const {
    return node->getData();
}

/**
    *  @brief  Move currPtr to headPtr.
    *  @param  void.
    *  @return  void.
    *
    *  The moveToHead function moves currPtr to headPtr.
    */
template <class T>
void LinkedList<T>::moveToHead(void) {
    currPtr = headPtr;
    prevPtr = nullptr;
}

/**
    *  @brief  Move currPtr to tailPtr.
    *  @param  void.
    *  @return  void.
    *
    *  The moveToTail function uses moveToHead function with
    *  parameter (sizeL - 1) to move currPtr to tailPtr.
    */
template<class T>
void LinkedList<T>::moveToTail(void) {
    moveToPos(sizeL - 1);
}

/**
    *  @brief  Move currPtr to nth node of the LinkedList.
    *  @param  n  Position of the target node where n € [0 , sizeL - 1].
    *  @return  void.
    *
    *  The moveToPos function iterates over the LinkedList nodes to move
    *  currPtr to the nth node of the LinkedList. n is in
    *  the range of [0 , sizeL - 1].
    *
    *  The moveToPos function uses moveToHead function to move currPtr
    *  to headPtr.
    */
template <class T>
void LinkedList<T>::moveToPos(int n) {
    moveToHead();
    for(int cnt=0; cnt<n; cnt++) {
        prevPtr = currPtr;
        currPtr = currPtr->next();
    }
}

/**
    *  @brief  Returns the position of the currPtr
    *  @param  void.
    *  @return  Integer representing position of the currPtr.
    *
    *  The getPost function iterates over the list until reaches the currPtr.
    *  Then returns the position of the currPtr as int.
    */
template <class T>
int LinkedList<T>::getPos(void) const {
    Node<T>* tempPtr = headPtr;
    int cnt;
    for(cnt=0; tempPtr!=currPtr; cnt++) {
        tempPtr = tempPtr->next();
    }
    return cnt;
}

/**
    *  @brief  Creates a dynamic Node of type T.
    *  @param  item  Data to be stored in the new node.
    *  @return  void.
    *
    *  Returns a pointer to node created dynamically. The new node's data is
    *  item of type T. The new node's next pointer is nullptr.
    */
template <class T>
Node<T>* LinkedList<T>::newNode(const T& item) {
    Node<T>* tempPtr = nullptr;
    tempPtr = new Node<T>(item);
    if(tempPtr == nullptr) {
        std::cerr << "Memory allocation for new node is failed" << '\n';
        return nullptr;
    } else {
        return tempPtr;
    }
}

/**
    *  @brief  Creates a dynamic Node of type T.
    *  @param  item  Data to be stored in the new node.
    *  @param  nextNode  The next node of the new node.
    *  @return  void.
    *
    *  Returns a pointer to node created dynamically. The new node's data is
    *  item of type T. The new node's next pointer is nextNode of type T.
    */
template <class T>
Node<T>* LinkedList<T>::newNode(const T& item, Node<T>* nextNode) {
    Node<T>* tempPtr = nullptr;
    tempPtr = new Node<T>(item, nextNode);
    if(tempPtr == nullptr) {
        std::cerr << "Memory allocation for new node is failed" << '\n';
        return nullptr;
    } else {
        return tempPtr;
    }
}

/**
    *  @brief  Prints the LinkedList nodes together with private variables.
    *  @param  os  The printing medium.
    *  @return  void.
    */
template <class T>
void LinkedList<T>::print(std::ostream& os) {
    os << "Class Variables:\n";
    //headPtr
    if(headPtr == nullptr)
        os << "headPtr: " << "nullptr" << " | ";
    else
        os << "headPtr: " << headPtr << ' '  << nodeData(headPtr) << " | ";
    //prevPtr
    if(prevPtr == nullptr)
        os << "prevPtr: " << "nullptr" << '\n';
    else
        os << "prevPtr: " << prevPtr << ' '  << nodeData(prevPtr) << '\n';
    //tailPtr
    if(tailPtr == nullptr)
        os << "tailPtr: " << "nullptr" << " | ";
    else
        os << "tailPtr: " << tailPtr << ' ' << nodeData(tailPtr) << " | ";
    //currPtr
    if(currPtr == nullptr)
        os << "currPtr: " << "nullptr" << '\n';
    else
        os << "currPtr: " << currPtr << ' '<< nodeData(currPtr) << '\n';

    //sizeL
    os << "sizeL: " << sizeL << '\n';
    Node<T>* tempPtr = headPtr;
    for(std::size_t cnt=0; cnt<sizeL; cnt++) {
        os << nodeData(tempPtr) << " -> ";
        tempPtr = tempPtr->next();
    }
    os << '\n';
}

Test Code

#include "LinkedList.h"

int main() {
    LinkedList<int> MyList;
    for(int i=1; i<7; i++)
        MyList.insertAfter(i);
    MyList.print(std::cout);

    MyList.moveToPos(3);
    MyList.print(std::cout);

    MyList.removeAt();
    MyList.print(std::cout);

    MyList.insertAt(9);
    MyList.print(std::cout);

    MyList.insertAfter(10);
    MyList.print(std::cout);

    MyList.removeAt();
    MyList.print(std::cout);

    MyList.removeAt();

    MyList.moveToPos(3);
    MyList.print(std::cout);
    std::cout << "********************" << '\n';
    LinkedList<int> CopiedList(MyList);
    CopiedList.print(std::cout);
    std::cout << "********************" << '\n';

    MyList.moveToHead();
    MyList.print(std::cout);
    MyList.removeHead();
    MyList.removeHead();
    MyList.removeAt();
    MyList.removeAt();
    MyList.removeAt();
    MyList.removeAt();

    MyList.print(std::cout);
    std::cout << "********************" << '\n';
    CopiedList.print(std::cout);
    std::cout << "********************" << '\n';

    for(int i=1; i<6; i++)
        MyList.insertHead(i);
    MyList.print(std::cout);
}
```
\$\endgroup\$
2
  • 2
    \$\begingroup\$ I'd like for the downvoter (who's probably the close voter) to explain the reasoning behind this. It seems like a well written question with clear description and + from a new contributor, I think it's bad faith to act like this. \$\endgroup\$
    – IEatBagels
    Aug 21, 2019 at 16:53
  • 1
    \$\begingroup\$ Currently, CR is a bit buggy when it comes to code fences. Your code may end up having an unwanted three backticks at the end. You can work around this issue by using indentation instead of code fences. (You can select the code and press Ctrl-K.) Also, don’t be discouraged by occasional illogical downvotes. \$\endgroup\$
    – L. F.
    Aug 22, 2019 at 10:01

2 Answers 2

2
\$\begingroup\$

Comments

Comments should be meaningful. Yours are not. Writing comments that just repeat the code are actual harmful rather than helpful. Over time the comments and code will diverge (as bugs are found and fixed). Then a maintainer that is reading code and comments will find a discrepancy, does he fix a comment or the code? They can probably find out using the source control but its a huge waste of time.

Comments should be reserved to explain WHY something is done. Use self documenting code (good variable/function/type names) to document HOW.

Comments could also be used to explain algorithms where the code is complex or to put a link to where the algorithm is explained (if you know the link will last).

Example
/**
    *  @brief  Inserts a node after the node.
    *  @param  nextNode  Pointer to the node to be inserted.
    *  @return  void.
    *
    *  Inserts the nextNode after the node and chains nextNode to the
    *  old next of the node.
    *
    */
template <class T>
void Node<T>::insertNext(Node<T>* nextNode) {
    nextNode->nextPtr = nextPtr;
    nextPtr = nextNode;
}

Did that comment tell me anything I could not understand by simply reading the name of the function insertNext() and the two lines of code!

Design

You have implemented a singly linked list. Sure but this is actually harder to do than implement a doubly linked list. As a result I am sure I will find a bug. The tiny amount of extra design will simplify your code tremendously.

You have implemented the list using null to mark the terminator. If you look up a technique called Sentinel List you will find a technique that removes the need for null. By removing the need for null your code will be highly simplified as you don't need to special case inserting into an empty list or and the head/tail of a list it is all simply an insertion into the list.

You maintain state about the internal "current" position. Could not see any errors but it seemed all a bit doggey and makes the code complex. I would dump this functionality and just ask the user to pass a position for insertion/deleting/getting.

High Level Code

Making it as a top level type you have exposed an implementation detail of the class. This is bad design as it locks you into using that implementation.

Also because you have made it a top level type you have overcomplicated it (presumably to prevent abuse). But a class that should have been 6 lines top takes a 100 lines of vertical space. That's an unnecessary cognitive load to put on the maintainer.

Idioms

Your linked list holds pointers. But I don't see you obeying the rule of 3/5. You should look it up and read it.

But without reading the code I bet the following does strange things.

MyList<int>     listA;
listA.insertHead(1);

MyList<int>     listB;
listB = listA;                 // Uses the compiler generated copy assignment
                               // If you don't define one the compiler does.
                               // When you'r class has pointers make sure
                               // you define the methods the compiler may
                               // generate automatic implantations off.
listB.insertHead(2);

How many items are in listA?

What is The Rule of Three?
Rule-of-Three becomes Rule-of-Five with C++11?

More Reading

Have a look at this review.
https://codereview.stackexchange.com/a/126007/507

Code Review

template <class T>
class Node {
  public:
    Node(const T& item);
    Node(const T& item, Node<T>* nextNode);
    Node<T>* next(void) const;
    void insertNext(Node<T>* nextNode);
    Node<T>* removeNext(void);
    T getData(void) const;
    void changeData(T& item);
  private:
    T data;
    Node<T>* nextPtr;
};

MY class would simply have been:

template<typename T>
template List
{
    struct Node          // Here Node is a private member of the class.
    {                    // As long as you don't expose a Node through
        T      data;     // the list interface its implementation is private.
        Node*  next;     // Thus adding member access functions is superfluous.
        Node*  prev;     // as only you can use the node.
    }
    ...
}

In constructors prefer to use initializer lists rather code blocks to initialize the data. This is because if you don't specifically specify initializer list items then the compiler is going to generate them for you.

Node<T>::Node(const T& item) {
    data = item;
    nextPtr = nullptr;
}

The above code is equivalent to:

Node<T>::Node(const T& item)
    : data()                  // default initialization of the type T
{                             // So you will call the constructor of T here.
                              // Not a big deal for integers but what if T
                              // has an expensive type?

    data = item;              // Here you are calling the assignment operator.
                              // So now you have called the constructor
                              // followed by a copy assignment.
    nextPtr = nullptr;
}

You should have written like this:

Node<T>::Node(const T& item)
    : data(item)
    , nextPtr(nullptr)
{}

I don't see a move constructor?

Node<T>::Node(T&& item)        // Notice the double &&
    : data(std::move(item))
    , nextPtr(nullptr)
{}

Here if T is expensive to construct we can move the object into the node. Move semantics has been a standard part of the language since C++11 (8 years).

Sometimes it is also nice to have a construct in place constructor. It may be cheap to pass the parameters to construct a T rather than passing around a T. To do this you need to use var arg templates so a bit more complicated syntactically.

template<typename... Args>               // Variable number of arguments.
Node<T>::Node(Args&& args...)
    : data(std::forward<Args>(args)...)  // Arguments forwarded to constructor
    , nextPtr(nullptr)
{}

Return value (of containers) by reference.

T Node<T>::getData(void) const {
    return data;
}

Here you are returning y value this means you are creating a copy of the body to return. If T is expensive to copy this is probably not what you want to do.

T const& Node<T>::getData(void) const {
  ^^^^^^
    return data;
}

Pass parameters by const reference (rather than reference).

void Node<T>::changeData(T& item) {
    data = item;
}

Unless you explicitly want to modify item then you should pass it be const reference. Also without the const you can not pass temporary object to this function.

struct X {
   X(int x) /* constructor */ {}
};

Node<T>    node(5); // This is allowed as the constructor takes by const ref.
node.changeData(6); // Not allowed as we need to construct a temporary X here.
                    // You can not pass a reference to a temporary object.
                    // A const reference is OK.

Again you may want to add a move version of this interface.


Don't print error messages from inside structures.
Throw an exception and allow the business logic externally decide if it wants to print an error message.

void LinkedList<T>::removeAt(void) {
    if(empty()) {
        std::cerr << "The LinkedList empty. Can't remove current node." << '\n';
        // Throw an exception if you want the message.
        // or simply ignore if it is not an error to remove from an empty list.
    } 

This seems a bit redundant.

void LinkedList<T>::freeNode(Node<T>* node) {
    delete node;
}

Why call freeNode(node)l when you could just call delete node;?


Two line initialization should be avoided:

   Node<T>* tempPtr = nullptr;
    tempPtr = new Node<T>(item);

Prefer to simply create and initialize:

   Node<T>* tempPtr = new Node<T>(item);

The action new never returns nullptr. If it fails to allocate then it will throw an exception.

    if(tempPtr == nullptr) {
        std::cerr << "Memory allocation for new node is failed" << '\n';
        return nullptr;
    } else {
        return tempPtr;
    }

Which is lucky for you. You return a null pointer but all your code assumes that this function never returns a nullptr and uses it as if the value was always good.

This is really shitty design and you lucked out in that the new would never give you a bad value.


Sure: Note: printing should not change the class so mark it const.

void LinkedList<T>::print(std::ostream& os) const {
                                      //    ^^^^^
    ...
}

But why not also make it work like a normal C++ streaming object.

friend std::ostream& operator<<(std::ostream& str, LinkedList const& data) {
    data.print(str);
    return str;
}
\$\endgroup\$
2
  • \$\begingroup\$ thank you (even though such comments are discouraged by CR) for such a detailed evaluation. I have a lot to learn from this answer. I will go over this line by line definitely. \$\endgroup\$
    – Erdem Tuna
    Aug 22, 2019 at 21:44
  • 1
    \$\begingroup\$ I think it's important to separate internal comments (in-line commentary) from external comments (documentation). Internal comments are useful for code maintainers. As you said, those comments should be kept short and crisp, explaining the "why" instead of the "what". External comments (documentation) are used by code consumers who don't care about the "why". Instead, they need the "what". Consumers need explicit documentation since they need to figure out which function to call, not how those functions work. \$\endgroup\$
    – Snowhawk
    Aug 22, 2019 at 23:43
1
\$\begingroup\$
  1. Strip out all your comments.

    The best of them are just unbelievably redundant, as they just restate the code, using as many words as feasible.

    A different Q&A going more into the comments is "Guessing a number, but comments concerning".

  2. Reduce Node to the bare necessities, and make it a private member of List.

    It's an implementation-detail of it, and giving it an elaborate interface and its own invariants to maintain needlessly complicates things.

    struct Node {
        struct Node* link;
        T data;
    };
    
  3. Only application-code can have a good reason to interact directly with the user without explicit request. All other code should refrain from doing so, instead using exceptions, error-codes and error-values to delegate the choice to the caller.
    Composability, reusability and testability suffer if this basic point is violated.

  4. Use the ctor-init-list to initialize the members, that's what it's for. Put the tear-down directly into the dtor, and you can implement .clear() by swapping with a temporary.

  5. If you use pointers-to-pointers, you can dispense with all the special-casing.

  6. Implement a proper iterator-interface:

    1. You can dispense with the band-aid of the internal iterator.
    2. You can use standard algorithms. Use them to implement your convenience-functions, unless you drop them completely as redundant.
    3. You can stop keeping track of any but the first node, only allowing insertion at the head or given an iterator.

    All those aspects simplify the implementation and make the abstraction more useful.

  7. Keep to the standard interface where possible. While doing your own thing may be fun, the jarring inconvenience is unsupportable. This is not a fashion show.

  8. pointer == nullptr can be simplified to !pointer. Just like pointer != nullptr is nearly always equivalent to pointer, though where the exact type is important !!pointer works.

\$\endgroup\$
2
  • \$\begingroup\$ I was always unsure about my commenting, suggestion 1 will work a lot for me. May I request a bit more information on suggestions 4 and 5? Regarding 4, releasing memory in directly destructor is okay, but I didn't understand implementing .clear() by swapping with a temporary. Regarding 5, do you mean the special cases like in insert and remove functions? How does pointer-to-pointer use avoid those cases (I just need some more keywords to search)? \$\endgroup\$
    – Erdem Tuna
    Aug 22, 2019 at 21:53
  • 1
    \$\begingroup\$ The copy-and-swap idiom is a common way to implement efficient and exception-safe (copy-/move-) assignment. (There are reasons it might not be right for move-assignment.) Instead of copying an argument, for .clear() just use a default-initialized temporary. Regarding double-pointers, the insert-pointer should point to the place where the address of the new node should be stored, not either to the node containing it or be null. \$\endgroup\$ Aug 22, 2019 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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