2
\$\begingroup\$

I'm new to C++ programming. I'm experienced in Java and its OOP paradigm. This code works well. I just need to make sure whether it's correct in terms of C++ programming standard.

main.cpp

#include <iostream>
#include "ListNode.h"
#include "LinkedList.h"

using namespace std;

int main(void) {

    LinkedList l;
    ListNode a(10);
    ListNode b(5);
    ListNode c(3);
    l.addFirst(a);
    l.addFirst(b);
    l.addLast(c);

    bool empty = l.isEmpty();

    cout << l.listSize() << endl;

    cout << empty << endl;

    system("PAUSE");
    return 0;
}

LinkedList.h

#pragma once
#include "ListNode.h"

class LinkedList
{
public:
    LinkedList();
    ~LinkedList();
    void addFirst(ListNode &node);
    void addLast(ListNode &node);
    bool isEmpty();
    int listSize();

private:
    ListNode *head;
    ListNode *tail;
    int size;
};

LinkedList.cpp

#include "LinkedList.h"



LinkedList::LinkedList()
{
    head = new ListNode();
    tail = new ListNode();
}


LinkedList::~LinkedList()
{
}

void LinkedList::addFirst(ListNode & node)
{
    if (isEmpty())
    {
        *head = node;
        *tail = node;
        size = 1;
    }
    else {
        node.setNext(*head);
        head->setPrev(node);
        *head = node;
        size++;
    }
}

void LinkedList::addLast(ListNode & node)
{
    if (isEmpty())
    {
        *tail = node;
        *head = node;
        size = 1;
    }
    else
    {
        tail->setNext(node);
        node.setPrev(*tail);
        *tail = node;
        size++;
    }
}

bool LinkedList::isEmpty()
{
    return size == 0;
}

int LinkedList::listSize()
{
    return size;
}

ListNode.h

#pragma once
class ListNode
{
public:
    ListNode();
    ListNode(int val);
    ~ListNode();

    inline void setPrev(ListNode &node) { *prev = node; }
    inline ListNode *getPrev() { return prev; }
    inline void setNext(ListNode &node) { *next = node; }
    inline ListNode *getNext() { return next; }
    inline void setValue(int val) { value = val; }
    inline int getValue() { return value; }

private:
    ListNode *prev;
    ListNode *next;
    int value;
};

ListNode.cpp

#include "ListNode.h"



ListNode::ListNode()
{
}

ListNode::ListNode(int val)
{
    prev = new ListNode;
    next = new ListNode;
    value = val;
}


ListNode::~ListNode()
{
}

Am I do it correctly as usually done by C++ programmer? Or there is something I need to fix. I heavily put my focus on pointer/reference usage.

\$\endgroup\$

migrated from stackoverflow.com Dec 13 '16 at 11:02

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ "Is this considered normal/good programming in C++" depends on how do you define it? \$\endgroup\$ – Sumeet Dec 13 '16 at 10:49
  • 2
    \$\begingroup\$ This probably belongs on codereview. \$\endgroup\$ – Kerrek SB Dec 13 '16 at 10:49
  • \$\begingroup\$ To answer your question simply... There are a lot of things that could be changed to make this better, some less fatal than other. But CodeReview is the place for that. \$\endgroup\$ – DeiDei Dec 13 '16 at 10:52
  • \$\begingroup\$ @hyde right. I'll delete it \$\endgroup\$ – imeluntuk Dec 13 '16 at 10:52
  • 5
    \$\begingroup\$ Your program has memory leaks. First of all you need to properly initialize the pointers in the constructor. And then you need a copy constructor, assignment operator and destructor. See What is The Rule of Three? \$\endgroup\$ – Lundin Dec 13 '16 at 10:59
5
\$\begingroup\$

It's not idiomatic, and definitely not good style.

C++ has evolved along the years, and C++11 brought along a swath of new facilities that good C++ style should now use: they help cut down the number of bugs.

Let's start from the bottom up, with ListNode:

  1. Use std::unique_ptr to manage dynamically allocated memory by default, although here std::shared_ptr/std::weak_ptr is necessary because of the doubly-linked aspect1
  2. Always initialize built-ins with a default value
  3. Use explicit for constructors that may be called with a single argument
  4. Follow the Rule of Zero (no need to define any special member, or if you have to, define them all)
  5. Use const wherever possible
  6. inline is unnecessary if you define a method inside the class definition

