Reinventing the wheel : C++ Linked List

Hasard du web ou magie des mots clés, j’ai l’impression en ce moment de ne lire que des posts ou les auteurs se demandent si les programmeurs de nos jours ne sont pas incompétents et paresseux comparés à leurs prédécesseurs…
La question du lien précédent a généré un nombre impressionnant de réponses en une demi journée.

Il y a aussi cet article de Joel Spolsky, co-fondateur de Stack Overflow, qui critique la simplification des cours d’IT : selon lui, en enseignant le Java plutôt que le C, et en évitant les vrais problèmes : pointeurs et récursion, la sélection ne se fait plus, et les programmeurs formés sont mauvais.

En tant que recruteur il écrit :

I used to be able to tell the smart kids because they could rip through a recursive algorithm in seconds, or implement linked-list manipulation functions using pointers as fast as they could write on the whiteboard. But with a JavaSchool Grad, I can’t tell if they’re struggling with these problems because they are undereducated or if they’re struggling with these problems because they don’t actually have that special part of the brain that they’re going to need to do great programming work.

Et c’est ce qui m’a interpelé : Je ne programme quasiment qu’en C# – langage (presque) sans pointeurs -, et même si je connais le C ou le C++ de façon théorique (en plus des cours de SUPINFO), je n’ai pas beaucoup pris le temps de faire des choses un peu poussées avec, n’y voyant pas d’intérêt.

Même si je ne le fais pas aussi vite que j’écrirais sur un tableau blanc, suis je capable d’implémenter une liste chainée et les fonctions qui vont avec ?

Do I have that special part of the brain?

Entrons dans le vif

J’ai commencé naïvement, avec une seule classe comprenant à la fois la structure (un int et deux int*), et les fonctions de manipulation, en ayant en tête une liste doublement chainée d’int.
Je me suis vite rendu compte que je ne me servais jamais des deux liens, je suis donc passé à une liste simplement chainée.

Comme j’étais arrivé à un résultat utilisable rapidement, j’en ai profité pour apprendre quelques petites choses sur les templates C++, en rendant ma liste générique o/.
J’ai aussi fini par séparer les éléments de la liste, de la liste elle même.

J’avais en tête les List de C#, accessibles via un indexer, mais le C++ a eu raison de moi sur ce point: pas moyen de faire marcher mon opérateur [], 🙁 finalement le principe reste le même, mais avec une fonction Get(int index)…

