2
\$\begingroup\$

I'm new to C++ and trying to learn by implementing data structures in it.

Is the code below the most efficient way of implementing the data structure in C++? Does it conform to C++ standards, and how readable is it?

#include <iostream>

class Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = nullptr;
    }
};

class LinkedList
{
public:
    Node *head;
    Node *tail;
    int length;
    LinkedList()
    {
        this->head = nullptr;
        this->tail = nullptr;
        this->length = 0;
    }

    void add(int data);
    void add(int data, int position);
    void delete_node(int position);
    int get_length();
    void print();
    int get_first();
};

void LinkedList::add(int data)
{
    Node *node = new Node(data);

    if (this->head == nullptr)
    {
        this->head = node;
    }
    else
    {
        this->tail->next = node;
    }
    this->tail = node;
    this->length = this->length + 1;
}

void LinkedList::add(int data, int position)
{
    Node *temp_head = this->head;
    Node *node = new Node(data);
    int i = 0;
    while (i < this->length)
    {
        if (i == position - 1)
        {
            node->next = this->head->next;
            this->head->next = node;
        }
        this->head = this->head->next;
        i++;
    }
    this->head = temp_head;
    this->length = this->length + 1;
}

void LinkedList::print()
{
    Node *temp_head = this->head;
    while (this->head != nullptr)
    {
        std::cout << this->head->data << '\n';
        this->head = this->head->next;
    }
    this->head = temp_head;
}

int LinkedList::get_length()
{
    return this->length;
}

int LinkedList::get_first()
{
    return this->head->data;
}

int main()
{
    LinkedList *llist = new LinkedList();
    llist->add(0);
    llist->add(1);
    llist->add(3);
    llist->add(4);
    llist->add(2, 2);
    llist->print();
    std::cout << "Length: " << llist->get_length() << '\n';
    std::cout << "First Element : " << llist->get_first() << '\n';
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ If you are new to a language, you should add the beginner tag to your question. Reviewers take this tag into account. \$\endgroup\$ Commented Aug 4, 2019 at 20:39
  • 1
    \$\begingroup\$ Have a look at: codereview.stackexchange.com/questions/125955/… and my follow up. That should give you some hints. \$\endgroup\$ Commented Aug 13, 2019 at 1:03

2 Answers 2

Reset to default
4
\$\begingroup\$

In addition to the above, these are my comments:

API completeness

One of the attractive features of a linked list is adding elements in O(1) anywhere in the list, given a Node*. But this API only allows for adding new elements in the middle in O(n) via add(int, position). I would at least allow a method of adding after a node, given a Node*.

Encapsulation

Usually you don't want classes to have public members (one exception is static constexpr). So move head, tail and length to private.

Code compactness

  1. You don't need the constructor, because you can initialize the members using {} in their declaration. prefer {}
  2. Conceptually, add(int data) is a private case of add(int data, int position), so the code should reflect that IMO.

Readability

  1. Since the length cannot be negative, it's better to use size_t instead of int.

  2. Const correctness. Add the const specifier at the end of functions that don't change the list, like: getters, print() etc: int get_length() const;. Note that this would prevent changing head in print() - which is good because you don't expect the list to change if you're merely printing it.

  3. Use the shorter length += 1; notation.

Reusability

One big thing to remember when writing a container is to templatize it. Since you're now doing your first steps in C++ I understand that you want to take one step at time, so just int as the type is fine.

template<typename T>
class LinkedList
{
...
}

Memory management

  1. In add() use a self-managed std::shared_ptr instead of raw pointers and new. Read about smart pointers, they're one of the best features in C++11.
  2. I don't see a reason for the new LinkedList(); in main(). Just a LinkedList list; would be enough.

Efficiency

In add(int data, int position), why continue traversing the while loop if you have already added the element?

Unit tests

Testing is really important. I would suggest using a testing framework (I work with gtests) and writing some unit tests. Going through each public method and thinking how to test it - by itself, or in conjunction with other functions - and writing unit tests to prove correctness is a sure way to increase quality.

Note that the implementation for delete_node() is missing. Make sure that it reuses the node search code that add(data, position) has.

\$\endgroup\$
4
\$\begingroup\$

  • C++ is not Java. You may safely get rid of all this->.

  • The client doesn't need to know about Node. Make it an inner class of the LinkedList.

  • The ~LinkedList() destructor is missing. You should also consider (or prohibit) the copy constructor, operator=, and move constructor.

  • add(int data, int position) may silently leak memory. If the position is too large, the created node is not linked into the list, and is lost. Also, there is no way to prepend a node.

  • I don't like the temp_head approach. Better leave the head alone, and iterate using a cursor variable, e.g.:

    void LinkedList::print() {
    Node * cursor = head;
    while (cursor) {
        std::cout << cursor->data << '\n';
        cursor = cursor->next;
    }
}

    At least, there is no need to restore head.

    Ditto for add.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ That's a prime place for for: void LinkedList::print() const { for (auto p = head; p; p = p->next) std::cout << p->data << '\n'; } \$\endgroup\$ Commented Aug 5, 2019 at 18:00

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.