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.

[code]
// 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
[/code]

[code]
// 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
[/code]

[code]
// Node.cpp
#include "Node.h"

Node::Node()
{
   Next = false;
   Prev = false;
}

Node::Node( Node *PointedNode )
{
   Next = PointedNode;
   Prev = PointedNode;
}

Node::~Node()
{

}
[/code]

[code]
// 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;
}
[/code]

[code]
// 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;
}
[/code]

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 author=Skywing link=board=30;threadid=3776;start=0#msg30804 date=1069554010]
In my experience it's generally more useful to use templates instead of virtual functions for datastructures like this.
[/quote]

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

[code]
template <class T>
class LinkedList
{
...
T *First;
T *Last;
...
};

// then

LinkedList <Node> LL;
LinkedList <SomeDataStructure> LL;

[/code]

... 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 author=Telos link=board=30;threadid=3776;start=0#msg30818 date=1069555617]
From what I know about templates it would look like

[code]
template <class T>
class LinkedList
{
...
T *First;
T *Last;
...
};

// then

LinkedList <Node> LL;
LinkedList <SomeDataStructure> LL;

[/code]

... Ok I see where templates would be good now you don't need to answer Skywing.
[/quote]

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

[code]
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;
[/code]?

[quote author=Telos link=board=30;threadid=3776;start=0#msg31351 date=1069778857]
Like
?
[/quote]

Exactly.

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 author=Telos link=board=30;threadid=3776;start=0#msg31358 date=1069784445]
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?
[/quote]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.