I've searched for linked lists quite a lot (and read some books), but I've yet to find one that suits my needs. I wanted one that is: templated, provides only the bare bones of what's needed and easy to read and understand the code (simple, consistent variable names, meaningful and uncluttered comments).
So here is what I made (thanks to Ancient Dragon also for some help earlier on).
As I said, only minimal functionality, so no iterators.
I plan to use this in my written exam (since STL containers are banned, I'm going to beat the lecturer at his own game!)
Any criticism is welcome. And maybe you find it useful or whatever..
#include <iostream>
#include <cassert>
template<typename T>
class list
{
protected:
// Linked list node
struct node
{
T data;
node* next;
};
// Basic linked list elements
node* head;
node* tail;
int count;
public:
// Default constructor
list() : head(NULL), tail(NULL), count(0) {}
// Clear list
void clear()
{
while (head != NULL)
{
node* popped = head;
head = head->next;
delete popped;
}
tail = NULL;
count = 0;
}
// Destructor
virtual ~list()
{
this->clear();
}
// Return true if list is empty
bool empty() const
{
return (head == NULL);
}
// Return true if element found in list
bool search (const T& t) const
{
// Traverse the list
node* curr = head;
while (curr != NULL)
{
if (curr->data == t)
return true; // Entry found
else
curr = curr->next;
}
// Entry not found
return false;
}
// Return size of the list
int size() const
{
return count;
}
// Access first element
T& front()
{
// Make sure not to dereference null ptr
assert (head != NULL);
return head->data;
}
// Access last element
T& back()
{
// Make sure not to dereference null ptr
assert (tail != NULL);
return tail->data;
}
// Access element at index
T& operator[] (unsigned int index)
{
// Make sure index is valid
int n = (int)index;
assert(n < count);
// Search for nth element
node* curr = head;
for (int i=0; i<n; i++)
curr = curr->next;
return curr->data;
}
// Push element to front of list
list& push_front(const T& t)
{
// Create a new node and push data
node* front = new node;
front->data = t;
// If list is empty..
if (head == NULL)
{
head = tail = front; // ..front is first and last node
front->next = NULL;
}
else
{
// Insert front before head
front->next = head;
head = front;
}
count++;
return *this;
}
// Push element to back of list
list& push_back(const T& t)
{
// Create a new node and push data
node* back = new node;
back->data = t;
// If list is empty..
if (head == NULL)
{
head = tail = back; // ..back is first and last node
back->next = NULL;
}
else
{
// Insert back after tail
back->next = NULL;
tail->next = back;
tail = back;
}
count++;
return *this;
}
// Pop element from front of list
list& pop_front()
{
if (head != NULL)
{
node* popped = head;
// Get new head
head = head->next;
// Deallocate memory pointed to by head
delete popped;
count--;
}
return *this;
}
// Pop element from back of list
list& pop_back()
{
if (head != NULL)
{
// Keep track of node to be deleted
node* popped = tail;
// Get new tail
tail = head;
node* curr = head;
while (curr->next != NULL)
{
tail = curr;
curr = curr->next;
}
tail->next = NULL;
// If list is now empty..
if (curr == head)
{
head = NULL; // ..head points to null
}
// Deallocate memory pointed to by tail
delete popped;
count--;
}
return *this;
}
// Erase element at index from list
list& erase(unsigned int index)
{
// If index is invalid, do nothing
int n = (int)index;
if (n >= count)
return *this;
// Boundary case
if (n == 0)
{
this->pop_front();
return *this;
}
// Boundary case
if (n == count-1)
{
this->pop_back();
return *this;
}
// Find element in front of the designated one
node* curr = head;
for (int i=0; i<n-1; i++)
curr = curr->next;
// Track node to be deleted
node* popped = curr->next;
// Relink the list
curr->next = popped->next;
// Erase designated element
delete popped;
count--;
return *this;
}
// List assignment
list& operator= (list<T> rhs)
{
this->clear();
for (int i=0; i<rhs.size(); i++)
{
this->push_back(rhs[i]);
}
return *this;
}
// DEBUG
list& print()
{
std::cout << "elements = { ";
for (int i=0; i<count; i++)
{
std::cout << (*this)[i] << ", ";
}
std::cout << "}; size = " << count << ";" << std::endl;
return *this;
}
};