0
\$\begingroup\$

I am currently in between semesters at school and am using that time to improve on my knowledge of C++ classes by making a node class and a linked list class that inherits from the node class. There is a list of areas in need of improvement at the start of the code, but I was also hoping to get some external input on this as well. Once these two classes are more sounds I'm going to implement a stack and queue class as well. I am building this code using Visual Studio 2019 on a Windows 10 operating system, and I do not believe it is optimized for cross-OS use.

If you believe that the int main() function I use to test the member functions is necessary to giving accurate feedback, I would be happy to comply.

//LinkedList.h
 #include <stdio.h>
 #pragma once

/*PLACES TO START AND IMPROVE ON CODE
Proper ctor and dtor implementation,
Replace int data value with template <typename T>,
Const Correctness,
keep default constructor in protected,
ostream operator
set_tail() and get_tail() function utilization
return node* from back_list() and push_back()
*/


const int UnkD = 999;//Variable for node() default constructor init

//NODE class code from http://cplusplus.com/forum/beginner/194591
class node {
protected:
    int data;
    node* prev;
    node* next;
public:
    node() : data(UnkD), prev(nullptr), next(nullptr) { printf("default node() ctor called... \n"); } //Default Constructor
    node(const int & d,node* p,node* n): data(d), prev(p), next(n) { printf("node() ctor with args called... \n"); } //Constructor With Args
    node(const node& rhs) {
        printf("node() copy ctor called... \n"); 
        data = rhs.data;
        prev = rhs.prev;
        next = rhs.next;
    }; //Copy Constructor

    node & operator = (const node& rhs) { //Copy Operator
        printf("Copy Operator");
        if (this != &rhs) {
            data = rhs.data;
            prev = rhs.prev;
            next = rhs.next;
        }
        return *this;
    }

    void set_data(int x) { data = x; }
    void set_prev(node* node) { prev = node; }
    void set_next(node* node) { next = node; }
    int get_data() { return this->data; }
    node* get_prev() { return this->prev; }
    node* get_next() { return this->next; }

    ~node() { printf("~node() dtor called...\n"); delete[] this; };
};

class LL: public node {
private:
    node* head;
    node* tail;
public:
    //Class Ctor Functions
    LL() : head(nullptr), tail(nullptr) { printf("LL deault constructor \n"); }
    LL(node* head, node* tail) : head(nullptr), tail(nullptr) { printf("LL constructor with assignments \n"); }

    void set_head(node* node) { head = node; }
    void set_tail(node* node) { tail = node; }
    node* get_head() { return this->head; }
    node* get_tail() { return this->tail; }

    //Create and Destroy Fucntions
    node* create_node(int d);
    void delete_list(node* list);
    void delete_selected(node* list, int selection);

    //Add and Remove Node Functions
    node* push_front(node* list, node* node);
    node* push_back(node* list, node* node);
    node* pop_front(node* list);
    void pop_back(node* list);
    void append_before(node* list, node* node, int selection);
    void append_after(node* list, node* node, int selection);

    //View List Functions
    void front_list(node* list);
    void back_list(node* list);
    void print_fwd(node* list);
    void print_bwd(node* list);
    void list_selected(node* list, int selection);

    ~LL() {
        printf("LL destructor \n");
        while (head)
        {
            node* tmp = head->get_next();
            delete[] tmp;
        }
    }
};

//create and destroy functions
node* LL::create_node(int d) { return new node{ d, nullptr, nullptr }; }
void LL::delete_list(node* list) {
    while (list)
    {
        node* tmp = list;
        list = list->get_next();
        delete[] tmp;
    }
    printf("List Deleted. \n");
}
void LL::delete_selected(node* list, int selection) {
    int count = 0;
    while (count != (selection - 1)) {
        list = list->get_next();
        count++;
    }

    node* tmp = list;
    list = list->get_prev();
    list->set_next(tmp->get_next());
    list = tmp->get_next();
    list->set_prev(tmp->get_prev());

    
    //delete[] tmp;
}

