6
\$\begingroup\$

How is this designed so far?

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <memory>
#include <iostream>

template <typename T> using ptr = std::shared_ptr<T>;

template <typename V>
class LinkedList
{
private:
    class Node
    {
    private:
        V data;
        ptr<Node> next;
    public:
        Node() : next{} {}
        Node(V _data) : next{}, data{_data} {}
        ptr<Node>& getNext(){
            return this->next;
        }
        V getData(){
            return this->data;
        }
    };

    ptr<Node> head;
    ptr<Node> tail;
    size_t _size;

public:

    LinkedList() : head{}, tail {}, _size{} {}

    void add(V _data){
        auto _tmp = std::make_shared<Node>(_data);
        if(isEmpty()){
            head = _tmp;
            tail = _tmp;
        } else {
            tail->getNext() = _tmp;
            tail = _tmp;
        }
        _size++;
    }

    bool isEmpty(){
        if(head == nullptr) return true;
        else return false;
    }

    V operator[](int index){
        int _c {};
        ptr<Node> tmp = head;
        while(tmp!=nullptr){
            if(_c == index){
                break;
            }
            tmp = tmp->getNext();
            _c++;
        }
        return tmp->getData();
    }

    void addFirst(V _data){
        auto _tmp = std::make_shared<Node>(_data);
        if(isEmpty()){
            _tmp->getNext() = head;
            head = _tmp;
            tail = _tmp;
        } else {
            _tmp->getNext() = head;
            head = _tmp;
        }
        _size++;
    }

    template <typename V>
    void insertAfter(int index, V _data){

        auto _tmp = std::make_shared<Node>(_data);
        std::shared_ptr<Node> _curr;
        std::shared_ptr<Node> _afterIndex;

        if(index<0 || index > size()-1){std::cerr << "__INDEX_OUT_OF_RANGE__" << std::endl;}
        else {
            int _c {};
            ptr<Node> tmp = head;
            while(tmp!=nullptr){
                if(_c == index){
                     _curr = tmp;
                     _afterIndex = _curr->getNext();
                     break;
                }
                tmp = tmp->getNext();
                _c++;
            }

            _curr->getNext() = _tmp;
            _tmp->getNext() = _afterIndex;
            _size++;
        }
    }

    void traverseList(){
        {
            ptr<Node> tmp = head;
            while(tmp!=nullptr){
                std::cout << tmp->getData() << std::endl;
                tmp = tmp->getNext();
            }
        }

    }

    size_t size(){ return _size; }
};

#endif // LINKEDLIST_H

#include "linkedlist.h"
#include <string>
int main(){

    auto list = std::make_shared<LinkedList<std::string>>();

    list->addFirst("Bob");
    list->add("Carl");
    list->add("Mario");
    list->add("Elliot");
    list->addFirst("Neo");
    list->insertAfter(0,"I'm inserted after " + (*list)[0]);

    for (int i {} ; i < list->size(); ++i) {
        std::cout << (*list)[i] << std::endl;
    }

    return 0;
}
\$\endgroup\$
12
\$\begingroup\$

Namespace

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

The term "linked list" is a common term. So I would expect somebody out there is already using the macro LINKEDLIST_H. When somebody uses that library and your library then you will get some funny interactions.

As a result I would make the include guards a little more unique. When I define header guards they include the full namespace and the the file name in the include guard.

Which brings me to namespace. All your work is in the global namespace. Which can lead to collision in names (Again LinkedList is a common type name). So creating a unique namespace for your code could be useful (I like the Java method of using your domain name).

#ifndef THORSANVIL_UTIL_LINKED_LIST_H
#define THORSANVIL_UTIL_LINKED_LIST_H

namespace ThorsAnvil
{
     namespace Util
     {

class LinkedList
{
};

     }
}
#endif

Containers Vs Smart Pointers

There are two common techniques for managing dynamic memory: Containers and Smart Pointers. Since the job of the container is to perform memory management so delegating this to Smart pointers is counter productive.

Secondly shared_ptr should not be your first choice of smart pointer. The shared pointer has significant overheads.

template <typename T> using ptr = std::shared_ptr<T>;

Given the choice I would prefer std::unique_ptr when you are expressing ownership, but simply use a normal RAW pointer inside function where no owner knowledge is needed.

Private Membership

template <typename V>
class LinkedList
{
private:
    class Node
    {

The class LinkedList::Node is exposed as public. Exposing this class exposes implementation details. Exposing implementation details makes your class much more brittle and harder to change.

Constructor

default constructor

    public:
        Node() : next{} {}

A default constructor. Do you need it. This can only be used when the object type V os default constructible. Conversely if the type V is not default constructible this constructor can not be used. Which would mean that certain portions of your class are unusable.

Construction

        Node(V _data) : next{}, data{_data} {}

This constructor passes _data by value. This means _data is copied into the function then it also copied again into the member. So you have multiple copies. Normally I would pass by const reference to avoid at least one copy.

Additionally in C++11 we introduced move semantics. This can thought of as an optimized copy. You should try and define your class to use move semantics so that you can remove the additional copy.

Also introduced in C++11 were variadic templates and perfect forwarding. This can be used to build objects in place using their own constructors very easily. This allows us to build the objects into the container with creating an external copy.

So if we put all three of these together I would write the Node class like this.

