C++ Generic Linked List

Question

My goal is to write a reasonably robust c++ linked list class. The current code represents the latest phase in this attempt. My future goal is to implement a doubly linked list along with more member functions. Before I continue further, I would like some input on my overall design thus far. Also, any input on improving the code is very much welcomed and is of great concern to me. I am hoping to learn other people's approach so that I can carry what I learn into this and future projects.

template <typename T>
struct Node
{
 Node(): link(nullptr), value(0) {}
 Node(const T val) : link(nullptr), value(val) {}
 Node(const Node<T>* node) : link(node->link), value(node->value) {}
 Node<T> *link;
 T value;
};

#include "node.h"
#include <cstddef>
#include <iostream>
template <typename T>
class List
{ 
public:
 // constructors
 List() : head(nullptr), sz(0) {}
 List(const size_t s);
 List(const List& rhs);
 ~List();
 List<T>& operator=(const List& rhs);
 // element access:
 T at(const size_t position);
 T operator[](const size_t position);
 // modifiers:
 void push_back(const T value);
 void pop_back();
 void insert(const size_t position, const T value);
 void erase(const size_t position);
 // capacity:
 size_t size() const {return sz;}
private:
 void subError(); // Handles memory subscripts out of range
 Node<T> *head;
 size_t sz;
};
// Class implementation
template <typename T>
List<T>::List(size_t const s) : head(nullptr), sz(s)
{
 Node<T> d;
 Node<T>* nodePtr = &d;
 for (size_t i = 0; i < sz; i++) {
 nodePtr->link = new Node<T>;
 nodePtr = nodePtr->link;
 }
 this->head = d.link;
}
template <typename T>
List<T>::List(const List& rhs)
{
 List::operator =(rhs);
}
template <typename T>
List<T>& List<T>::operator=(const List& rhs)
{
 sz = rhs.sz;
 Node<T> d;
 for (Node<T>* r = rhs.head, *n = &d; r; r = r->link) {
 n->link = new Node<T>(r);
 n = n->link;
 }
 this->head = d.link;
 return *this;
}
template <typename T>
List<T>::~List()
{
 Node<T>* nodePtr = head;
 while (nodePtr != nullptr) {
 Node<T>* nextNode = nodePtr->link;
 delete nodePtr;
 nodePtr = nextNode;
 }
}
template <typename T>
T List<T>::at(const size_t position)
{
 Node<T>* nodePtr = head;
 if (position < 0 || position >= this->size()) {
 subError();
 } else {
 for (size_t i = 0; i < position; i++) {
 nodePtr = nodePtr->link;
 }
 }
 return nodePtr->value;
}
template <typename T>
T List<T>::operator[](const size_t position) {
 return at(position);
}
template <typename T>
void List<T>::push_back(const T value)
{
 Node<T>* newNode = new Node<T>(value);
 // If there are no nodes in the list make newNode the first node.
 if (head == nullptr) {
 head = newNode;
 // Otherwise, insert newNode at end.
 } else {
 Node<T>* nodePtr = head;
 // Go to the last node in the list.
 while (nodePtr->link) {
 nodePtr = nodePtr->link;
 }
 // Insert newNode as the last node.
 nodePtr->link = newNode;
 }
 ++sz;
}
template <typename T>
void List<T>::pop_back()
{
 if (!head) {
 return;
 } else if (!head->link) {
 delete head;
 head = nullptr;
 sz = 0;
 } else {
 Node<T>* nodePtr = head;
 Node<T>* previousNode = nullptr;
 while (nodePtr->link) {
 previousNode = nodePtr;
 nodePtr = nodePtr->link;
 }
 previousNode->link = nullptr;
 delete nodePtr;
 --sz;
 }
}
template <typename T>
void List<T>::insert(const size_t position, const T value)
{
 if (position > sz) {
 subError();
 }
 Node<T>* newNode = new Node<T>(value);
 Node<T>* nodePtr = head;
 Node<T>* previousNode = nullptr;
 if (head == nullptr) {
 head = newNode;
 // Insert at beginning of list
 } else if (position == 0) {
 head = newNode;
 newNode->link = nodePtr;
 // Otherwise insert new node at given position
 } else {
 for (size_t i = 0; i < position; i++) {
 previousNode = nodePtr;
 nodePtr = nodePtr->link;
 }
 previousNode->link = newNode;
 newNode->link = nodePtr;
 }
 ++sz;
}
template <typename T>
void List<T>::erase(const size_t position)
{
 if (sz <= position || head == nullptr) {
 subError();
 }
 Node<T>* nodePtr = head;
 Node<T>* previousNode = nullptr;
 // Erase first element
 if (position == 0) {
 head = nodePtr->link;
 delete nodePtr;
 // Otherwise erase element at position
 } else {
 for (size_t i = 0; i < position; i++) {
 previousNode = nodePtr;
 nodePtr = nodePtr->link;
 }
 previousNode->link = nodePtr->link;
 delete nodePtr;
 }
 --sz;
}
template <typename T>
void List<T>::subError() {
 std::cout << "ERROR: Subscript out of range.\n";
 exit(EXIT_FAILURE);
}

