Singly linked list in C++

These days I needed a clean implementation of a singly linked list in C++. I found some ones around, but none of them was functional and clean and the same time. So I wrote my own, using nothing but pure C++ with templates, and here I’m publishing the full implementation.

First, the header. I chose to put the node class nested into the linked list class, because this approach allows me to have another node class which can belong to another kind of structure, if I need to. There are a couple of methods beyond the basics, I needed them to have a functional data structure that worked for me.

template<typename T> class LinkedList {
public:
	class Node {
	public:
		      Node()                     : _next(NULL) { }
		      Node(const T& data)        : _data(data), _next(NULL) { }
		Node* insertAfter();
		Node* insertAfter(const T& data) { return &(*this->insertAfter() = data); }
		Node* removeAfter();
		T&    data()                     { return _data; }
		Node& operator=(const T& data)   { this->_data = data; return *this; }
		Node* next(int howMany=1);
		int   countAfter() const;
	private:
		T     _data;
		Node *_next;
	friend class LinkedList;
	};

public:
	      LinkedList()          : _first(NULL) { }
	     ~LinkedList();
	int   count() const         { return !this->_first ? 0 : this->_first->countAfter() + 1; }
	Node* operator[](int index) { return !this->_first ? NULL : this->_first->next(index); }
	Node* append();
	Node* append(const T& data) { return &(*this->append() = data); }
	void  removeFirst();
	Node* insertFirst();
	Node* insertFirst(const T& data) { return &(*this->insertFirst() = data); }
private:
	Node *_first;
};

The node class implementation:

template<typename T> typename LinkedList<T>::Node* LinkedList<T>::Node::insertAfter() {
	Node *tmp = new Node;
	tmp->_next = this->_next; // move our next ahead
	this->_next = tmp; // new is our next now
	return this->_next; // return newly inserted node
}

template<typename T> typename LinkedList<T>::Node* LinkedList<T>::Node::removeAfter() {
	if(this->_next) {
		Node *nodebye = this->_next;
		if(this->_next->_next) this->_next = this->_next->_next;
		delete nodebye;
	}
	return this; // return itself
}

template<typename T> typename LinkedList<T>::Node* LinkedList<T>::Node::next(int howMany) {
	Node *ret = this;
	for(int i = 0; i < howMany; ++i) {
		ret = ret->_next;
		if(!ret) break;
	}
	return ret; // howMany=0 returns itself
}

template<typename T> int LinkedList<T>::Node::countAfter() const {
	int ret = NULL;
	Node *no = this->_next;
	while(no) { no = no->_next; ++ret; }
	return ret; // how many nodes exist after us
}

And the linked list implementation:

template<typename T> LinkedList<T>::~LinkedList() {
	Node *node = this->_first;
	while(node) {
		Node *tmpNode = node->next();
		delete node;
		node = tmpNode;
	}
}

template<typename T> typename LinkedList<T>::Node* LinkedList<T>::append() {
	if(!this->_first)
		return ( this->_first = new Node ); // return first and only
	Node *node = this->_first;
	while(node->next()) node = node->next();
	return node->insertAfter(); // return newly inserted node
}

template<typename T> void LinkedList<T>::removeFirst() {
	Node *nodebye = this->_first;
	if(this->_first->next()) this->_first = this->_first->next();
	delete nodebye;
}

template<typename T> typename LinkedList<T>::Node* LinkedList<T>::insertFirst() {
	Node *newly = new Node;
	if(this->_first) newly->_next = this->_first; // only case of FRIEND use
	return this->_first = newly; // return newly inserted node
}

The machinery is pretty straightforward to use, I believe. You just need to declare one instance of the LinkedList class, and all the node manipulation will be done through it and the node pointers returned by the methods, which allows operations on the nodes themselves. You’ll never have to alloc/dealloc any node. Here’s an example, with some operations and then printing all elements:

#include <stdio.h>
int main() {
	LinkedList<int> list;
	list.append(33)->insertAfter(80);
	list.insertFirst(4)->removeAfter();

	LinkedList<int>::Node *node = list[0];
	while(node) {
		printf("%d\n", node->data()); // print each value
		node = node->next();
	}
	return 0;
}