4
\$\begingroup\$

This is part 2. My problems are with too any pointers and with long body code in the following functions:

void push_back(T_ data);
void push_front(T_ data);
T_ pop_back();
T_ pop_front();
void insert(iterator_t& i, T_ data);
void erase(iterator_t& i);
T_ front();
T_ back();
void print();
void clear();

private:
    Node*  _head;
    Node*  _tail;
    int    _size;

public:
    typedef LinkedList<T_> list_t;
    typedef Node      node_t;
    typedef list_t*  listPtr;
    typedef node_t*  node_ptr_t;
    typedef LinkedListIterator iterator_t;

    LinkedList() : _head( nullptr ), _tail( nullptr ), _size( 0 ) {}
    LinkedList( LinkedList && list ) {        // Rvalue move ctor
        _head = std::move(list._head);
        _tail = std::move(list._tail);
        _size = std::move(list._size);
    }
    ~LinkedList() {
        // dtor deletes all of the node ptrs in the list
        // very important to avoid memory leaks
        while(_head)
        {
            node_ptr_t tmpNode(_head);
            _head = _head->next;
            delete tmpNode;
        }
    }

    LinkedList& operator = ( LinkedList && list ) { // Rvalue = operator
        _head = std::move(list._head);
        _tail = std::move(list._tail);
        _size = std::move(list._size);
        return *this;
    }

    bool empty() const { return ( !_head || !_tail ); }
    operator bool() const { return !empty(); }

    node_ptr_t head() { return _head; }
    node_ptr_t tail() { return _tail; }
    int size() { return _size; }

    iterator_t begin() { return iterator_t(_head); }
    iterator_t end() { iterator_t i(_head); while(i != nullptr) ++i; return i; }

    void push_back(T_ data){
        _tail = new node_t(data, _tail, nullptr);
        if( _tail->prev )
            _tail->prev->next = _tail;

        if( empty() )
            _head = _tail;
        ++_size;
    }
    void push_front(T_ data)
    {
        _head = new node_t(data, nullptr, _head);
        if( _head->next )
            _head->next->prev = _head;

        if( empty() )
            _tail = _head;
        ++_size;
    }
    T_ pop_back(){
        assert( !empty() );

        node_ptr_t tmpNode(_tail);
        T_ result = _tail->data;
        if(_tail->prev)
            _tail = _tail->prev;
        else
            _tail = _head;

        _tail ? _tail->next=nullptr : _head=nullptr;

        --_size;
        delete tmpNode;
        return result;
    }
    T_ pop_front(){
        assert( !empty() );

        node_ptr_t tmpNode(_head);
        T_ result = _head->data;
        if(_head->next)
            _head = _head->next;
        else
            _head = _tail;

        _head ? _head->prev=nullptr : _tail=nullptr;

        --_size;
        delete tmpNode;
        return result;
    }
    void insert(iterator_t& i, T_ data){
        node_ptr_t tmpNode = new node_t(data, i.getNode()->prev, i.getNode());
        if(i.getNode()->prev)
            i.getNode()->prev->next = tmpNode;
        i.getNode()->prev = tmpNode;
        if(i.getNode() == _head)
            _head = i.getNode()->prev;
        i = iterator_t(tmpNode);
        ++_size;
    }
    void erase(iterator_t& i)   {
        node_ptr_t tmpNode = i.getNode();
        if(i.getNode() == _head) {
            _head = i.getNode()->next;
        }
        if(i.getNode() == _tail) {
            _tail = i.getNode()->prev;
        }

        if( i.getNode()->next )
            i = iterator_t( i.getNode()->next );
        else if( i.getNode()->prev)
            i = iterator_t( i.getNode()->prev );

        if(tmpNode->prev)
            tmpNode->prev->next = tmpNode->next;
        else
            tmpNode->prev = nullptr;
        if(tmpNode->next)
            tmpNode->next->prev = tmpNode->prev;
        else
            tmpNode->prev = nullptr;

        delete tmpNode;
        --_size;

        //node_ptr_t newTail = (tail == i.getNode()->prev ) ? i.getNode()->prev : tail;

        //tail = newtail;
        //--_size;
        //delete i.Node

    }
    T_ front(){
        return _head->data;
    }
    T_ back(){
        return _tail->data;
    }
    void print();
    void clear(){
        while(_head)
        {
            node_ptr_t tmpNode(_head);
            _head = _head->next;
            delete tmpNode;
        }
    }
};
\$\endgroup\$
  • \$\begingroup\$ You should probably include your Node implementation, or at least mention that it exists. At first glance, I thought you were implementing the list and the node in one class. \$\endgroup\$ – Jamal Feb 11 '14 at 23:12
  • 1
    \$\begingroup\$ Your code becomes much simpler if you add a sentinal to the list. This will remove all the checks for NULL in the list as there is always at least one element (the sentinal). See codereview.stackexchange.com/a/9399/507 \$\endgroup\$ – Martin York Feb 11 '14 at 23:24
6
\$\begingroup\$

Size