• Jerry Coffin: Your effort is impressive. Your choice of targets...less so, at best. There are very few situations in which linked lists are preferable to other data structures (and those few are sufficiently specialized that generic linked lists often don't work for them).
• Loki Astari: In my opinion the Double Linked list is an easier first project. You do the singly linked list as an optimization to save space. As a result of saving space things get more complicated.

Answer 1

Design

In your list you are only tracking the head of the list.

 Node<T> *head;

This may be an efficiency problem as adding to the end of a list is a common task. Currently a push to the back of the list requires you to traverse the list before adding the item.

Also a singly linked list is probably not a good choice as it is harder to write. Inserting/Deleting require you keep track of two positions while a doubly linked list can be done by just tracking a singly linked list.

If you use a doubly linked list then using a circular list with a sentinel value will make the code even easier to write as you never need to check for NULL (as there will always be a sentinel).

Interface Review

Interface

Your node is a private member of you list. As such it should not be exposed to you users (Any interface you provide has to be maintained). Thus your node class should be a private member of List<T>

Pass by reference

Currently when you pass the data payload into your list you are passing it by value.

 Node<T>::Node(const T val) : link(nullptr), value(val) {}
 ^^^^^^^
 void List<T>::push_back(const T value)
 ^^^^^^^

This means a copy of the object is made as it is passed to the parameter to push_back() then another copy is made as it is passed as a parameter to the Node() constructor and finally another copy is made as it is placed into the object.

So you have three copies of the input parameter being made. To prevent this pass by const reference.

 Node<T>::Node(T const& val) : link(nullptr), value(val) {}
 ^ Notice the & 
 void List<T>::push_back(T const& value)
 ^ Notice the & 

Move Semantics

You are still using C++03 (we are now on C++14 and quickly rushing towards C++17). It's time to learn move semantics.

It is usually much more efficient to move an object rather than copy it, so you should design your list with move semantics in mind. Currently when you create a Node object you are copying the payload into the Node<T>. You should add a move constructor.

 // Copy data into node
 Node(const T& val) : link(nullptr), value(val) {}
 // Move data into node
 Node(T&& val) : link(nullptr), value(std::forward<T>(val)) {}

Emplacement

There is also the concept of emplacement. This is passing the parameters need to construct the payload forward to the constructor of the payload so that you don't need to even create the object until it reaches the Node.

This uses vardac templates though so is not a beginner topic. But looks like this.

template<typename T>
struct Node
{
 T data;
 template<typename... Args>
 Node(Args&& args...)
 : data(std::forward<Args>(args)...)
 {}
};

Constructors

 List(const size_t s);

A list that takes just a size does not seem very logical. What are the object you place in the list? I suppose you can default construct the payload but not all payloads are default constructible. I would have added a second parameter for the values in the list (you can always default it to the default constructed value).

 // Here is my version.
 List(const size_t s, T const& value = T());

You have the copy constructor.

 List(const List& rhs);
 List<T>& operator=(const List& rhs);

But you may want to add a couple more constructors.

 List(List&& rhs); // Move constructor.
 List<T>& operator=(List&& rhs); // Move assignment
 template<typename I>
 List(I begin, I end); // Constructor using iterators.
 List(std::initializer_list<T> const&) // Using initializer list.

This makes it more similar to other container types. Also it makes it much easier to use.

Const correctness

Members that do not change the state of the object should be marked as const. This way you can pass the object as a parameter that is a const reference and still use the members.

 // element access:
 T at(const size_t position);
 T operator[](const size_t position);

Currently if I pass you list to this function:

 void printAt(List<int> const& list, size_t position)
 ^^^^^^ pass by const reference to avoid
 copying the list.
 {
 std::cout << list[position] << "\n";
 ^^^^^^^^^^^^^^ This is not a const member function
 So you can not access it here as
 the function is not marked const
 and list is const.
 }

So these members should be declared as such:

 // element access:
 T at(const size_t position) const;
 T operator[](const size_t position) const;

Return by reference.

 // element access:
 T at(const size_t position);
 T operator[](const size_t position);

What you are doing here is returning by value (so you are copying the value out of the object). Normally what you want to do is return by reference. Then if the user wants a copy assigning to a normal variable makes a copy but if you want to update the value in the list then you can just use it as a reference.

 // Mutating element access
 T& at(const size_t position);
 T& operator[](const size_t position);
 // Non mutating element access.
 T const& at(const size_t position) const;
 T const& operator[](const size_t position) const;

Prefer to pass parameters by const reference

 void push_back(const T value);
 void insert(const size_t position, const T value);

In both these functions you are copying the input parameter. If T is an expensive type to copy you are doing extra work.

Implementation Review

Sized constructor

template <typename T>
List<T>::List(size_t const s): head(nullptr), sz(s)

Default initializer list. Like normal variable declarations deserve a line per variable being initialized. Not all crammed onto the same line

template <typename T>
List<T>::List(size_t const s)
 : head(nullptr)
 , sz(s)

The code below seems overly complex.

{
 Node<T> d;
 Node<T>* nodePtr = &d;
 for (size_t i = 0; i < sz; i++) {
 nodePtr->link = new Node<T>;
 nodePtr = nodePtr->link;
 }
 this->head = d.link;
}

If you move some work off into the Node<T> constructor you can simplify like this.

{
 for (size_t i = 0; i < sz; i++)
 {
 head = new Node<T>(head, value)
 }
}

Copy Constructor

The copy constructor looks broken. I think it currently works. But the assignment operator is broken so when you fix the assignment operator the break will move to this function.

template <typename T>
List<T>::List(const List& rhs)
{
 List::operator =(rhs);
}

You don't initialize the head or sz parameters so they are undefined when you call the assignment operator. Also normally you define the copy constructor and then define the assignment operator in terms of the copy constructor (it's called the copy and swap idiom).