//add and remove node functions
node* LL::push_front(node* list, node* node) {
    if (!list) { return node; }

    node->set_next(list);
    list->set_prev(node);
    list = node;

    return list;
}
node* LL::push_back(node* list, node* node) {
    if (list->get_next() == nullptr) { list->set_next(node); node->set_prev(list); }
    else {
        while (list->get_next()) { list = list->get_next(); }
        list->set_next(node); node->set_prev(list);
    }
    return node;
}
node* LL::pop_front(node* list) {
    //node* tmp = list;
    list = list->get_next();
    list->set_prev(nullptr);
    //delete[] tmp;
    return list;
}
void LL::pop_back(node* list) {
    node* tmp;
    if (list->get_next() == nullptr) {
        //tmp = list;
        list = list->get_prev();
        list->set_next(nullptr);
    }
    else {
        while (list->get_next()) { list = list->get_next(); }
        //tmp = list;
        list = list->get_prev();
        list->set_next(nullptr);
    }
    //delete[] tmp;
}
void LL::append_before(node* list, node* n, int selection) {
    int count = 0;
    while (count != (selection - 1)) {
        list = list->get_next();
        count++;
    }

    n->set_next(list);
    n->set_prev(list->get_prev());
    node* tmp = list->get_prev();
    tmp->set_next(n);
    list->set_prev(n);
}
void LL::append_after(node* list, node* n, int selection) {
    int count = 0;
    while (count != (selection - 1)) {
        list = list->get_next();
        count++;
    }

    n->set_next(list->get_next());
    node* tmp = list->get_next();
    tmp->set_prev(n);
    n->set_prev(list);
    list->set_next(n);
}

//View list functions
void LL::front_list(node* list) {
    if (list->get_prev() == nullptr) { printf("The data at the front of the list is %d \n", list->get_data()); }
    else {
        while (list->get_prev()) { list = list->get_prev(); }
        printf("The data at the front of the list is %d \n", list->get_data());
    }
}
void LL::back_list(node* list) {
    if (list->get_next() == nullptr) { printf("The data at the back of the list is %d \n", list->get_data()); }
    else {
        while (list->get_next()) { list = list->get_next(); }
        printf("The data at the back of the list is %d \n", list->get_data());
    }
}
void LL::print_fwd(node* list) {
    int count = 0;
    while (list)
    {
        printf("count [%d] : %d \n", count, list->get_data());
        list = list->get_next();
        count++;
    }
}
void LL::print_bwd(node* list) {
    int count = 0;

    while (list->get_next()) { list = list->get_next(); count++; }
    while (list) {
        printf("count [%d] : %d \n", count, list->get_data());
        list = list->get_prev();
        count--;
    }
}
void LL::list_selected(node* list, int selection) {
    int count = 0;
    while (count != (selection - 1)) {
        list = list->get_next();
        count++;
    }
    printf("node %d: [%d] %d \n", selection, (selection - 1), list->get_data());

}
\$\endgroup\$
3
  • \$\begingroup\$ Welcome to CodeReview@SE. Conventionally, questions are titled for the task to accomplish. (And the first advice as to your code may be that code should tell what everything is there for.) \$\endgroup\$
    – greybeard
    Nov 27, 2019 at 3:30
  • \$\begingroup\$ The copy constructor and copy assignment operators perform shallow copies (both objects will point to the same list data), and the copy assignment leaks memory used by the existing (this) object. delete[] this; does not belong in a destructor. Correct these bugs, then edit your question to include the fixed code. \$\endgroup\$ Nov 27, 2019 at 4:40
  • \$\begingroup\$ You should have a look at this question: My first implementation of a linked list in C++ \$\endgroup\$ Nov 27, 2019 at 7:34

1 Answer 1

2
\$\begingroup\$

Overview

I don't like that a LL is a node.
A linked list contains nodes. But the list itself is not a node.

The LL missed the rule of three.

LL  x;
LL  y(x); // You did not define a copy constructor
          // But this is still allowed (look up rule of three).
          // Normally this is an advantage. BUT if your class
          // contains RAW owned pointers then this will probably cause UB
          // because both x and y will try and delete the same list.

Most of the linked list functionality for manipulating list would break unless used in very specific ways. So these function should all be private and only used internally.

So I think this code is very broken.

Compiler Warnings:

x2.cpp:59:14: warning: unused parameter 'head' [-Wunused-parameter]
LL(node* head, node* tail) : head(nullptr), tail(nullptr) { printf("LL constructor with assignments \n"); }
         ^^^^        ^^^^
                     ^
x2.cpp:150:11: warning: unused variable 'tmp' [-Wunused-variable]
node* tmp;
      ^^^

Well the unused arguments look like a bug.
The unused variables is just sloppy and should be removed.

But this tells me you compile without warning tunred on. TURN THE ON NOW. Not just for this project but make your default projects settings have a higher warning level and you will catch errors like this.

Personally I treat all warnings as errors (There is a flag to do this in VS). I would advice everybody to do the same. C++ warnings are usually a logical error in your thinking. Fix the code so your code is warning free.


Codes Review

C Headers?

Why are we include C headers in C++ code?

 #include <stdio.h>

Windows specific.

 #pragma once

Sure if you don't want anybody else to use your code and never plan on working on other platforms. I would bet most professional developers (OK I guess I don't have any number on "most" so its hyperbolic but there are a few (not an insignificant)) use Linux.