1 Doubly linked lists are actually very tricky from a memory management point of view; there are risks of cycles, ...

Putting this altogether:

#pragma once

class ListNode {
public:
    ListNode() = default;

    explicit ListNode(int val): value(value) {}

    int getValue() const { return value; }
    void setValue(int val) { value = val; }

private:
    std::weak_ptr<ListNode> prev;
    std::shared_ptr<ListNode> next;
    int value = 0;
};

Note that by default a Node does not allocate memory for the previous and next nodes. That's because the previous and next fields are supposed to refer to existing nodes, not new ones!

Moving on: we need to be able to set the previous/next fields! We do so by passing std::shared_ptr<ListNode> around:

std::shared_ptr<Node> ListNode::getNext() const { return next; }
void ListNode::setNext(std::shared_ptr<Node> n) { next = n; }

std::shared_ptr<Node> ListNode::getPrevious() const { return previous.lock(); }
void ListNode::setPrevious(std::shared_ptr<Node> p) { previous = p; }

Moving on to LinkedList.

Good encapsulation is about hiding internal implementation details, and therefore the LinkedList interface should NOT expose the fact that there are ListNode instances under the scenes. Instead, it should allow the user to manipulate values.

On top of the previous remarks:

  • prefer empty and size, those are the names used by the Standard containers

For simplicity's sake, I will only demonstrate operations at the head of the list; the tail is symmetric.

#pragma once
#include "ListNode.h"

class LinkedList
{
public:
    bool empty() const { return size == 0; }
    int size() const { return size; }

    void prepend(int value);

private:
    int size;
    std::shared_ptr<ListNode> head;
    std::shared_ptr<ListNode> tail;
};

And now, how do we prepend?

In C++, using new is bad form. C++11 fortunately provides std::make_shared (and C++14 provides std::make_unique). This is a factory method: pass the type as template argument, pass the arguments to be forwarded to the constructor of this type as regular arguments, and low and behold it returns an instance of this type wrapped in a shared_ptr.

void LinkedList::prepend(int value) {
    auto node = std::maked_shared<ListNode>(value);

    if (empty()) {
        head = node;
        tail = node;
        size = 1;
        return;
    }

    node->setNext(head);
    head->setPrevious(node);
    head = node;
    size += 1;
}

It's relatively simple. I'll let you figure out how to unlink a node (when removing it), if done wrong you could leak memory.

Also, a final parting remark to get your brain churning, there are two issues with this implementation:

  • A copy of LinkedList is a shallow copy: both original and copy share the nodes, due to the usage of shared_ptr. You may either prevent copying (using LinkedList(LinkedList const&) = delete;) or you need to actually implement the copy constructor... and as per the Rule of Five this means all other special members.
  • The default generated destructor of ListNode may cause a stack overflow as it recurses; I suggest to actually handle this issue at LinkedList level, an assert in ListNode that next is null in the destructor will help with identifying the places where you did not correctly unlink it.
