Linked List Class

[zeid]

Game Jam is over, it was fun. Even though our game failed hard. Learnt what to expect for next year. So as I said...
My linked list class. There are a couple of things to note;
*deleting a node will only delete the first node with the specified m_id, I did this as that is what I needed for my particular implementation (all m_id's are unique in my game as they corresponding to each entities ID).
*this implementation could likely be optimised a bit more with the use of itteration in place of a number of reccursive methods.
feel free to write code for the above and post it to your hearts content.

Code: Select all

/*
 *  Node.h
 *  Core
 *
 *  Created by Samuel Zeid on 24/01/10.
 *  Copyright 2010 Sam Zeid. All rights reserved.
 *
 */

#ifndef _NODE_H
#define _NODE_H

template<typename T>

class Node
{
public:
	T m_data;
	Node<T> *m_child;
	Node():m_child(0){}
	Node(Node<T> *p_this):this(p_this){}
	Node(T p_data):m_child(0),m_data(p_data){}
	//Node(Node<T> p_child,T p_data):m_child(p_child),m_data(p_data){}
};

#endif

Code: Select all

/*
 *  List.h
 *  Core
 *
 *  Created by Samuel Zeid on 24/01/10.
 *  Copyright 2010 Sam Zeid. All rights reserved.
 *
 */
#define NULL 0
#ifndef _LIST_H
#define _LIST_H

#include "Node.h"
template<typename T>
class List
{
public:
	List():m_root(NULL){}
	
	void addNode(T p_data)
	{
		_insert(m_root, p_data);
	}

	void deleteNode(T p_data)
	{
		_delete(m_root,p_data);
	}

	void empty()
	{
		_clear(m_root);
	}

	void release()
	{
		_clear(m_root);
		delete this;
	}

private:
	Node<T> *m_root;
	
	void _insert(Node<T> *&n, T p_data)
	{
		if(!n)
		{
			n=new Node<T>(p_data);
			return;
		}
		_insert(n->m_child,p_data);
	}

	void _delete(Node<T> *&n, T p_data)
	{
		if(!n)
			return;
		if(n->m_data==p_data)
		{
			Node<T> *temp(n);//Node<T> *temp = n;
			n=n->m_child;
			delete temp;
		}
		else
			_delete(n->m_child,p_data);
	}

	void _clear(Node<T> *n)
	{
		if(!n)
			return;
		_clear(n->m_child);
		delete n;
	}
};
#endif

So I got this working with a nice wrapper, and everything seems to work nicely, so I will be implementing it with my renderer soon!

[avansc]

http://elysianshadows.com/phpBB3/viewto ... art=999999

it be very easy to make that code only to delete the first m_id.

[zeid]

Thanks, but that was a non-issue for what I was trying to do. Also I have since solved all the issues of that structure by taking a different more appropriate approach I came up with which is both faster and less costly to memory.

EDIT:

Updated the code with a few optimizations.

Also for those interested, here is my Wrap class that makes up the core of my rendering system note - I make List.h a friend class

Code: Select all

/*
 *  Wrap.h
 *  Core
 *
 *  Created by Samuel Zeid on 24/01/10.
 *  Copyright 2010 Sam Zeid. All rights reserved.
 *
 */
#define NULL 0
#ifndef _WRAP_H
#define _WRAP_H

#include "List.h"
struct KeyData
{
	int m_key; //m_key identifies the sprite.
	List<int> *m_list; //m_id identifies the entity
};

class Wrap
{
public:
	Wrap()
	{
		m_root=NULL;
	}

	void addNode(int p_key, int p_id)
	{
		_insert(m_root,p_key, p_id);
	}

	void deleteNode(int p_key, int p_id)
	{
		_delete(m_root,p_key,p_id);
	}

	void empty()
	{
		_clear(m_root);
	}

	void release()
	{
		_clear(m_root);
		delete this;
	}

private:
	Node<KeyData> *m_root;

	void _insert(Node<KeyData>*&n,int p_key,int p_id)
	{
		if(!n)
		{
			n=new Node<KeyData>();
			n->m_data.m_list=new List<int>();
			n->m_data.m_list->addNode(p_id);
			n->m_data.m_key=p_key;
			return;
		}
		if(n->m_data.m_key==p_key)
		{
			n->m_data.m_list->addNode(p_id);
			return;
		}
		_insert(n->m_child,p_key,p_id);
	}

	void _delete(Node<KeyData>*&n,int p_key,int p_id)
	{
		if(!n)
			return;
		if(n->m_data.m_key==p_key)
		{
			n->m_data.m_list->deleteNode(p_id);
			if(n->m_data.m_list->m_root==NULL)
			{
				delete n->m_data.m_list;
				Node<KeyData> *temp(n);
				n=n->m_child;
				delete temp;
			}
			return;
		}
		_delete(n->m_child,p_key,p_id);
	}

	void _clear(Node<KeyData> *n)
	{
		if (!n)
			return;
		n->m_data.m_list->release();
		_clear(n->m_child);
		delete n;
	}
};

#endif