IMPLEMENTATION STL (LIST)

// Implémentation de la List

/* List.h : class for double linked list */
/* Writed by Taron_ -> GPL attitude ;) */

#ifndef _LIST_H_
#define _LIST_H_

#include <iostream>
using namespace std;

/* Types of errors */
#define ERROR_ALLOCATE_HEAP 1
#define ERROR_FREE_HEAP     2

#define OK 0

/* Class declaration */

template <typename T> 
class List
{
 private:
   struct Link   // Struct for linked list
   {
      T Value;   // Value of new object
       
      Link *Next;
      Link *Prev;
   };
          
   typedef struct Link Link;            
   Link *End;   

 public:
   List();   /* Constructor & Destructor */
  ~List();

   friend ostream& operator<<(ostream&, List<T>);

   int push_front(T);  /* Insert a element */
   int push_back(T);
   
   void pop_front();   /* Delete a element */
   void pop_back();
 
   void remove(T);

   Link* begin();   /* Get address for begin and end of list */
   Link* end();

   Link *Temp, *Head;
};

template <typename T>
ostream& operator<<(ostream& Out, List<T> L)
{
   L.Temp = 0;

   if(L.Head->Value == 0) L.Temp = L.Head->Next;
   else L.Temp = L.Head;

   /* Display all object */
   for(; L.Temp != 0 ; L.Temp = L.Temp->Next)
      cout << L.Temp->Value << endl;             

   return Out;
}

template <typename T>
List<T>::List()   /* Constructor */
{
   Head = (Link *)malloc(sizeof(Link));   /* Prepare the list */
  
   Head->Next = 0;
   Head->Prev = 0;
   
   Head->Value = 0;

   End = Head;   
}

template <typename T>
List<T>::~List()   // Destructor
{
   Temp = 0;
   
   if(Head->Value == 0) Temp = Head->Next;
   else Temp = Head;   

   for(; Temp != 0 ; Temp = Temp->Next);
   // free(Temp);
}

template <typename T>
int List<T>::push_front(T Value)   /* Add a value front of the list */
{
   Link *New = 0;
   New = (Link *)malloc(sizeof(Link));

   if(Head->Value != 0)
   {
      if(!New) return ERROR_ALLOCATE_HEAP;   // Can't allocate heap memory !
   
      New->Next = Head;
      New->Prev = 0;
   
      Head->Prev = New;
      New->Value = Value;

      Head = New;   // Update of new Head
   }

   else Head->Value = Value;

   return OK;
}

template <typename T>
int List<T>::push_back(T Value)   /* Add a value at the end of the list */
{
   Temp = 0;
   Link *New = 0;
   
   if(Head->Next != 0)
   {
      for(Temp = Head ; Temp->Next != 0 ; Temp = Temp->Next); 
   }

   else Temp = Head;
   
   New = (Link *)malloc(sizeof(Link));   // Allocate memory for new object
   if(!New) return ERROR_ALLOCATE_HEAP;   // Can't allocate heap memory !

   Temp->Next = New;

   New->Prev = Temp;   /* Insert into list */
   New->Next = 0;

   New->Value = Value;
   End = New;

   return OK;
}

template <typename T>
void List<T>::pop_front()   /* Delete the first element of the list */
{
   Temp = Head;

   Head = Head->Next;
   free(Temp);   // Be free
}

template <typename T>
void List<T>::pop_back()   /* Delete the last element of the list */
{
   Temp = 0;

   for(Temp = Head ; Temp->Next != 0 ; Temp = Temp->Next);
   
   Temp->Prev->Next = 0;
   free(Temp);   // Free
}

template <typename T>
void List<T>::remove(T Value)
{
   if(Head->Value == 0) Temp = Head->Next;
   else Temp = Head;

   Link *Copy = 0;

   /* Moving in the list */
   for(; Temp != 0 ; Temp = Temp->Next)
      if(Temp->Value == Value)
	  {
         Copy = Temp->Prev;
         
		 if(Temp->Prev != 0)
		   Temp->Prev->Next = Temp->Next;
	
		 if(Temp->Next != 0)
		   Temp->Next->Prev = Temp->Prev;
         
   		 free(Temp);
		 Temp = Copy;
	  }
}

template <typename T>
List<T>::Link* List<T>::begin()
{
   return Head;   // Return head of the list
}

template <typename T>
List<T>::Link* List<T>::end()
{
   return End;   // Return end of the list
}

#endif



// voici un court exemple d'utilisation

#include <iostream>
#include "List.h"

using namespace std;


int main()
{
    List<char> l;
    
    l.push_back('z');
    l.push_back('p');
    l.push_front('r');
    l.push_back('b');
    l.push_front('p');
    l.push_back('i');
    l.push_front('p');
    l.push_back('u');
    l.push_back('p');

    cout << l << endl;

    l.remove('p');

    cout << l << endl;

    l.pop_front();
    l.pop_back();

    return 0;
}