• Advertisement

Archived

This topic is now archived and is closed to further replies.

double-linked-list optimisation

This topic is 6061 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

just wanted to know how i can make this double-linked-list more efficient... i use it in my game engine A LOT, and it's crucial for it to be as fast as it can be... also, if you want to use it, feel free...
  
#ifndef __INSANE_LINKED_LIST_CLASS_HEADER__
#define __INSANE_LINKED_LIST_CLASS_HEADER__

template <class T>
class insaneNode
{
public:
	T		data;
	insaneNode<T>	*next;
	insaneNode<T>	*back;
	
	insaneNode()
	{
		next=back=NULL;
	}
	
	insaneNode(T d)
	{
		data=d;
		next=back=NULL;
	}
	
	T GetData()
	{
		return data;
	}

	void SetData(T d)
	{
		data=d;
	}
};

template <class T>
class insaneLinkedList
{
public:
	insaneLinkedList()
	{
		head=tail=spot=NULL;
		length=0;
		place=-1;
	}
	~insaneLinkedList()
	{
		MoveFirst();
		for(int i=0;i<length;i++)
		{
			Remove();
		}
	}
	
	void Insert(T data)
	{
		insaneNode<T> *p;
		p=new insaneNode<T>;
		
		p->SetData(data);
		p->next=NULL;
		p->back=NULL;
		
		if(spot==NULL)
		{
			head=tail=p;
		}
		else
		{
			if(spot->next)
			{
				spot->next->back=p;
				p->next=spot->next;
				spot->next=p;
				p->back=spot;
			}
			else
			{
				p->back=spot;
				spot->next=p;
				tail=p;
			}
		}
		
		spot=p;
		
		length++;
		place++;
	}
	
	insaneNode<T> *MoveFirst()
	{
		spot=head;
		place=0;
		return spot;
	}
	
	insaneNode<T> *MoveLast()
	{
		spot=tail;
		place=length-1;
		return spot;
	}
	
	insaneNode<T> *MoveNext()
	{
		if(spot->next)
		{
			spot=spot->next;
			place++;
		}
		return spot;
	}
	
	insaneNode<T> *MoveBack()
	{
		if(spot->back)
		{
			spot=spot->back;
			place--;
		}
		return spot;
	}
	
	insaneNode<T> *MoveTo(int who)
	{
		return FindX(who);
	}
	
	insaneNode<T> *This()
	{
		return spot;
	}
	
	insaneNode<T> *Find(T d)
	{
		if(MoveFirst())
		{
			do
			{
				if(This()->data==d)
				{
					spot=This();
					return spot;
				}
			} while(MoveNext()->next);
			if(This()->data==d)
			{
				spot=This();
				return spot;
			}
		}
		
		return NULL;
	}
	
	insaneNode<T> *FindX(int who)
	{
		if(length>0)
		{
			int p=place;

			if(p==who) return spot;
			if(p>who)
			{
				for(int i=0;i<(p-who);i++)
				{
					MoveBack();
				}
				return spot;
			}
			else
			{
				for(int i=0;i<(who-p);i++)
				{
					MoveNext();
				}
				return spot;
			}
		}
		
		return NULL;
	}
	
	void Remove()
	{
		if(spot->back)
		{
			spot->back->next=spot->next;
			if(spot->next)
			{
				spot->next->back=spot->back;
				spot=spot->next;
			}
			else
			{
				tail=spot->back;
				spot=spot->back;
			}
		}
		else
		{
			if(spot->next)
			{
				spot->next->back=NULL;
				head=spot->next;
				spot=spot->next;
			}
			else
			{
				head=tail=spot=NULL;
			}
		}
		
		length--;
	}
	
	int GetLength()
	{
		return length;
	}
	
	int GetPlace()
	{
		return place;
	}
private:
	insaneNode<T>	*head;
	insaneNode<T>	*tail;
	insaneNode<T>	*spot;					// [X MARKS THE SPOT! :]

	int		length;
	int		place;
};

#endif
  
oh, and sorry if it's kinda long and i ask so much of you... any ideas would be appreciated... everything is relative. -- even in the world of computers... so PUSH BEYOND THE LIMITS OF SANITY! Edited by - Ionut Costica on July 18, 2001 9:23:08 PM

Share this post