Normally I'd say right away that size should return an std::size_t instead of an int, but some recent collaborations amongst top C++ experts (including Bjarne Stroustrup himself) have revealed that this can be problematic due to signed/unsigned mismatch. In your implementation at least, you could probably keep it as is, but I at least wanted to bring that up here.

Pointers

In general, keep in mind that you should use smart pointers for C++. They are preferred as they can take ownership of what they point to, which especially ensures that their data will be cleaned up properly.

However, for containers (like you have here), you would use raw pointers. Just make sure to manage them correctly because the list should still be responsible for cleaning up after itself.

clear() and ~LinkedList()

You may not need clear() since you already have to do the same thing in the destructor. If you prefer to be able to clear the nodes at will but keep the same object, then you can keep it. If you choose to keep it, then you can just call clear() in the destructor to avoid duplicate code.

Self-assignment

Normally you (may) do self-assignment with the copy constructor and operator=, but with a move contstructor, you likely will not. A more detailed answer on this can be found here.

Nonetheless, this is what operator= would look like if you were to use it anyway. This would also be similar for the copy constructor.

LinkedList& operator = ( LinkedList && list ) {
    if (this != &list) {
        _head = std::move(list._head);
        _tail = std::move(list._tail);
        _size = std::move(list._size);
    }

    return *this;
}

Misc.

  • Your pop_front() and pop_back() should just be void. This is especially useful as they may potentially fail (especially with templated types), and so you won't be forced to return something. However, popping from an empty container can still cause undefined behavior.

    Along with that, you can also have define front() and back() to return references to elements. With a pop_back() that is void, this will allow you to copy to a local variable before the pop.

    Note that these are all done in the STL, which you should try to imitate.

  • With begin() and end(), you may also define cbegin() and cend(), which return const iterators. This would be useful for uses such as displaying the list contents.

  • head(), tail(), and size() should be const as they're accessors:

    node_ptr_t head() const { return _head; }
    node_ptr_t tail() const { return _tail; }
    int size() const { return _size; }
    
\$\endgroup\$
5
\$\begingroup\$

Here your code is going to crash(or have undefined behavior):

LinkedList getValue() {/*Something*/ return result;}

int main()
{
    LinkedList  x = getValue();
    LinkedList  y(std::move(x));
}

That's because the move constructor moves all the pointers from x into y. But you have not set x into a different state. It still has its old values. Now y goes out of scope destroying the internal data. Then x goes out of scope with its pointers pointing at the delocated objects. But its destructor does not know they were deallocated and will do a second delete on all the members.

This is a very expensive way to get end:

iterator_t end() { iterator_t i(_head); while(i != nullptr) ++i; return i; }

What happens if I write:

for(auto loop = list.begin(); loop != list.end(); ++loop)
{}

Every time we test loop against end we have to loop through the whole list to construct the end iterator. That basically converts this from O(n) into an O(n^2) operation.

If you must do it this way keep a copy for re-use. You only need to re-create it when you add/remove elements to the container the rest of the time just return your cached copy (a lot of containers use this simple optimization tactic).

But really this class is so simple I would expect to see:

iterator_t end() { return iterator_t(tail)++;} 

Your code could be much simpler if you use a sentinel node(s). It removes all the code that checks for NULL (as an empty list has the sentinel in it so no NULLs). Because you don't need to check for NULL it makes the code much more trivial to write).

// Look how short erase is when you don't need to worry about NULL.
void erase(iterator_t& i)   {
    node_ptr_t tmpNode = i.getNode();

    tmpNode->next->prev = tmpNode->prev;
    tmpNode->prev->next = tmpNode->next;

    delete tmpNode;
    --_size;
}

Stop using a leading underscore:

_size

The rules about a leading underscore are non trivial so just don't use them. In a lot of cases they are reserved for the implementation. So the standard library can use it legitimately all the time (you can't always use it).

Don't always return a copy.

T_ front(){
    return _head->data;
}
T_ back(){
    return _tail->data;
}

Return a reference to the internal object. That way they can be modified in place.

T_& front(){
    return _head->data;
}
T_& back(){
    return _tail->data;
}
T_ const& front() const {
    return _head->data;
}
T_ const& back() const {
    return _tail->data;
}

This code is exactly the same as the destructor:

void clear(){
    while(_head)
    {
        node_ptr_t tmpNode(_head);
        _head = _head->next;
        delete tmpNode;
    }
}

Write DRY code. Make the constructor call clear(). But also make the destructor catch all exceptions (unlike clear). This way if a user wants to check for errors they call clear. If they don't care then the destructor will clean up and catch any exceptions (as you should never allow an exception to escape a destructor).

 ~LinkedList()
 {
     try {
        clear();
     }
     catch(...) {}
 }

Don't expose the internal implmentation of your class:

node_ptr_t head() { return _head; }
node_ptr_t tail() { return _tail; }

We have the abstract concept of iterator to allow users to search or move through containers. Don't provide them with implementation details in the public interface as this locks you to using the implementation forever.

\$\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.