phalaris_trip 5 Junior Poster in Training

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;
	}
};
elsiekins commented: best explanation and code i have found on this so far +0
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.