linked list

linked_list.hpp

#pragma once

#include <iostream>

template <typename T> 
class linked_list
{
public:
	static const size_t k_invalid_pos = 0xFFFF;

public:
	linked_list() = default;
	~linked_list();
	linked_list(const linked_list& l);

	size_t count() const;

	void reverse();

	//linked_list reverse() const;
	void print() const;

	void insert(const T& t);
	T pop_front();
	void push_back(const T& t);
	void remove(const T& t);
	size_t pos(const T& t) const;
	bool exists(const T& t) const;
	
private:
	struct node
	{
		struct node* next;
		T data;
	} *head = nullptr;
};

template<typename T>
inline linked_list<T>::~linked_list()
{
	while (head != nullptr)
	{
		node* p = head;
		head = p->next;
		delete p;
	}
}

template<typename T>
inline linked_list<T>::linked_list(const linked_list& l)
{
	node* p = l->head;
	while (p != nullptr)
	{
		push_back(p->data);
		p = p->next;
	}
}

template<typename T>
inline size_t linked_list<T>::count() const 
{ 
	size_t total = 0;
	node* p = head;
	while (p != nullptr)
	{
		p = p->next;
		total++;
	}

	return total;
}

template<typename T>
inline void linked_list<T>::reverse()
{
	node* p = head;
	head = nullptr;

	while (p != nullptr)
	{
		node* temp = head;
		head = p;
		p = p->next;
		head->next = temp;
	}
}

template<typename T>
inline void linked_list<T>::print() const
{
	node* p = head;
	while (p != nullptr)
	{
		std::cout << p->data << ", ";
		p = p->next;
	}
	std::cout << std::endl;
}

template<typename T>
inline void linked_list<T>::insert(const T& t)
{
	node* p = new node;
	p->data = t;
	p->next = head;
	head = p;
}

template<typename T>
inline T linked_list<T>::pop_front()
{
	if (head != nullptr)
	{
		node* p = head;
		head = head->next;
		return p->data;
	}

	// TODO:
	return T();
}

template<typename T>
inline void linked_list<T>::push_back(const T& t)
{
	if (head == nullptr)
	{
		node* new_node = new node;
		new_node->data = t;
		new_node->next = nullptr;
		head = new_node;
		return;
	}

	node* p = head;
	// find the tail node
	while (p != nullptr)
	{
		if (p->next == nullptr)
		{
			node* new_node = new node;
			new_node->data = t;
			new_node->next = nullptr;
			p->next = new_node;
			break;
		}
		else
		{
			p = p->next;
		}
	}
}

template<typename T>
inline void linked_list<T>::remove(const T& t)
{
	node* p = head;
	node* prev = nullptr;

	while (p != nullptr)
	{
		if (p->data == t)
		{
			if (prev == nullptr)
			{
				head = head->next;
			}
			else
			{
				prev->next = p->next;
			}

			// remove the node
			node* temp = p->next;
			delete p;
			p = temp;
		}
		else
		{
			prev = p;
			p = p->next;
		}
	}
}

template<typename T>
inline size_t linked_list<T>::pos(const T& t) const
{
	node* p = head;
	size_t i = 0;

	while (p != nullptr)
	{
		if (p->data == t)
		{
			return i;
		}

		p = p->next;
		i++;
	}

	return k_invalid_pos;
}

template<typename T>
inline bool linked_list<T>::exists(const T& t) const
{
	node* p = head;
	while (p != nullptr)
	{
		if (p->data == t)
			return true;

		p = p->next;
	}

	return false;
}