Doubly Linked List - Request for comments

[Telos]

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 Select Expand


// 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 Select Expand


// 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 Select Expand


// Node.cpp
#include "Node.h"

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

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

Node::~Node()
{

}


Code Select Expand


// 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 Select Expand


// 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;
}


[iago]

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

[Skywing]

In my experience it's generally more useful to use templates instead of virtual functions for datastructures like this.

[Telos]

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.

[iago]

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).

[Telos]

From what I know about templates it would look like

Code Select Expand


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.

[iago]

I was goign to say you got your code tags backwards, but you fixed that


Yes, using a template would be much nicer

[CupHead]

Someone want to turn this into a nice DLL I can use from VB?  

[Kp]

From what I know about templates it would look like

Code Select Expand


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.

[Telos]

Like

Code Select Expand


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;
?

[Kp]

Like
?

Exactly.

[Telos]

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?

[iago]

hmm, I don't think there is one.  That's a good reason NOT to do it templated, I guess

Perhaps don't sort?

[Eibro]

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.

[Telos]

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.