Learn to use macro guards (until we add better modules to the language and we can stop using this frail old hangover from the 60s).


Const over constexpr

const int UnkD = 999;//Variable for node() default constructor init

The constexpr has been part of the language for a while now. I think the standard advice is to use contexpr where you can and const if not (when creating global state).

Its good that is non mutable :-)

Node

class node {

A node of int is not very interesting. You should have templated this. That way the data object could have been any type. OK my following comments may assume you have templated this (as I assume you will in the long term). That makes the review more interesting.

Secondly its sort of standard to name "user" types with an upper case first letter. This helps you spot variables and types more easily in the code.

Note: "sort of" there is no one true standard. But this is a common practice.

Constructors

Stop adding us-less comments.

// Default Constructor (I moved it so you could see it)
node() : data(UnkD), prev(nullptr), next(nullptr) { printf("default node() ctor called... \n"); } 

I know its a default constructor. Comments rote over time. Unless they are meaningful and useful in some way they will cause confusion when they become out of sync with the code.


Less printing in constructors. At least put them in macros for debugging.

    node() : data(UnkD), prev(nullptr), next(nullptr)
    {
    #if defined(DEBUG)
        printf("default node() ctor called... \n");
    #endif
    }

This one is a tiny bit long for a single line.

    node(const int & d,node* p,node* n): data(d), prev(p), next(n) { printf("node() ctor with args called... \n"); } //Constructor With Args

But that's mostly to do with the print. If you take that out I would not have cared that it was one line.


You were using the initializer list above. Why have you not used it here?

    node(const node& rhs) {
        printf("node() copy ctor called... \n"); 
        data = rhs.data;
        prev = rhs.prev;
        next = rhs.next;
    }; //Copy Constructor  Again with the useless comment.

Here you have let the members be default constructed then copied over them. OK sure if the data type is int the default construction is going to usually be no action. But think into the future when its not an int type. You are pauing to initialize the data object then the first thing you do in the code is copy over it using the assignment operator. That seems like a waste.

Be consistent and always use the initializer list:

    node(const node& rhs)
        : data(rhs.data)
        , prev(rhs.prev)
        , next(rhs.next)
    {
    #if defined(DEBUG)
        printf("node() copy ctor called... \n"); 
    #endif
    };

Learn the copy and swap idiom.

    node & operator = (const node& rhs) { //Copy Operator
        printf("Copy Operator");
        if (this != &rhs) {
            data = rhs.data;
            prev = rhs.prev;
            next = rhs.next;
        }
        return *this;
    }

I would have written like this:

    node& operator=(node const& rhs)
    {
        node tmp(rhs)             // Copy
        rhs.swap(*this);          // Swap
        // Note there is no test for self assignment.
        // This will help because you have no test
        // Optimizes the normal behavior (usually not a self assignment)
        // Does pessimism because self assignment (but that is so rare not a concern)
        return *this;
    }
    void swap(node& other) noexcept
    {
        using std::swap;
        swap(data,    other.data);
        swap(prev,    other.prev);
        swap(next,    other.next);
    }
    friend void swap(node& lhs, node& rhs)
    {
        lhs.swap(rhs);
    }

Why did you leave out the move semantics for a node?

    node(node&& rhs) noexcept
        : data{}
        , prev(nullptr)
        , next(nullptr)
    {
        rhs.swap(*this);
    }
    node& operator=(node&& rhs) noexcept
    {
        rhs.swap(*this); 
        return *this;
    }

Why is the destructor not next to constructor?

    ~node() { printf("~node() dtor called...\n"); delete[] this; };

Place the construction/destruction all in the same place. So you can see it all works together.

Getters/Setters

Normally I say these are bad. But property bag so a resonable implementation. Though I would not particularly bother myself here.

    void set_data(int x) { data = x; }

If you had templatized the data type. Then I would make sure you have a copy and move version of set_data() (snake case!! is this python?).

When returning data you are not modifying the state.

    int get_data() { return this->data; }

Thus you method should be marked const. That way if your node is passed by const reference into a function you could still use the fundtion to get the value out.

If you had templatized the data type. Then I would return by reference (and a version for const reference) to avoid an extra copy. Not really an issue when simply returning an int but for larger types returning by value would cause a copy.

    int&       get_data()       { return data; }
    int const& get_data() const { return data; }

Sure pretty standard.
Would not bother myself.

