HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Optimising a LinkedList data structure - Part 1

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
linkedlistpartoptimisingstructuredata

Problem

I have implemented a linked list. I feel I overdid it with pointers, used old standards and C++11, and I ended with too many lines of code. I will make my quotations into two parts: one for the Node and iterator struct and the other for rest of the class.

For node and iterator, how can I optimize for C++11? Can you review it?

```
#include
#include
template
class LinkedList
{
private:
struct Node
{
T_ data;
Node* prev;
Node* next;
/Node(T_ D, Node p = nullptr, Node n = nullptr) : data(d), prev(p), next(n) {}/

Node( const T_ & d = Object{ }, Node p = nullptr, Node n = nullptr )
: data(d), prev(p), next(n) { }

Node( T_ && d, Node p = nullptr, Node n = nullptr )
: data( std::move(d)), prev(p), next(n) { }

Node( Node && n ) { // Rvalue move ctor
data = std::move(n.data);
prev = std::move(n.prev);
next = std::move(n.next);
}
Node& operator = ( Node && n ) { // Rvalue = operator
data = std::move(n.data);
prev = std::move(n.prev);
next = std::move(n.next);
return *this;
}
void swap(Node& rhs) throw ()
{
std::swap(prev, rhs.prev); std::swap(next, rhs.next);
}
};

public:
struct LinkedListIterator : public std::iterator
{
Node* _pNode;

LinkedListIterator(Node* p = nullptr) : _pNode(p) {}

Node* getNode() { return _pNode; }

T_ operator * () { return _pNode->data; }
LinkedListIterator & operator ++ () { _pNode = _pNode->next; return *this; } // pre
LinkedListIterator operator ++ (int) { LinkedListIterator retval = this; ++this; return retval; } // post
bool operator < ( LinkedListIterator const& rhs ) const { return _pNode < rhs._pNode; }
bool operator != ( LinkedListIterator const& rhs ) const { return _pNode != rhs._pNode; }
bool op

Solution

There are several small things I can see in class Node:

  • You have a move constructor, but no copy constructor.



  • You have a move assignment operator, but no copy assignment operator.



  • Since you use C++11, you should replace the exception specification throw () (now deprecated) by noexcept.



  • Your move assignment operator is not protected against self-assignment. You should add the condition if (&n != this) { ... }.



  • Also, if possible, your move constructor and operator= should be noexcept too.



-
Generally speaking, with move assignment operator, you don't want to move pointers, you only want to swap them since - I believe - your nodes own the pointed values (more information here).

Node& operator=(Node&& n) noexcept {
    if (&n != this) {
        std::swap(data, n.data);
        std::swap(prev, n.prev);
        std::swap(next, n.next);
    }
    return *this;
}

Code Snippets

Node& operator=(Node&& n) noexcept {
    if (&n != this) {
        std::swap(data, n.data);
        std::swap(prev, n.prev);
        std::swap(next, n.next);
    }
    return *this;
}

Context

StackExchange Code Review Q#41388, answer score: 5

Revisions (0)

No revisions yet.