I wrote this doubly linked list to learn more about data structures. I think the bugs have been worked out but this may not be the case. If anyone has comments for how it could be made better I want to know.
// Node.h
#ifndef _NODE_H_
#define _NODE_H_
#include <iostream.h>
class Node
{
public:
Node();
Node( Node *PointedNode );
virtual ~Node();
void DisplayContents( void ) { cout << Contents << endl; }
Node *Next;
Node *Prev;
// Better to inherit this class than put the data directly in like this.
char Contents[256];
};
#endif
// LinkedList.h
#ifndef _LINKEDLIST_H_
#define _LINKEDLIST_H_
#include "Node.h"
class LinkedList
{
public:
LinkedList();
~LinkedList();
Node *First;
Node *Last;
void InsertAtFront( Node *NewNode );
void InsertAtBack( Node *NewNode );
void InsertInOrder( Node *NewNode, bool CaseSensitive );
void RemoveFromFront( void );
void RemoveFromBack( void );
void RemoveByIndex( unsigned int Index );
Node *GetNodeByIndex( unsigned int Index );
unsigned int GetNodeCount( ) { return NodeCount; }
private:
unsigned int NodeCount;
};
#endif
// Node.cpp
#include "Node.h"
Node::Node()
{
Next = false;
Prev = false;
}
Node::Node( Node *PointedNode )
{
Next = PointedNode;
Prev = PointedNode;
}
Node::~Node()
{
}
// LinkedList.cpp
#include <string.h>
#include "LinkedList.h"
LinkedList::LinkedList()
{
First = new Node;
Last = new Node( First );
First->Next = Last;
Last->Prev = First;
// Unneeded but useful during debugging
strcpy(First->Contents, "[First]");
strcpy(Last->Contents, "[Last]");
NodeCount = 0;
}
LinkedList::~LinkedList()
{
}
void LinkedList::InsertAtBack( Node *NewNode )
{
NewNode->Prev = Last->Prev;
NewNode->Next = Last;
Last->Prev->Next = NewNode;
Last->Prev = NewNode;
NodeCount++;
}
void LinkedList::InsertAtFront( Node *NewNode )
{
NewNode->Prev = First;
NewNode->Next = First->Next;
First->Next->Prev = NewNode;
First->Next = NewNode;
NodeCount++;
}
void LinkedList::InsertInOrder( Node *NewNode, bool CaseSensitive )
{
int i;
int strResult;
int strResult2;
Node *TempNode;
if( GetNodeCount() == 0 )
{
InsertAtFront( NewNode );
return;
}
for( i = 1; i <= GetNodeCount(); i++ )
{
TempNode = GetNodeByIndex( i );
if( CaseSensitive )
{
strResult = strcmp( NewNode->Contents, TempNode->Contents );
strResult2 = strcmp( NewNode->Contents, TempNode->Next->Contents );
} else {
strResult = _stricmp( NewNode->Contents, TempNode->Contents );
strResult2 = _stricmp( NewNode->Contents, TempNode->Next->Contents );
}
if( (strResult < 0) && (TempNode->Prev == First) )
{
InsertAtFront( NewNode );
return;
}
if( (strResult > 0) && (strResult2 < 0) )
{
NewNode->Prev = TempNode;
NewNode->Next = TempNode->Next;
TempNode->Next = NewNode;
TempNode->Next->Prev = NewNode;
NodeCount++;
}
if( (strResult > 0) && (TempNode->Next == Last) )
{
InsertAtBack( NewNode );
return;
}
}
}
void LinkedList::RemoveFromBack()
{
if( NodeCount < 1 ) return;
Node *TempNode = Last->Prev;
TempNode->Prev->Next = Last;
Last->Prev = TempNode->Prev;
delete TempNode;
NodeCount--;
}
void LinkedList::RemoveFromFront()
{
if( NodeCount < 1 ) return;
Node *TempNode = First->Next;
TempNode->Next->Prev = First;
First->Next = TempNode->Next;
delete TempNode;
NodeCount--;
}
void LinkedList::RemoveByIndex( unsigned int Index )
{
if( NodeCount < 1 ) return;
unsigned int i;
Node *TempNode;
TempNode = this->First;
for( i = 0; i < Index; i++ )
{
TempNode = TempNode->Next;
}
TempNode->Prev->Next = TempNode->Next;
TempNode->Next->Prev = TempNode->Prev;
delete TempNode;
NodeCount--;
}
Node *LinkedList::GetNodeByIndex( unsigned int Index )
{
unsigned int i;
Node *ReturnedNode;
ReturnedNode = this->First;
for( i = 0; i < Index; i++ )
{
ReturnedNode = ReturnedNode->Next;
}
return ReturnedNode;
}
// LinkedListTest.cpp
#include "Node.h"
#include "LinkedList.h"
#include <string.h>
#include <stdlib.h>
int main()
{
LinkedList MyList;
Node *MyNode;
int Count;
MyNode = new Node;
strcpy(MyNode->Contents, "a");
//MyList.InsertAtBack( MyNode );
MyList.InsertInOrder( MyNode, true );
MyNode = new Node;
strcpy(MyNode->Contents, "b");
//MyList.InsertAtFront( MyNode );
MyList.InsertInOrder( MyNode, true );
MyNode = new Node;
strcpy(MyNode->Contents, "c");
//MyList.InsertAtBack( MyNode );
MyList.InsertInOrder( MyNode, true );
MyNode = new Node;
strcpy(MyNode->Contents, "FIRST");
//MyList.InsertAtFront( MyNode );
MyList.InsertInOrder( MyNode, true );
cout << MyList.GetNodeCount() << endl;
for( Count = 1; Count <= MyList.GetNodeCount(); Count++ )
{
MyNode = MyList.GetNodeByIndex( Count );
cout << Count << ": ";
MyNode->DisplayContents();
}
MyList.RemoveFromBack();
cout << MyList.GetNodeCount() << endl;
for( Count = 1; Count <= MyList.GetNodeCount(); Count++ )
{
MyNode = MyList.GetNodeByIndex( Count );
cout << Count << ": ";
MyNode->DisplayContents();
}
MyList.RemoveFromFront();
cout << MyList.GetNodeCount() << endl;
for( Count = 1; Count <= MyList.GetNodeCount(); Count++ )
{
MyNode = MyList.GetNodeByIndex( Count );
cout << Count << ": ";
MyNode->DisplayContents();
}
system("PAUSE");
return 0;
}
It looks really nice!
I'm glad you used iterative stuff rather than recursive, that's the biggest mistake I normally see.
From there, it's a short change to write a binary tree. You should do that :)
In my experience it's generally more useful to use templates instead of virtual functions for datastructures like this.
Quote from: Skywing on November 22, 2003, 08:20 PM
In my experience it's generally more useful to use templates instead of virtual functions for datastructures like this.
Could you possibly explain what you mean? I am not sure what use templates would be in this case.
I don't know how to create a templated class, but it would be like this:
Say you wanted to store an int in your list
DoubleList <int> blah;
blah.add(5);
..etc.
It'll assume that all data being added is an int. It's nice, but doesn't port well to other languages (like Java) and is rather nasty to implement (this badly needs to be fixed).
From what I know about templates it would look like
template <class T>
class LinkedList
{
...
T *First;
T *Last;
...
};
// then
LinkedList <Node> LL;
LinkedList <SomeDataStructure> LL;
... Ok I see where templates would be good now you don't need to answer Skywing.
I was goign to say you got your code tags backwards, but you fixed that :P
Yes, using a template would be much nicer :)
Someone want to turn this into a nice DLL I can use from VB? :P
Quote from: Telos on November 22, 2003, 08:46 PM
From what I know about templates it would look like
template <class T>
class LinkedList
{
...
T *First;
T *Last;
...
};
// then
LinkedList <Node> LL;
LinkedList <SomeDataStructure> LL;
... Ok I see where templates would be good now you don't need to answer Skywing.
Actually, I think he meant for you to use type T for the contained data, not for the nodes. Then you'd be able to do LinkedList<MyBot> to create a list of MyBot objects, or LinkedList<int> to get a LL of ints.
Like
template <class T>
class LinkedList
{
...
Node<T> *First;
Node<T> *Last;
...
};
// with
template <class T>
class Node
{
Node *Prev;
Node *Next;
T Contents;
};
// and
struct contentStruct
{
char szData[256];
};
// then
LinkedList<contentStruct> MyList;
With a templated node like that what is the best way to go about doing the InsertInOrder function because there will not be any standard comparison?
hmm, I don't think there is one. That's a good reason NOT to do it templated, I guess :)
Perhaps don't sort?
Quote from: Telos on November 25, 2003, 12:20 PM
With a templated node like that what is the best way to go about doing the InsertInOrder function because there will not be any standard comparison?
Why not? The user should define these operators for type T.
Eibro - The list takes care of what position nodes are inserted so the user would have to derive from the linked list class in order to overload the order function. If the user does not do this then they will have to either maintain a seperate list with its own order function before inserting or modify the linked list class version of InsertInOrder.
No they wouldn't. Take std::list for example.
You'll need to remove case sensitivity, since this only makes sense for strings alike. Use operators < > == in the InsertInOrder function. The user will need to overload these operators for their type in order to use the InsertInOrder function.
Or you could go the route of std::sort and accept a function or functor for the purposes of comparison.
What if they just want to put in int's, or some other type?
In Java, you could just use the interface Comparable, but this isn't Java.
I still think the best way is either to not sort it or to use an abstract class for data.
Inserting items in order into a linked list is a bad idea anyway; a list is no good for sorting. A skiplist or a tree would work better.
If you absolutely want to sort the list anyway, do like Eibro suggests. I see no problem at all with just sorting based on the regular operators, < > =, applied to the items. Those operators exist for the built-in types, and if you want to make a sorted list of some class all you have to do is define the comparison operators for that class.