\$\endgroup\$
  • 1
    \$\begingroup\$ I disagree with the use of smart pointers in the case. The point of the class 'LinkedList' is memory management (there is no other business logic). Using one technique of memory management (Smart Pointer) to implement another type of memory management (Containers) is counter productive IMO. Also do nodes belong to other nodes or to the container as a whole? \$\endgroup\$ – Martin York Dec 14 '16 at 6:00
  • \$\begingroup\$ @LokiAstari: Then we disagree. I personally see no reason not to use smart pointers when the logic you need can be expressed with them. I much prefer NOT mixing class invariants and memory management in a single class, this helps keeping the few classes that have to do memory management small enough that I can convince myself that they do it right (no leak, no dangling pointer); for me, LinkedList has enough invariants to manage on its own that doing management right (in the presence of exceptions) is really a burden that it should offload to another self-contained class. \$\endgroup\$ – Matthieu M. Dec 14 '16 at 7:40
  • \$\begingroup\$ Invariants and Memory management. What does that mean! Even smart pointers have invariants. And the point of the container is memory management. If we consider the standard as good examples of implementation techniques then not using smart pointers is OK. Though unique_ptr imposes no overheads shared_ptr definitely does impose an overhead (time and space) and implementing a doubly linked list (as in this example) requires the use of a shared_ptr (as two nodes will own each other node (or some usage of weak_ptr)). This example codereview.stackexchange.com/a/126007/507 shows its not hard. \$\endgroup\$ – Martin York Dec 14 '16 at 8:15
  • \$\begingroup\$ @LokiAstari: The point that smart pointers have invariants is exactly the one I am making. I advise to use a Divide & Conquer approach: have the smart pointers handle the memory management issue (to avoid dangling pointers) and concentrate on maintaining the list invariants (that each node is the next node of its previous and the previous node of its next, that the size is correct, etc...). Of course, using shared_ptr there's some overhead. By the "correctness first, performance second" principle, I'd argue for debugging the implementation before tackling this overhead... \$\endgroup\$ – Matthieu M. Dec 14 '16 at 8:31
  • 1
    \$\begingroup\$ @Nick: The stack overflow is duly noted at the bottom of the answer. A simple: while (!empty()) { pop_front(); } solves the issue without invoking manual memory management though. \$\endgroup\$ – Matthieu M. Dec 15 '16 at 7:42
5
\$\begingroup\$

Two things:

  • You need to use a lot of consts.

Example:

    void setNext(ListNode &node)

    void setNext(const ListNode &node)
  • You call to new in some places of your code but never call to delete
\$\endgroup\$
4
\$\begingroup\$

Since you are using a container, there's really no reason to expose the ListNode class to your users, especially since all it does is hold a value. Instead, you can modify your addFirst and addLast functions to take the value directly and create a ListNode internally:

void addFirst(int val)
{
     ListNode node = new ListNode(val);
     if (isEmpty())
     {
         *head = node;
         *tail = node;
         size = 1;
     }
     else {
         node.setNext(*head);
         head->setPrev(node);
         *head = node;
         size++;
     }
}

Now, if later on you decide to change the way ListNode works, you can change it internally without having to change any code. It's also easier on the user:

LinkedList myList;
myList.addFirst(5);

Lastly, it means that you control how the ListNode objects are actually created, so you can easily control how they are deleted. By leaving their creation to the user, the user might accidentally delete a reference to one and leave your list with a dangling reference. For example, if the user wrote a function like:

LinkedList* createList(std::vector<int> values)
{
    LinkedList* myList = new LinkedList;
    for (int i = 0; i < values.size(); ++i)
    {
        ListNode node(values[i]);
        myList -> addLast(node);
    }
    return myList;
}

All of the node objects were declared in the for scope, so once that exits they become invalid. The user might pick up on the problem if they notice addLast takes a reference, or if your documentation explicitly states that the ListNode objects need to be kept valid, but usually container classes take that burden off the of the user.

\$\endgroup\$
1
\$\begingroup\$

Next to what @GutiMac already remarked:

Doing really different things in overloaded constructors is weird.

I would expect the constructor for ListNode to be:

ListNode::ListNode(int val = 0)
{
    prev = nullptr;
    next = nullptr;
    value = val;
}

If your node has an invalid value by default, this should be filled in in some way. Make sure to initialize everything.

Make your ListNode non-copyable/movable by deleting copy constructor, move constructor, assignment operator and move assignment operator because copying would mean that the new list-node points to the same prev and next. You can always make a new node with the same value by giving the value to the constructor.

Your LinkedList still needs some find/iterator functionality and some remove functionality to be a useful container and the destructor should clean up the nodes.

As it is now, when copying the linked list, two instances will now point to the same data. Either avoid copying (see LinkNode) or make a deep copy of all the nodes in the copy constructor.

Also, but this can be an extension: containers are usually made as templates. There is not that much difference except that templates should be fully implemented in the header file.

Lastly, while it is nice to make your own containers as exercise, in production code, use std::list

\$\endgroup\$
0
\$\begingroup\$

Couple of things:

std namespace

using namespace std;

Do not use this. Type "std::" where is needed:

std::cout << empty << std::endl;

std::endl