Link to post
Share on other sites
Advertisement
Is there any specific reason why you wanted to re-invent the wheel by writing your own Doubly linked list class ? If you think that there is no specific reason, then probably the best bet is the "list" class of the C++ standard library.

The "list" class of the C++ STL is highly optimzed and very efficient. Using this, you can leave aside technicalities of the linked list and can concentrate on your game engine optimization which is more important.

Thanks
Arun

Share this post


Link to post
Share on other sites
reasons:
1) i''m trying to implement everything i know, for this engine (my first) is like a test of my manhood
2) in any case, i''d still have to write the Find and FindX funcs, but without the support of place for FindX

everything is relative. -- even in the world of computers... so PUSH BEYOND THE LIMITS OF SANITY!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
how about storing extra nodes hanging off of the back of the tail? That way you won''t have to use new and delete so much, anytime you need a new node just grab one from the back, when you remove a node just throw it back there. Not sure if that is a gain or a loss. Keep the nodes hanging off the back singly linked. Imagine the tail''s next pointer as pointing to a stack of nodes, pop one off when you need a fresh one, push on old ones when you''re done with them.

Share this post


Link to post
Share on other sites
You can optimize it a lot by using the STL classes that come with MSVC. < Vector > comes to mind.

Edited by - Buster on July 18, 2001 11:22:57 PM

Share this post


Link to post
Share on other sites
Well, a simple change would be to stop using NULL to mark the ends of the list, use a sentinel node, and make the list circular. That would remove code for special cases on insert and delete, so would be a clear speed increase, if only a small bit.

But are you sure the linked list is the appropriate structure for your purpose? Most of the time, a linked list isn''t the best structure. There are only about two times the linked list is an appropriate data structure.


1. You need a data structure that supports insert and delete in constant time, and in HARD constant time. That is, you need EACH access to be in O(1) time, rather than a sequence of n accesses taking O(n) time. That''s a fairly rare restriction, so this reason isn''t especially common.

2. You''re chaining elements (for sequential access) inside of another data structure. Threaded binary trees are an example of this.

Of course, that list isn''t complete. There are other cases when a linked list is the best choice. But they are rather esoteric.

In just about EVERY other case, there are better options than a linked list, that depend on the application. But balanced BST''s, heaps, and resizeable arrays are the best structures for most cases... Not necessarily in that order.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

My advice is to pick up a good Data Structures book.

I do not use lists a lot, you should read about vectors.

Vectors are often better than lists and if there are lots of elements and insertion//deletion operations are needed, tree-like structures are much better...

Speed-wise good lists, good in some concrete problems are something like this, adapted to the problem in concrete:

.-Double linked. You store the next AND the previous node.
.-Circular. Next node to the "tail"(last) is the "head" (first).
.-"Chained". Don´t know how to call this . At each X nodes store an additional pointer to Y forward nodes. The same for previous nodes. This is for speeding-up the iteration, jumping parts of the list. For example, at each 10 nodes you insert a special node with two extra pointers, one pointing to 30 nodes forward and the other one to 30 nodes backwards. But this is going forward to a tree...

One advice: When you feel confortable enough with data structures, start using STL. It is better code than you and me could implement. It is standard. It is something every program needs and is not needed to be reimplemented every time...


What the hells!

Share this post


Link to post
Share on other sites
Having only passed a cursory glance over your code I have but one comment... pass your data by reference to and from your list. Of course, you cannot pass by reference if your data is itself a reference, but that is unlikely. The reason why you shouldn''t pass by value to a container object is twofold:

1) Passing by value invokes the copy constructor, which definitely means a time penalty at run time; and,

2) The copy is stored in the container class, meaning that the original is floating around somewhere in memory unless you remember your garbage collection. Again, extra computation.

Passing by reference is certainly the better way to go!

Cheers,

Timkin

Share this post


Link to post
Share on other sites
You want speed eh??
Well what I think you need is a binary tree with red-black balancing to boot

Share this post


Link to post
Share on other sites
Thanks, guys... i know it''s kinda slow, but i just want to have it right for now... until i finish the basic game engine, and i can *see* it works (on an arkanoid-type game... oh, the glorious days of the spectrum! ), i won''t try to improve it, but afterwards, i''ll look into better techniques.

everything is relative. -- even in the world of computers... so PUSH BEYOND THE LIMITS OF SANITY!

Share this post


Link to post
Share on other sites

  • Advertisement