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);
}
}
}
templated linked list
Author
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?
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
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.
Author
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?
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?
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.
Author
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); };
Author
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?
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: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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
