2
\$\begingroup\$

This is a working linked list that will be used as a vector. Instead of using dynamic arrays, I am using a linked list. I would like to see a more concise solution without utilizing the STL.

SimpleVector.h

class SimpleVector
{

public:

    SimpleVector(){
        head = nullptr;
    }
    SimpleVector(const SimpleVector &);
    ~SimpleVector();

    void appendNode(const int value);
    void insertNode(const int value);
    int getElementAt(const int index);
    void displayVect();

private:

    struct Node
    {
        int value;
        Node *next;
    };

    Node *head;

};

Copy constructor implementation

SimpleVector::SimpleVector(const SimpleVector &obj)
{

    Node *oldNodePtr;
    Node *newNodePtr;

    // Initialize head to nullptr incase obj is empty
    this->head = nullptr;

    // Position oldNodePtr to the head of the list.
    oldNodePtr = obj.head;

    if (oldNodePtr != nullptr) {

        // Create new node. This is the first node in the new list
        Node *newNode = new Node;
        newNode->value = oldNodePtr->value;

        // Set head to new node address
        this->head = newNode;

        newNodePtr = newNode;

        oldNodePtr = oldNodePtr->next;

        // While oldNodePtr points to a node, traverse the list.
        while (oldNodePtr->next != nullptr) {

            Node *newNode = new Node;
            newNode->value = oldNodePtr->value;
            newNodePtr->next = newNode;
            newNodePtr = newNodePtr->next;

            oldNodePtr = oldNodePtr->next;
        }

        Node *lastNode = new Node;
        lastNode->value = oldNodePtr->value;
        newNodePtr->next = lastNode;
        lastNode = nullptr;
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ Using a linked list as a vector sounds like a bad idea. It would have poor performance characteristics. \$\endgroup\$ Mar 25, 2016 at 23:04
  • \$\begingroup\$ That ok. It's just an experiment. Not actually going to be used. \$\endgroup\$ Mar 25, 2016 at 23:06
  • 1
    \$\begingroup\$ @RitchieShatter: Just call it a linked list. What you are doing is implementing a container that happens to use a linked list underneath the hood. \$\endgroup\$ Mar 26, 2016 at 17:02
  • 1
    \$\begingroup\$ @RitchieShatter: One of the .. Sorry I mean THE MOST important part of C++ is knowing the type information about objects. You make it really hard to review because you only have a part of your code and thus we have to guess at the types of some objects: this->head for example. So next time when only posting a method also include a section with the member variables so we can see their types. \$\endgroup\$ Mar 26, 2016 at 17:04
  • \$\begingroup\$ Your correct. I added the specification file. \$\endgroup\$ Mar 26, 2016 at 17:28

2 Answers 2

4
\$\begingroup\$

A standard dummy node trick (along with appropriate Node::Node constructors) greatly simplifies the code:

    SimpleVector::SimpleVector(const SimpleVector &obj)
    {
        Node dummy;

        for (Node * o = obj.head, *n = &dummy; o; o = o->next) {
            n->next = new Node(o->value);                
            n = n->next;
        }

        this->head = dummy.next;
    }

To utilize STL, you need to implement iterators.

\$\endgroup\$
2
  • \$\begingroup\$ Couple of issues with dummy. 1) The value has to be default construable 2) The cost of constructing the value may be non neglable. Now with the current implmentation it uses int for the value so these don't apply. But presumably the OP is going to convert this into a generic container at some point. \$\endgroup\$ Mar 26, 2016 at 17:33
  • \$\begingroup\$ @LokiAstari Proper constructors are mentioned. \$\endgroup\$
    – vnp
    Mar 27, 2016 at 5:00
4
\$\begingroup\$

Placement of '*' and '&'

In C++ the '*' and '&' are part of the type information and usually belong beside the type not the variable. This is the opposite of normal behavior for C.

const SimpleVector &obj

Is more normally written as:

const SimpleVector&   obj

Personally I prefer to put the const on the right. There are one or two corner cases were this makes a difference and when doing complex C++ templates this has saved my butt.

SimpleVector const&   obj

Remember const always binds to the left, unless it is on the very left then it binds right. So the above two have the same meaning.

Some people argue that they put the '*' next to the variable because there is the use case.

int*   x,y;

Here x is a pointer and y is not. My counter argument is that you should never declare more than one variable per line. This is echoed in every coding standard I have ever seen. And nobody will let you get through a code review with two variables on a line. So this is invalid straw man argument.

Initialize all members in the intializer list.

SimpleVector::SimpleVector(const SimpleVector &obj)
    : head(nullptr) 
    // All members should be initialized here.
    // It is a good habit to get into
    // So that a quick glance shows that you have made sure
    // that all members are in a nice valid state
{

Declare an initialize members at the same point.

    Node *oldNodePtr;

    // Many lines later.

    oldNodePtr = obj.head;

Why not use a single line.

    Node*       oldNodePtr = obj.head;

This also goes to the point of declaring your variables as close to the point of first use as you can. This is not ancient C where you need to declare all the variables at the top of the function.

This has several benifits

  1. You can see the type at the point where you are using the variable.
  2. When an object has a constructor/destructor they are only being run at the point where they need to. If you exit early then the constructor is not even run.

Don't manually copy object.s

The object should know how to copy itself.

        // Create new node. This is the first node in the new list
        Node *newNode = new Node;
        newNode->value = oldNodePtr->value;

This should be:

        Node* newNode = new Node(*oldNotePtr);

By moving this code out of the Node you are opening yourself up to a whole bunch of potential maintenance problems. If you keep this in the Node class then if you modify the way Node is used then you will automatically update the way it is copied. With your current implementation you have to search for all the places that Node is used and update them as well.

Don't do extra work

   {
        Node *lastNode = new Node;

        // Why are you setting this to null
        // it leaves scope and no longer exists 
        // after the next line and thus this is
        // just superfluous work that has no meaning.
        lastNode = nullptr;
   }

I would have simplified to:

SimpleList::SimpleList(SimpleList const& rhs)
    : head(nullptr)
{
    Node** tailPtr = &head;

    for(Node* list = rhs.head; list; list = list->next)
    {
        (*tailPtr) = new Node(*list);
        tailPtr = &((*tailPtr)->next);
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Forgive my ignorance but why did you use a double pointer here? What is the benefit? Thank you. \$\endgroup\$ Mar 28, 2016 at 23:07
  • 1
    \$\begingroup\$ @RitchieShatter: Because I want to update what it points at. (*tailPtr) = new Node(*list); Notice I dereference (thus the thing it points at) is being updated with the result of the new expression. If I just used a single pointer I could update my pointer but what I want to do is update the pointer that I am pointing at. \$\endgroup\$ Mar 29, 2016 at 2:14

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.