Jump to content
  • Advertisement
Sign in to follow this  
BloodLust666

templated linked list

This topic is 4835 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

I just made this, i haven't tried it yet, but i wanted to make sure it's safe to use and there's no dangling pointers or anything. Can a few ppl just skim over it and see if there's any problems?
template <class Type>
class tLinkedList
{
	typedef struct Node
	{
		Type	*m_Item;
		Node	*m_NextNode;
		char	*m_cRefName;

		Node():m_Item(0), m_NextNode(0), m_cRefName(0){};
		~Node()	
		{
			delete m_Item; m_Item=0; 
			delete m_NextNode; m_NextNode=0; 
			m_cRefName=0;
		};

		void Insert(Type* NewItem)
		{
			if (m_NextNode)
				if (m_NextNode->m_cRefName == NewItem->m_RefName)
				{
					if (m_NextNode->m_NextNode)
						NewItem->m_NextNode = m_NextNode->m_NextNode;
					else
						NewItem->m_NextNode = 0;

					m_NextNode->m_NextNode = 0;
					m_NextNode->m_Item = 0;

					delete m_NextNode;
					m_NextNode = 0;

					m_NextNode = NewItem;
				} else {
					m_NextNode->Insert(NewItem);
				}
			else
			{
				m_NextNode = NewItem;
				NewItem->m_NextNode = 0;
			}	
		};
	};

private:
	Node			*m_Head;
	unsigned char	m_NetItems;

public:
	void Add(Type* Item, char* RefName);
	void Delete(char* RefName);
	void Shutdown();

	Type* GetItem(char* RefName);
	char  GetNetItems()	{return m_NetItems;};
};

template <class Type>
void tLinkedList<Type>::Add(Type *Item, char *RefName)
{
	if (NewItem != Null)
	{
		Type *NewItem = new Type();
		Node *NewNode = new Node();

		NewItem = Item;
		
		NewNode->m_Item = NewItem;
		NewNode->m_cRefName = RefName;

		if (m_Head == NULL || m_Head->m_cRefName == RefName)
		{
			m_Head = NewNode;
			NewNode->m_NextNode = 0;
		} else {
			m_Head->Insert(Item);
		}
	}
}



this is pretty much kinda like the <map> tempate of STL, how you can get the items by another type (in my case, a char*). The insert checks to see if it's next pointer has the same name as the new one, if so, it over writes the nextnode and i'm looking to safely delete the nextnode and replace it with the new one

Share this post


Link to post
Share on other sites
Advertisement
At first glance it looks okay to me, with one caveat: You're comparing char*s. Assuming you actually want to compare the contents of the string, you should use strcmp() instead. Also, of course, this class will have much lower performance than std::map because of its linear searching.

Share this post


Link to post
Share on other sites
alright, i'll put strcmp() in instead.

well, i know that, but i like to use all original code... but is it still pretty good code? does it have some good performance?

Share this post


Link to post
Share on other sites
Just a minor nitpick on a previous post, but when comparing strings you should favor strncmp(), wihch requires a character limit, and is less succeptible to buffer overruns.

Share this post


Link to post
Share on other sites
what about this code? except i'm deleting the node specified by the RefName


void tLinkedList<Type>::Remove(char *RefName)
{
if (strcmp(m_Head->m_cRefName, RefName) == 0)
{
Node *NewHead = new Node();

NewHead->m_NextNode = m_Head->m_NextNode;
delete m_Head; m_Head = 0;

m_Head = NewHead;
} else
m_Head->Remove(RefName);
}



void Node::Remove(char *RefName)
{
if (strcmp(m_NextNode->m_cRefName, RefName) == 0)
{
Node *NextNode = new Node();

NextNode = m_NextNode->m_NextNode;

delete m_NextNode; m_NextNode = 0;

m_NextNode = NextNode;
} else
m_NextNode->Remove(RefName);
};


Share this post


Link to post
Share on other sites
Quote:
Original post by scott_l_smith
Just a minor nitpick on a previous post, but when comparing strings you should favor strncmp(), wihch requires a character limit, and is less succeptible to buffer overruns.


should i just do

strncmp(... , RefName , sizeof(RefName));

or is there a different string function to find the length of the string?

Share this post


Link to post
Share on other sites
Quote:
Original post by EvilKnuckles666
well, i know that, but i like to use all original code...

Bad programmer. No cookie. In the long run, using the ST--and understanding how to use the STL in order to have as much flexibility as your own code--will work out MUCH better for you.[/quote]
Quote:
but is it still pretty good code?

You're using a fair amount of recursion, which looks nice but can really blow up in your face (stack overflow, and/or bad performance) if the compiler doesn't do tail-recursion optimization. Prefer iteration when iterating over elements of a container.
Quote:
does it have some good performance?

No. Insertion is O(n) in your implementation, as opposed to O(log n) in std::map.

Share this post


Link to post
Share on other sites
Quote:
Original post by scott_l_smith
Just a minor nitpick on a previous post, but when comparing strings you should favor strncmp(), wihch requires a character limit, and is less succeptible to buffer overruns.

Here there is no reasonable limit to pass to strncmp(). Keep in mind that strn* are not panaceas; they merely swap one type of security hole (buffer overflow) for another (silent failure behavior). The real solution, of course, is std::string.

Share this post


Link to post
Share on other sites
Yes. If you had used <map>, you'd be done already, your code would be more efficient, and if you ran into problems, you wouldn't have to worry about whether there was a bug in the data structure. Also, someone else would be more able to understand and maintain your code. Programmers don't use the STL because they're lazy or because they aren't "hardcore"; they use the STL because they have better things to program than data structures.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!