linked list problem

  
if(the_list == NULL)
  

  
if(the_list->data == NULL)
  

  // þessi klasi er hringdengdur tvítengdur listi með dummy-node.

// 

#include <iostream>
using namespace std;

template <class T>
class C2TListi
{
	template <class T>
	struct node
	{
		T data;
		node<T>* next;
		node<T>* prev;

		// Smiður sem frumstillir data, next og prev. Sá sami og var í seinasta lokaprófi.

		// Ef engin færibreyta er gefin er kallað í færibreytulasan smið fyrir tagið T.

		node( const T& data=T(), node* next_p=0, node* prev_p=0)
		: data(data), next(next_p), prev(prev_p)
		{
			// Ef annarhvor eða báðir bendarnir eru 0, þá neda þeir á sjálfan sig

			if (next_p == 0) next = this;
			if (prev_p == 0) prev = this;
		}
	};
	
	// skilar bendi á réttan hnút miðað við data

	node<T>* FindBefore(const T& data);
	// skilar bendi á hnút á ákveðnu indexi

	node<T>* GetAt( int index);
	
	// bendir á tómt stak sem er notað sem dummy-node

	node<T>* head;
	// fjöldi staka í listanum

	int  size;
public:
	// færibreytulaus smiður

	C2TListi()  { size=0; head=new node<T>(); }
	// afritatökusmiður eða copy constructor

	C2TListi( C2TListi<T>& l) { size=0; head=new node<T>(); *this = l; }
	// eyðir eða destructor

	~C2TListi() 
	{
		while(size) RemoveAt(size-1); 
		head->next=0; head->prev=0; delete head; head=0; 
	}
	
	// almennar aðgerðir

	node<T>* AddLast(T data);
	node<T>* AddInOrder(T data);
	node<T>* Insert(T data, int index);
	node<T>* RemoveAt(int index); 
	int GetSize() { return size; } const

	// yfirskrifaðir virkjar

	friend ostream& operator << (ostream& out, const C2TListi& l);
	friend bool operator == (C2TListi& lhs,C2TListi& rhs);
	C2TListi<T>& operator = (C2TListi<T>& rhs); 


};

///////////////////////////////////////////////////////////////////////////////////


template <class T>
C2TListi<T>::node<T>* C2TListi<T>::AddLast(T data)
{
	// Set stakið aftast. Eftir þessa línu verða

	// newnode->next = head og newnode->prev = head->prev

	node<T>* newnode = new node<T>(data, head, head->prev );	

	// uppfærum þá seinasta stakið þannig að það bendi á newnode,

	// newnode er þá seinasta stakið

	head->prev->next = newnode;

	// uppfærum fyrsta stakið þannig að það bendi á seinasta stakið

	// sem nú er newnode

	head->prev = newnode;

	size++;

	return newnode;
}

///////////////////////////////////////////////////////////////////////////////////


template <class T>
C2TListi<T>::node<T>* C2TListi<T>::AddInOrder(T data)
{	
	// fáum bendi á hnútinn sem á að vera á undann nýja hnútnum

	node<T>* afterme = FindBefore(data);

	// athugum hvort listinn er tómur, bætum þá bara aftast

	if (afterme == 0) 
		return AddLast(data);	

	// Frumstillum data, next og prev í newnode, mjög líkt og í AddLast

	node<T>* newnode = new node<T>(data, afterme->next, afterme );	

	// uppfærum hnútana tvo sem eiga að koma á undan og eftir newnode

	afterme->next->prev = newnode;
	afterme->next = newnode;
	size++;

	return newnode;
}

///////////////////////////////////////////////////////////////////////////////////


template <class T>
C2TListi<T>::node<T>* C2TListi<T>::FindBefore(const T& data)
{
	// þetta fall skilar bendi á stak sem þessi tala (data) á að 

	// koma á eftir, raðað er í hækkandi röð.


	// ef listinn er tómur, þá skila 0

	if (size==0) return 0;

	// notum temp til að ferðast í gegnum listann

	node<T>* temp = head->next;

	// á meðan við erum ekki kominn út á enda listans og við erum

	// ekki kominn á réttan stað í listanum

	for(int i=0; i<size && data>temp->data; i++, temp=temp->next);

	// okkur er algeg sama hvar á að setja þetta, skilum því bara hnútnum

	// á undan. Ef ekki væri notaður dummy-node væru einhverjar if setningar 

	// settar hér

	return temp->prev;	
}

///////////////////////////////////////////////////////////////////////////////////


template <class T>
C2TListi<T>::node<T>* C2TListi<T>::GetAt( int index )
{
	if (index < 0 || index > size-1) 
		return 0;
	
	node<T>* temp=head->next;

	// athugum hvort það er fljótlegra að fara áfram eða afturábak

	if (index <= (size-1)/2)
		for(int i=0; i<index; temp=temp->next, i++);
	else
		for(int i=0; i<=(size-index); temp=temp->prev, i++);

	return temp;
}

///////////////////////////////////////////////////////////////////////////////////