Et voici venu le moment de vous coller mes 219 lignes de C++ 😄 (merci WordPress de me supprimer tous mes sauts de ligne…)
(codées avec Visual studio bien sur, d’ou le #pragma once…)

#pragma once
#include <iostream>

template <class T>
//Linked List Item, the user doesn't need to use this class
class LListItem
{
public:
	LListItem(T value);
	LListItem(LListItem<T>* next, T value);
	~LListItem(void);
	bool HasNext(void);
	T value;
	LListItem<T>* next;
protected:
	void Init(LListItem<T>* next, T value);
	
};

/******************************************************************************/

template <class T>
//Linked List object
class LList
{
public:
	LList(void);
	~LList(void);
	void Add(T value);
	void InsertAfter(int index, T value);
	void RemoveAt(int index);
	void Clear(void);
	T Get(int index);
	int Count(void);
	static const int ERROR_OUT_OF_BOUNDS = 0x100;
protected:
	LListItem<T>* first;
	LListItem<T>* last;
	int count;
};

/******************************************************************************/

template <class T>
LListItem<T>::LListItem(T value)
{
	Init(NULL, value);
}

template <class T>
LListItem<T>::LListItem(LListItem<T>* next, T value)
{
	Init(next, value);
}

template <class T>
void LListItem<T>::Init(LListItem<T>* next, T value)
{
	this->next = next;
	this->value = value;
}

template <class T>
bool LListItem<T>::HasNext()
{
	return this->next != NULL;
}

template <class T>
LListItem<T>::~LListItem(void) {}

/******************************************************************************/

template <class T>
LList<T>::LList(void)
{
	this->first = NULL;
	this->last = NULL;
	this->count = 0;
}

template <class T>
LList<T>::~LList(void)
{
	this->Clear();
}

template <class T>
int LList<T>::Count()
{
	return this->count;
}

template <class T>
void LList<T>::Add(T value)
{
	if(this->first == NULL)
	{
		this->first = new LListItem<T>(value);
		this->last = this->first;
		this->count = 1;
	}
	else
	{
		LListItem<T>* newLast = new LListItem<T>(NULL, value);
		this->last->next = newLast;
		this->last = newLast;
		this->count++;
	}
}

template <class T>
void LList<T>::InsertAfter(int index, T value)
{
	if(this->first != NULL && index >= 0)
	{
		LListItem<T>* iterator = this->first;
		int i = 0;
		while(i != index)
		{
			if(!iterator->HasNext())
			{throw LList::ERROR_OUT_OF_BOUNDS;}
			iterator = iterator->next;
			i++;
		}
		LListItem<T>* afterIterator = iterator->next;
		iterator->next = new LListItem<T>(afterIterator, value);
		if(this->last == iterator)
		{
			this->last = iterator->next;
		}
		this->count++;
	}
	else if(this->first != NULL && index == -1)
	{
		//special case, we insert at index 0
		this->first = new LListItem<T>(this->first, value);
		this->count++;
	}
	else
	{
		throw LList::ERROR_OUT_OF_BOUNDS;
	}
}

template <class T>
void LList<T>::Clear()
{
	if(this->first != NULL)
	{
		LListItem<T>* iterator = this->first;
		LListItem<T>* temp = NULL;
		do
		{
			//keep a reference on the next, and delete the current
			temp = iterator->next;
			delete iterator;
			iterator = temp;
		} while(iterator != NULL);
		this->count = 0;
		this->first = NULL;
		this->last = NULL;
	}
}

template <class T>
void LList<T>::RemoveAt(int index)
{
	if(this->first != NULL && index >= 0)
	{
		LListItem<T>* iterator = this->first;
		LListItem<T>* prev = NULL;
		int i = 0;
		while(i != index)
		{
			if(!iterator->HasNext())
			{throw LList::ERROR_OUT_OF_BOUNDS;}
			prev = iterator;
			iterator = iterator->next;
			i++;
		}
		if(prev != NULL)
		{
			if(iterator->next != NULL)
			{
				prev->next = iterator->next;
			}
			else
			{
				//we are going to delete the last item
				prev->next = NULL;
				this->last = prev;
			}
		}
		else
		{
			//we are going to delete the first item
			if(iterator->next != NULL)
			{
				this->first = iterator->next;
			}
			else
			{
				//there are only one item
				this->first = NULL;
			}
		}
		delete iterator;
		this->count--;
	}
	else
	{
		throw LList::ERROR_OUT_OF_BOUNDS;
	}
}

template <class T>
T LList<T>::Get(int index)
{
	if(this->first != NULL && index >= 0)
	{
		LListItem<T>* iterator = this->first;
		int i = 0;
		while(i != index)
		{
			if(!iterator->HasNext())
			{throw LList::ERROR_OUT_OF_BOUNDS;}
			iterator = iterator->next;
			i++;
		}
		return iterator->value;
	}
	else
	{
		throw LList::ERROR_OUT_OF_BOUNDS;
	}
}

/******************************************************************************/

Je n’ai bien sur googlé aucune source similaire avant de commencer. Quel challenge sinon ?
J’ai quand même eu besoin de faire quelques recherches sur la syntaxe du C++, pour les templates entre autres…

Conclusion

une soirée pour coder une liste chainée, en en ayant qu’une connaissance théorique. Je me sens un peu rassuré 🙂

J’ai appris à mes dépends que le chainage de constructeur n’existait pas en C++,
j’ai appris à utiliser les templates en C++,
j’ai appris que lors de l’utilisation de templates, on ne pouvait pas séparer le .h du .cpp …

Je me suis souvenu pourquoi je faisais du C#… 😄

Un petit bonus pour les développeurs : Test Yourself. (j’en ai réussi deux sur trois facilement.)

Codé sur une terrasse ensoleillée, en écoutant Access To Arasaka.