Implementazione di una lista concatenata semplice in C++

Una Singly Linked List (lista concatenata semplice) è una struttura dati, composta da nodi, dotata di un nodo testa (head). Ogni nodo contiene al suo interno i dati e un puntatore next al prossimo nodo. L’ultimo elemento ha come valore di next NULL, per indicare il termine della lista.

Di seguito viene presentata un’implementazioen minima di questa struttura dati, che comprende i metodi push_back, push_front e remove.
Si noti come la push_back esegua in O(1) mentre per effettuare in inserimento in testa c’è bisogno di scorrere tutta la lista, che richiede dunque O(n), dove n è il numero di elementi della lista:

struct Node
{
	int data;
	Node* next;
};

class SinglyLinkedList
{
	public:
		SinglyLinkedList();
		~SinglyLinkedList();
		void push_back(int data);
		void push_front(int data);
		void remove(int data);

		void print();
	private:
		Node* head;
};

SinglyLinkedList::SinglyLinkedList()
{
	head = NULL;
}

SinglyLinkedList::~SinglyLinkedList()
{
	Node* iter = this->head;

	while(iter != NULL)
	{
		Node* temp = iter->next;
		delete iter;
		iter = temp;
	}
}

void SinglyLinkedList::push_back(int data)
{
	Node* newNode = new Node;
	newNode->data = data;
	newNode->next = this->head;

	this->head = newNode;
}

void SinglyLinkedList::push_front(int data)
{
	Node* newNode = new Node;
	newNode->data = data;
	newNode->next = NULL;

	if(this->head == NULL)
	{
		this->head = newNode;
	}
	else
	{
		Node* temp;
		for(Node* iter = this->head; iter != NULL; temp = iter, iter = iter->next)
		{	}

		temp->next = newNode;
	}
}

void SinglyLinkedList::remove(int data)
{
	Node* iter = this->head;
	Node* temp = iter;
	while(iter != NULL)
	{
		if(iter->data == data)
		{
			temp->next = iter->next;
			delete iter;
			break;
		}
		else
		{
			temp = iter;
			iter = iter->next;
		}
	}
}

void SinglyLinkedList::print()
{
	for(Node* iter = this->head; iter != NULL; iter = iter->next)
		cout << iter->data << " -> ";
	cout << endl;
}