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;
}
Slayer
Red Hot Chili Peppers
Children of Bodom
Pantera
Stratovarius
Rage Against the Machine
Velvet Revolver
Franz Ferdinand
Audioslave
Joey Ramone