        struct Node
        {
            Node*   next;   // not owned.
            V       data;

            Node(V const& data)
                : next(nullptr)
                , data(data)
            {}
            Node(V&& data)
                : next(nullptr)
                , data(data)
            {}
            template<typename... Args>
            Node(Args&& args...)
                : next(nullptr)
                , data(std::forward<Args>(args)...)
            {}
        };

Head Tail Vs Sentinel

    ptr<Node> head;
    ptr<Node> tail;

Sure you can use a singly linked list and head and tail. Personally I prefer to use a doubly linked list and a sentinel (there are several other questions on code review where I explain this technique in detail).

Using a sentinel object allows you to write code without having to worry about nullptr this can considerably simplify the code.

The additional benefit (of the sentinel technique) is that you have a node in your chain that can be used by the end iterator (one past the end of the list).

Const member functions

    size_t size(){ return _size; }

    bool isEmpty(){
        if(head == nullptr) return true;
        else return false;
    }

Functions that do not mutate the state of the object should be marked const. Note: When passing around large objects to functions it is quite common to pass them by const reference. This means you can only call const methods on the object.

    size_t size() const { return _size; }

if test anti pattern

    bool isEmpty(){
        if(head == nullptr) return true;
        else return false;
    }

This is an anti pattern. There is no need to perform a test and return true/false. Simply return the value of the test.

    bool isEmpty() const
    {
        return (head == nullptr);
    }

Error

What happens when index is greater than size?

    V operator[](int index){
        int _c {};
        ptr<Node> tmp = head;
        while(tmp!=nullptr){
            if(_c == index){
                break;
            }
            tmp = tmp->getNext();
            _c++;
        }

        // I bet this de-reference a null ptr
        // Does it.
        return tmp->getData();
    }

Name your function appropriately

This may traverse the list. But that is not what it is actually doing. The traverse is just a side effect of the action you are taking.

    void traverseList(){
        {
            ptr<Node> tmp = head;
            while(tmp!=nullptr){
                std::cout << tmp->getData() << std::endl;
                tmp = tmp->getNext();
            }
        }

To me this looks like a print function name it as such. Also it always prints to std::cout. Why not pass the stream you want to print to (it can default to std::cout.

     void printList(std::ostream& str = std::cout)
     {
         // Code as before
     }
     // Then just for giggles we add a friend function to make
     // printing more C++ like.

     friend std::ostream& operator<<(std::ostream& s, LinkedList const& ll)
     {
         ll.printList(s);
         return s;
     }
\$\endgroup\$
  • \$\begingroup\$ Brilliant! This was EXTREMELY helpful. Thank you so much! \$\endgroup\$ – Oleg Nykolyn Sep 2 '16 at 10:20
4
\$\begingroup\$

Only a couple minors for now:

  1. You should make consistent use of spaces, e.g. you have while(tmp!=nullptr) vs if(_c == index) - generally sprinkling a few spaces around makes the code easier to read.
  2. isEmpty() can be simplified to return head == nullptr.
  3. I'd classifiy the implementation for [] as broken - if you pass in an index which is out of range then tmp will be nullptr and you invoke undefined behaviour (most likely you will trigger an access violation).
  4. In insertAfter you duplicate the code from []
  5. In insertAfter you do a check whether index is valid however the implementation is questionable. You should throw an exception instead of writing to stderr - this way you can leave the user of your data structure to deal with invalid input.
  6. Similar traverseList - instead of writing to stdout it should accept a callback function which gets called for every entry. This way the caller can do whatever suits best.
  7. The method names should match those of standard containers so people familiar with them will bve immediately familiar with your data structure, so like empty instead of isEmpty, or push_front instead of add_first.
  8. Next step would be to add iterator support.

Update: One other thing to mention is that the index access operator has linear complexity. This makes your example loop:

    for (int i {} ; i < list->size(); ++i) {
        std::cout << (*list)[i] << std::endl;
    }

quadratic complexity which is probably not what the user of the structure would expect. This is probably one of the reasons why std::list doesn't implement indexed access (neither does C#'sLinkedList for example).

Also I noticed that you initialize variables of primitive types like this:

int _c {}

I don't know if this just the latest "hip thing" with C++14 but I find

int _c = 0;

much clearer to read since it's explicit and will have the same effect. Just because a language feature exists doesn't meant you have to use everywhere.

\$\endgroup\$
2
\$\begingroup\$

Your indexing operator:

V operator[](int index){

Should probably handle an invalid index (I'd suggest throwing something like an out of range exception). At the moment, you're going to be triggering a null pointer reference.

You keep going until tmp is nullptr:

while(tmp!=nullptr){

Then return a value from that nullptr:

return tmp->getData();

Which is bad...

\$\endgroup\$

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.