Do not use std::endl. It does implicit flush. This hurts the performance a lot. Use \n instead:

std::cout << empty << '\n';

system()

Don't use system("PAUSE");.

This forks new shell (probably in your case "cmd.exe") and executes via the shell command "pause".

I do not know what C++ function you should use, but probably getchar will do. However it is C function.

http://www.cplusplus.com/reference/cstdio/getchar/

For this you need to add #include <cstdio>.

pragma once

I see you have used #pragma once. It is well supported, but it is not standard. Try use "include guard" it is what standard way.

https://en.wikipedia.org/wiki/Include_guard

main()

This is perfectly OK:

int main(void){
}

However I would use this instead, even I do not use any arguments. This is because argv[0] is always set.

int main(int atgc, char **argv){
}

return 0 from main()

In latest C++, return 0; from main() is optional. Since is there, do not remove it.

const method

bool LinkedList::isEmpty();

should be const, e.g.

bool LinkedList::isEmpty() const{
   return size == 0;
}

Also move this into the .h file. It is so short.

destructor

Your destructor is empty - remove it completely.

default constructor in ListNode

default constructor in ListNode is empty. You can not remove it, because you have one more constructor. However if you have C++11, you can do:

class ListNode
{
public:
    ListNode() = default;
    ListNode(int val);
//...

inline methods in ListNode

inline methods are present into the class definitions. Remove all "inline" keyword, it does not needed.

However ListNode is so small, I would merge it in .h file like this:

class ListNode
{
public:
    ListNode() = default;

    ListNode(int val){
        prev = new ListNode;
        next = new ListNode;
        value = val;
    }

    void setPrev(ListNode &node) {
        *prev = node;
    }
    ListNode *getPrev() {
        return prev;
    }
    void setNext(ListNode &node) {
        *next = node;
    }
    ListNode *getNext() {
        return next;
    }
    void setValue(int val) {
        value = val;
    }
    int getValue() {
        return value;
    }

private:
    ListNode *prev;
    ListNode *next;
    int value;
};

constructor class member "initializers"

I may be using incorrect term, but constructor better be like this:

    ListNode(int val):
        prev(new ListNode),
        next(new ListNode),
        value(val){
    }

possible error:

constructors / destructor of ListNode does not add-up. there is some error somewhere.

possible error in constructor

probably there is an error? why you create prev and next here? I believe you need to set those point to something else, not to allocate new nodes?

or possible error in default constructor and destructor

you have default constructor. what is it purpose? just to have one? it does not initialize prev and next. You probably want to remove it.

probably destructor wants to free the memory? I said to remove it, because it does nothing.

or possible benefit of using "std::unique_ptr"?

you probably want to use automatic memory management using "std::unique_ptr" (C++11 feature)

\$\endgroup\$
  • \$\begingroup\$ "Some people reports it is even faster than #pragma once." [citation-needed] Who says this? If anything, #pragma once will be faster in parsers that special-case it. But nowadays, every toolchain worth its salt recognizes and optimizes both idioms. Also, it's perfectly valid for the entry point to have the signature int main() if you don't need the arguments. \$\endgroup\$ – Cody Gray Dec 13 '16 at 15:09
  • \$\begingroup\$ no idea, saw this on stackoverflow . I never use pragma once. do you think I should remove this? \$\endgroup\$ – Nick Dec 13 '16 at 15:11
  • \$\begingroup\$ It's perfectly valid to mention that it is non-standard, albeit widely supported. That's good for someone to know. But yes, I'd remove the claim about one or the other being faster. Or link to the original source of the claim. \$\endgroup\$ – Cody Gray Dec 13 '16 at 15:12
  • \$\begingroup\$ about main(). I know main() works, but is wrong.- you always have at least one parameter argv[0] - the program name \$\endgroup\$ – Nick Dec 13 '16 at 15:30
  • 1
    \$\begingroup\$ No, you really don't. The C++ language standard explicitly allows two declarations of main: one with int and char*[] parameters, and the other with no parameters. If argv is one of the parameters, argv[0] generally contains the name of the program, but this is not even guaranteed! Exactly what the arguments are is implementation-dependent. \$\endgroup\$ – Cody Gray Dec 13 '16 at 15:33

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.