    void set_prev(node* node) { prev = node; }
    void set_next(node* node) { next = node; }
    node* get_prev() { return this->prev; }
    node* get_next() { return this->next; }

Try not to use this->

You don't need to use this-> in a method. The compiler will get them member (unless you have shadowed it by declaring a local variable of the same name).

BUT shadowing is bad practice. It means you have been lazy in naming your variables and leads to you having to differentiate the two with this->. The trouble here is that if you use the wrong name the compiler can't tell its the wrong one and thus you get no warnings. If you make sure the names are all distinct you can't make this type of error.

And bonus the compiler will warn you about shadowing.


LL

LL is not a node.

class LL: public node {

The LL contains a list of nodes but is not one itself.


Same comments as above on printing.

    LL() : head(nullptr), tail(nullptr) { printf("LL deault constructor \n"); }
    LL(node* head, node* tail) : head(nullptr), tail(nullptr) { printf("LL constructor with assignments \n"); }

Same comment as above put the destructor close to the constructor so we can see we are creating and correctly destroying the object in the same area of the file.

    ~LL() {
        printf("LL destructor \n");
        while (head)
        {
            node* tmp = head->get_next();
            delete[] tmp;
        }
    }

That defiantly looks wrong.

  1. There is no removing links for the chain.
  2. There is no moving of head forward.
  3. You are using delete[] to delete a single item.

You missed the rule of three here.

If you do not define a copy constructor or copy assignment operator then the compiler will generate one for you. The compiler generated version of these functions does a simple shallow copy of the object (which is normally perfect).

But when your object contains RAW pointers this means both object now contain the same pointers. The problem arises when these pointers are owned by the object. This means that the object should be calling delete on the destructor which means both object will call delete on the points (a double delete on a pointer is UB).

List Interface.

The internals (or how head/tail are implemented) is an internal part of LL yet here you are leaking the abstraction of node out of the list.

    void set_head(node* node) { head = node; }
    void set_tail(node* node) { tail = node; }
    node* get_head() { return this->head; }
    node* get_tail() { return this->tail; }

    //Create and Destroy Fucntions
    node* create_node(int d);
    void delete_list(node* list);
    void delete_selected(node* list, int selection);

    //Add and Remove Node Functions
    node* push_front(node* list, node* node);
    node* push_back(node* list, node* node);
    node* pop_front(node* list);
    void pop_back(node* list);
    void append_before(node* list, node* node, int selection);
    void append_after(node* list, node* node, int selection);

    //View List Functions
    void front_list(node* list);
    void back_list(node* list);
    void print_fwd(node* list);
    void print_bwd(node* list);
    void list_selected(node* list, int selection);

When interacting with a linked list I would be more inclined to add values of the data type (int until you upgrade node to be templated). I should simply be able to add values to the list and remove values from the list (and retrieve from the ends I suppose).

I definately would not be allowing the customer to crate and pass pointers around.

My interface would have looked like:

    void push_front(T const& value);    // copy a value to the front.
    void push_front(T&& value);         // move a value to the front.
    void push_back(T const& value);     // copy a value to the back.
    void push_back(T&& value);          // move a value to the back.

    T const& get_front() const;         // get a const reference to the front
    T& get_front();                     // get a reference to the front
    T const& get_back() const;          // get a const reference to the front
    T& get_back();                      // get a reference to the front

    void pop_front();                   // pop the front of the list.
    void pop_back();                    // pop the back of the list.

    bool empty() const;                 // check if the list is empty.
    std::size_t size() const;           // get the size of the list.

   // Ignore iterators for version 1 we can do those after you fix up this

// version and make it better.

This should be a private member.

node* LL::create_node(int d) { return new node{ d, nullptr, nullptr }; }

This is a bug. Same reason as the destructor.

void LL::delete_list(node* list) {
    while (list)
    {
        node* tmp = list;
        list = list->get_next();
        delete[] tmp;
    }
    printf("List Deleted. \n");
}

Note when you have repeated code like this (here and destructor). Then you should be re-using function. Basically the destructor should call this not have the same code repeated. Taht way when you fix an error you only need to fix it in one place.


    // You are not checking that list does not slip of the end of the list.
    while (count != (selection - 1)) {
        list = list->get_next();
        count++;
    }

If list becomes nullptr then calling get_next() will be UB.


Wrong version of delete.

    //delete[] tmp;

It should be

    delete tmp;

This function assumes that list is the head of the list.

node* LL::push_front(node* list, node* node) {
    if (!list) { return node; }

    node->set_next(list);
    list->set_prev(node);  // If list is not the head this overwrites a value.
    list = node;

You also make no effort to update tail.


\$\endgroup\$
1
  • \$\begingroup\$ Thank you for this detailed review and critique of my code. I will work through this and improve upon my code. Once i do that i will respond with it and hopefully have you critique it once more. \$\endgroup\$ Dec 3, 2019 at 19:20

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.