Assignment Operator

This is definitely broken. You leak all your current state.

template <typename T>
List<T>& List<T>::operator=(const List& rhs)
{
 sz = rhs.sz;
 Node<T> d;
 for (Node<T>* r = rhs.head, *n = &d; r; r = r->link) {
 n->link = new Node<T>(r);
 n = n->link;
 }
 this->head = d.link;
 return *this;
}

The Copy and swap idiom

template <typename T>
List<T>::List(List const& rhs)
 : head(nullptr)
 , sz(0)
{
 Node** current = &head;
 for(Node* loop = rhs.head; loop; loop = loop->link)
 {
 (*current) = new Node(loop->data);
 current = &(*current)->link;
 ++sz;
 }
}
template<typename T>
List<T>& List<T>::operator=(List const& rhs)
{
 List<T> tmp(rhs); // Copy
 tmp.swap(*this); // Swap
 return *this; // return
}
template<typename T>
void swap(List<T>& other) noexcept
{
 using std::swap;
 swap(head, other.head);
 swap(sz, other.sz);
}

pop_back()

template <typename T>
void List<T>::pop_back()
{
 if (!head) {
 return;

In the above functions at and operator[] if the request was out of range you called subError() why are you not doing that here?

subError

template <typename T>
void List<T>::subError() {
 std::cout << "ERROR: Subscript out of range.\n";
 exit(EXIT_FAILURE);
}

You are exiting a program for a local error. This is not acceptable. Throw an exception. If the application catches the exception then it can continue if it does not catch the exception then it will exit just like you want.

Answer 2

This strikes me as a severely problematic design.

At least as I see them, linked lists have two basic strengths: constant complexity for:

• insertion or deletion in the middle of the list
• splicing

Unfortunately, your design doesn't seem to support splicing at all, and has linear complexity for insertion or deletion in the middle of the list, because the only way to specify the position is with an integer that requires traversal from the beginning of the list to find the insertion/deletion point.

Two more obvious characteristics of linked lists (though they're common enough with other structures that they don't qualify as special strengths of linked lists) are constant complexity for:

• traversing from one node to the next
• adding to the beginning or end of the list.

Unfortunately, you design seems to provide only one of these: adding to the beginning of the list. Adding to the end of your list is linear, and (again, because the position is specified as an integer) traversal to the next node is linear on the number of nodes before this one in the list.

At least in my opinion, these are fundamental problems with the design. Most of the problems are with the interface, so repairing them requires a new/different definition of the link list class itself.

The one that can be fixed quickly and easily is adding items to the end of the list with constant complexity. To do that, your List class needs to store both a pointer to the last node in the list in addition to the Head pointer you currently have pointing to the first node in the list. Then adding a new node is something like Tail->link = new_node; Tail = Tail->link;

The rest require some fundamental re-thinking of the design though. Probably the biggest change is to change your position type from an integer to some sort of pointer or iterator, so you can manipulate that node without traversing the entire list up to that point to get to it. Without that, even simple traversal of the list is an \$O(N^2)\$ operation, which essentially prohibits almost any serious use.

As to how to do the job right: while it may or may not make a lot of sense to just implement it as specified, I'd at least take a look at the specification of std::list and std::forward_list in the C++ standard for at least some idea of what a linked list can support, and (especially) an interface that allows at least some operations on a linked list to be done reasonably efficiently. I wouldn't say it's the be-all and end-all of linked list designs, but at least it's a reasonable starting point.