3
\$\begingroup\$

This is a follow-up to the previous question: Implementation of the linked list data structure in C++

I've tried to improve the design of the previous code by fixing some indexes that could go out of range and cause the dereferencing of a nullptr, and minor changes for compactness and elegance. However, I'm not sure about the final result (in all honesty I'm satisfied because this is my second week working with C++), so that's why I'm asking for feedback.

#ifndef NYO_UTIL_LINKEDLIST_H
#define NYO_UTIL_LINKEDLIST_H

#include <memory>
#include <iostream>

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

namespace Nyo{
namespace Util{

template <typename V>
class LinkedList
{
private:

class Node
{
private:
    V data;
    ptr<Node> next;
public:
    Node(const 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(const V& _data){

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

    if(isEmpty()){

        head = (_tmp);
        tail = (_tmp);

    } else {
        tail->getNext() = (_tmp);
        tail = (_tmp);
    }
    _size++;
}

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

V operator[](int index){

    if(index < 0 || isEmpty() || index > size()-1){ return {};}

    else {

        int _c {};
        ptr<Node> tmp = (head);

        while(tmp!=nullptr){

            if(_c == index){
                break;
            }
            tmp = (tmp->getNext());
            _c++;
        }

        return tmp->getData();
    }
}

void pushFront(const 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 insertAt(int index, const V& _data){

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

    if(index<0 || index > size()){std::cerr << "__INDEX_OUT_OF_RANGE__" << std::endl;}

    else if (index==0) {
        pushFront(_data);
    }

    else {

        int _c {};
        ptr<Node> tmp = (head);

        while(tmp!=nullptr){
            if(_c == index-1){
                _curr = (tmp);
                _afterIndex = (_curr->getNext());
                break;
            }

            tmp = (tmp->getNext());
            _c++;
        }

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

    }

}
bool find(const V& data){

    bool _isIn;
    for(ptr<Node> tmp {head}; tmp; tmp = tmp->getNext()){
        if(tmp->getData() == data) {
            _isIn = true;
            break;
        }
        else _isIn = false;
    }
    return _isIn;
}

void display(){

    ptr<Node> tmp = (head);
    std::cout << "[->] " ;

    while(tmp!=nullptr){
        std::cout << tmp->getData() << " ";
        tmp = (tmp->getNext());
    }

    std::cout << std::endl;

}

size_t size() const { return _size; }

V deleteLast(){

    int _c{};
    ptr<Node> _tmp;
    ptr<Node> _lastValue;
    _tmp = (head);

    if(size()!=0){

        while(_tmp!=nullptr){

            if(size() == 1){
                _lastValue = (head);
                head = nullptr;
                tail = nullptr;
                head = (tail);
                _size--;
                return _lastValue->getData();

            }

            else if(_c == size()-2){
                _lastValue = (_tmp->getNext());
                _tmp->getNext() = nullptr;
                tail = (_tmp);
                _size--;
            }
            _tmp = (_tmp->getNext());
            _c++;
        }

        return _lastValue->getData();

    } else {

        return {};

    }
}
};
}
}
#endif // LINKEDLIST_H




#include "linkedlist.h"
#include <string>

int main(){

    auto list = std::make_unique<Nyo::Util::LinkedList<std::string>>();

    list->pushFront("Bob");
    list->add("Carl");
    list->add("Mario");
    list->add("Elliot");
    list->pushFront("Neo");
    list->insertAt(0,"Sara");
    list->insertAt(4,"Marek");

    list->display();

    do {
        std::cout << "Deleting " << list->deleteLast() << std::endl;
        list->display();
    } while (!list->isEmpty());


    list->pushFront("fSociety");
    list->pushFront("Skyler");
    list->add("Say_my_name");
    list->display();

    std::cout << "Printing first and last element: " << (*list)[0] << " " << (*list)[static_cast<int>(list->size())-1] << std::endl;



    if(list->find("fSociety")){
         std::cout << "__ITEM_FOUND__" << std::endl;
    }


    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I would use if (isEmpty()) { instead of if(isEmpty()){. Also, no need to use else on an if that always does return. I'd be more consistent in the usage of blank lines. Also, I'd leave off braces for one-liner ifs: if(_c == index) { break; } --> if (_c == index) break; Personally, I dislike "cuddled" else: } else { and I'd move else { to the next line. And, where are the comments??? \$\endgroup\$ – Craig Estey Sep 2 '16 at 20:54
3
\$\begingroup\$

namespace Usage

This type ptr is in the global namespace. Why not make it part of your namespace? All your definitions should be in your namespace.

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

I note you are still using shared pointers for memory management.

Identifier Nameing

I hate the use of _ as a prefix to an identifier. Though you are not actually breaking any rules. Do you actually know the rules about using a prefix _ on an identifier.

Personally I find that people that use _ are using it to help them identify certain names for certain purposes. Personally I see this as a crutch to actual using good meaningful names for these identifiers.

Style

This looks funny.

    tail = (_tmp); // why the braces?

Prefer prefix increment

_size++;

When using integer it makes absolutely no difference. But when you are using user defined types (like iterators) it can. The default implementation of an iterator the prefix increment is more efficient than the postfix version.

Also you want to write your code so that it is type agnostic. If during maintenance you decide to change a type you should not also have to run through the code making sure that you are doing things the most efficient way (that should be automatic; just change the type).

As a result it is preferable to train yourself to always use the prefix increment (make it a habit). That way you will always be using the most efficient version of increment no matter what the type and situation.

Default Constructing V

You fixed the bug in you access operator operator[]. But you have done so in a way that means your type V must be default constructable.

if(index < 0 || isEmpty() || index > size()-1){ return {};}

You are constructing a temporary V object that is returned.

Accessing beyond the end is an error you should treat it as such. Now you can treat this in several ways. The easiest way is to to throw an exception. This is the way I would recomend for you at the moment:

 if(index < 0 || isEmpty() || index > size()-1)
 {
     throw std::out_of_range("Error Message");
 }

The standard library for vector does it slightly differently. In the vector it is just undefined behavior to use an out of range index. But that fact is well documented (unlike your original version). But they also provide a second method at() that does do range checking. This version will throw an exception when the range is exceeded.

  V& operator[](std::size_t index) {return data[index];}
  V& at(std::size_t index)         {checkRange(index);return data[index];}

Returning by reference.

The standard containers return reference to their members. This allows you to modify the members in place in the container.

  std::vector   myData(/* Fill the container*/);

  myData[5] = 56; // modifies the value in the container.
                  // this only works if you return a reference.

Access operator const version

Now you have access to members via operator[]. But the contents become inaccessible if you have a const reference to your container. But as long as you are not modifying the container you should still be able to read them.

So you should also add const version of the access operator.

  V&       operator[](std::size_t index)       {return data[index];}
  V const& operator[](std::size_t index) const {return data[index];}

Prefer local objects to dynamic objects

auto list = std::make_unique<Nyo::Util::LinkedList<std::string>>();

You should only be making objects dynamically like this if you can not tell the lifespan of the object until runtime.

Most of the time you should be using automatic objects.

Nyo::Util::LinkedLis  list;  // This is how you normally declare variables.
\$\endgroup\$
  • \$\begingroup\$ sorry for the goofy braces but I tried to replace some words in my editor and throught this action these braces remained like that, this was not done on my purpose . Thanks for the prefix operator tip. I'll work on pointers a little bit more, I'm feeling confident with the shared type, but I know I need to get further into raw and unique types for efficiency: that's why I'm Learning! anyways thanks for your answers, they are really appreciated \$\endgroup\$ – Oleg Nykolyn Sep 2 '16 at 16:21
  • 1
    \$\begingroup\$ @OlegNykolyn another couple of sections added. \$\endgroup\$ – Martin York Sep 2 '16 at 16:35
  • \$\begingroup\$ well appreciated suggestions, thanks again \$\endgroup\$ – Oleg Nykolyn Sep 2 '16 at 16:44
2
\$\begingroup\$

naming comments.

In general dont surprise people. I found these things surprising

typename V Although perfectly valid and correct, everybody expects T not V

Using a naming convention for non member variables. You use an _ prefix for parameters and locals. Again perfectly correct (although prepending '_' is not really a good thing, it comes close to using reserved names). But most people expect the opposite, special names for member variables and 'plain' names for parameters and locals

\$\endgroup\$
  • \$\begingroup\$ thanks for the tips, I'm profoundly influeced by the java world, I need to be detached from it a lot more when writing c++. \$\endgroup\$ – Oleg Nykolyn Sep 3 '16 at 6:29
2
\$\begingroup\$
template <typename V>
class LinkedList {
    // ...
    template <typename V>
    void insertAt(int index, const V& _data) {

The declaration typename V for insertAt shadows the declaration of typename V for LinkedList. The C++ Standard says this behavior isn't allowed.

14.6.1 Locally declared names [temp.local]

\$^6\$ A template-parameter shall not be redeclared within its scope (including nested scopes). A template-parameter shall not have the same name as the template name.


Compile with warnings enabled (-Wall -Wextra). If your goal is to write code intended for other platforms, enable pedantic warnings as well (-pedantic).

gcc -stdlib=libc++ -O3 -march=native -std=c++1z -Wall -Wextra -pedantic

Two warnings are generated in LinkedList:

warning: field next will be initialized after field data [-Wreorder]

Define and initialize member variables in the order of member declaration. Member variables are always initialized in the order they are declared in the class definition, so write them in that order in the constructor initialization list. Writing them in a different order in the constructor initialization list just makes the code confusing because it won't run in the order you see, which makes it difficult to find order-dependent bugs.

warning: comparison of integers of different signs: int and unsigned long [-Wsign-compare]

If you deal with values at the extreme ends of the value range, sign mismatch comparisons can end up biting you. If you know as a fact your code will never approach those extreme ends, then you can safely cast to discard the warning. If your code has the possibility of working in those extreme ends, then use the same type.


Assume you create a list of one million elements.

const auto elements_expected = 1000000;
auto list = std::make_unique<Nyo::Util::LinkedList<int>>();

for (int i = 0; i < elements_expected; ++i) {
    list->add(i);
}

// do something to ensure the list isn't optimized away.

Your program, when run, will ultimately return

Segmentation fault

RAII containers are designed to call the destructor at the end of scope. In this use-case, that destruction call cascades down the list adding each call to the stack. If the list is deep enough, you will overflow the stack and the result is a segmentation fault. You'll need a destructor that iteratively destructs the list, which will also require that you satisfy the rule of five.

You are perfectly right about the segmentation fault, how do I actually fix that? I have no clue at the moment

The simplest way is to pop off the first the element until you have an empty list.

~LinkedList() {
    while (head) {
        head = std::move(head->getNext());
    }
}
\$\endgroup\$
  • \$\begingroup\$ You are perfectly right about the segmentation fault, how do I actually fix that? I have no clue at the moment \$\endgroup\$ – Oleg Nykolyn Sep 3 '16 at 0:05
  • 1
    \$\begingroup\$ Added it to the answer, but do read up on the rule of five as the compiler will not generate all of them implicitly define constructors/operators for you. \$\endgroup\$ – Snowhawk Sep 3 '16 at 0:59
  • \$\begingroup\$ I've been trying to understand why your answer worked. Let me know if my explanation is correct. Because I'm using a shared_ptr<T> everytime I get an instance in the destructure of head, when this one is set to the next node, the previous head has its resources freed up automatically because of the implicit nature of a smart pointer. \$\endgroup\$ – Oleg Nykolyn Sep 3 '16 at 6:24
  • \$\begingroup\$ That's the general order. There are temporaries created, value swapping, and shared_ptr's reference count management. \$\endgroup\$ – Snowhawk Sep 3 '16 at 8:38
  • 1
    \$\begingroup\$ I think the problem lies in the extreme usage of shared_ptr<T> \$\endgroup\$ – Oleg Nykolyn Sep 3 '16 at 8:46

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.