template <class T>
C2TListi<T>::node<T>* C2TListi<T>::RemoveAt(int index)
{
	// fáum bendi á þann sem á að eyða

	node<T>* removeme = GetAt(index);
	
	// ef satt þá hefur index líklega verið vitlaust

	if (removeme == 0) 
		return 0;

	// fáum bendi á hnútinn sem á að skila, sem er hnúturinn á undan 

	// þeim sem á að eyða

	node<T>* temp = removeme->prev;
	
	// uppfærum hnútana tvo sem eru á undan og eftir þannig að þeir bendi

	// fram hjá removeme hnútnum

	removeme->prev->next = removeme->next;
	removeme->next->prev = removeme->prev;

	// svona til öryggis

	removeme->next = 0;
	removeme->prev = 0;

	// eyðum honum loks

	delete removeme;
	removeme = 0;

	size--;

	// skilum bendinum á undan 

	return temp;	
}

///////////////////////////////////////////////////////////////////////////////////


template <class T>
C2TListi<T>::node<T>* C2TListi<T>::Insert(T data, int index)
{
	if (index == 0)
	{
		// bætum við hnút fremst, eða strax á eftir hausnum

		node<T>* newnode = new node<T>(data, head->next, head);
		
		// uppfærum hnútana tvo sem eiga að koma á undan og eftir newnode

		head->next->prev = newnode;
		head->next = newnode;

		size++;	
		
		return newnode;
	}
	else
	{
		// fáum bendi á hnútinn sem á að vera á undan innsetningunni

		node<T>* afterme = GetAt(index-1);
	
		// ef satt þá hefur index líklega verið vitlaust

		if (afterme == 0) 
			return 0;

		// Frumstillum data, next og prev í newnode, mjög líkt og í AddLast

		node<T>* newnode = new node<T>(data, afterme->next, afterme);

		// uppfærum hnútana tvo sem eiga að koma á undan og eftir newnode

		afterme->next->prev = newnode;
		afterme->next = newnode;

		size++;
		
		return newnode;
	}

}

///////////////////////////////////////////////////////////////////////////////////


template <class T>
ostream& operator << (ostream& out, const C2TListi<T>& l)
{
	// sæki bendi á fyrsta hnútinn í listanum l

	C2TListi<T>::node<T>* temp = l.head->next;
	
	// fer í gegnum listann og skrifa út gildið í hverjum hnút.

	for(int i=0; i<l.size; i++)
	{
		cout << temp->data << endl;
		temp = temp->next;
	}

	// hægt að láta operator << skila void, en nú er hægt að 

	// gera "cout << l1 << l2"

	return out;
}

///////////////////////////////////////////////////////////////////////////////////


template <class T>
C2TListi<T>& C2TListi<T>::operator = (C2TListi<T>& rhs)
{
	if (this == &rhs)
		return *this;
	
	// hreinsum listann þannig að aðeins hausinn (dummy-node) er eftir

	while(size) RemoveAt(size-1); 	
	head->next=head; 
	head->prev=head; 
	
	// förum í gegnum rhs listann og kóperum alla hnútana þar yfir í þennan lista

	for(int i=0; i<rhs.size; i++)
		Insert(rhs.GetAt(i)->data, i);

	return *this;
}

///////////////////////////////////////////////////////////////////////////////////


template <class T>
bool operator == (C2TListi<T>& lhs, C2TListi<T>& rhs)
{
	if (&lhs == &rhs) 
		return true;

	if (lhs.GetSize() != rhs.GetSize())
		return false;
	
	// fáum bendi á fyrstu hnútana í hvorum listanum

	C2TListi<T>::node<T>* lhstemp = lhs.head->next;
	C2TListi<T>::node<T>* rhstemp = rhs.head->next;

	// förum í gegnum öll stökin og berum saman milli lista, ef data er á einhverjum 

	// stað ekki eins eru listarnir ekki nákvæmlega eins, þá skilum við fara false

	for(int i=0; i<lhs.GetSize(); i++)
	{
		if (lhstemp->data != rhstemp->data)
			return false;
		lhstemp = lhstemp->next;
		rhstemp = rhstemp->next;		
	}

	// öll stökin eru eins, skilum true

	return true;
}

///////////////////////////////////////////////////////////////////////////////////

  

  
#include <stdio.h>
#include <stdlib.h>

typedef struct list_element
{
  struct list_element *start;
  int data;
  struct list_element *previous;
  struct list_element *next;
} list_element;


list_element *add_to_list(list_element *the_list, int data)
{
  list_element *new_element;
  new_element = (list_element*)malloc(sizeof(list_element));
  new_element->data = data;

  if(the_list == NULL)
  {
    new_element->start = new_element;
    new_element->previous = NULL;
    new_element->next = NULL;
    the_list = new_element;
    printf("it''s a new list\n");
  }
  else
  {
    new_element->start = the_list->start;
    new_element->next = the_list->next;
    the_list->next = new_element;
    new_element->previous = the_list;
    printf("it''s an old list\n");
  }

  return new_element;
}


int main(int argc, char *argv[])
{
  list_element *enemy_list = NULL;

  enemy_list=add_to_list(enemy_list, 4);
  enemy_list=add_to_list(enemy_list, 2);
  enemy_list=add_to_list(enemy_list, 5);
  enemy_list=add_to_list(enemy_list, 12);

  return 1;
}