/*
Quote from
Teach Yourself C++ in 24 Hours, 4th Edition
Publisher: Sams; 4 edition (August 11, 2004)
Language: English
ISBN-10: 0672326817
ISBN-13: 978-0672326813
by Jesse Liberty (Author), David Horvath (Author)
*/
// ***********************************************
// FILE: Listing 19.1
//
// PURPOSE: Demonstrate ilinked list
// NOTES:
//
// COPYRIGHT: Copyright (C) 1997 Liberty Associates, Inc.
// All Rights Reserved
//
// Demonstrates an object-oriented approach to
// linked lists. The list delegates to the node.
// The node is an abstract data type. Three types of
// nodes are used, head nodes, tail nodes and internal
// nodes. Only the internal nodes hold data.
//
// The Data class is created to serve as an object to
// hold in the linked list.
//
// ***********************************************
#include
enum { kIsSmaller, kIsLarger, kIsSame};
// Data class to put into the linked list
// Any class in this linked list must support two methods:
// Show (displays the value) and Compare
// (returns relative position)
class Data
{
public:
Data(int val):myValue(val){}
~Data(){}
int Compare(const Data &);
void Show() { std::cout << myValue << std::endl; }
private:
int myValue;
};
// Compare is used to decide where in the list
// a particular object belongs.
int Data::Compare(const Data & theOtherData)
{
if (myValue < theOtherData.myValue)
return kIsSmaller;
if (myValue > theOtherData.myValue)
return kIsLarger;
else
return kIsSame;
}
// forward declarations
class Node;
class HeadNode;
class TailNode;
class InternalNode;
// ADT representing the node object in the list
// Every derived class must override Insert and Show
class Node
{
public:
Node(){}
virtual ~Node(){}
virtual Node * Insert(Data * theData)=0;
virtual void Show() = 0;
private:
};
// This is the node which holds the actual object
// In this case the object is of type Data
// We'll see how to make this more general when
// we cover templates
class InternalNode: public Node
{
public:
InternalNode(Data * theData, Node * next);
virtual ~InternalNode(){ delete myNext; delete myData; }
virtual Node * Insert(Data * theData);
virtual void Show()
{ myData->Show(); myNext->Show(); } // delegate!
private:
Data * myData; // the data itself
Node * myNext; // points to next node in the linked list
};
// All the constructor does is to initialize
InternalNode::InternalNode(Data * theData, Node * next):
myData(theData),myNext(next)
{
}
// the meat of the list
// When you put a new object into the list
// it is passed ot the node which figures out
// where it goes and inserts it into the list
Node * InternalNode::Insert(Data * theData)
{
// is the new guy bigger or smaller than me?
int result = myData->Compare(*theData);
switch(result)
{
// by convention if it is the same as me it comes first
case kIsSame: // fall through
case kIsLarger: // new data comes before me
{
InternalNode * dataNode =
new InternalNode(theData, this);
return dataNode;
}
// it is bigger than I am so pass it on to the next
// node and let HIM handle it.
case kIsSmaller:
myNext = myNext->Insert(theData);
return this;
}
return this; // appease MSC
}
// Tail node is just a sentinel
class TailNode : public Node
{
public:
TailNode(){}
virtual ~TailNode(){}
virtual Node * Insert(Data * theData);
virtual void Show() { }
private:
};
// If data comes to me, it must be inserted before me
// as I am the tail and NOTHING comes after me
Node * TailNode::Insert(Data * theData)
{
InternalNode * dataNode = new InternalNode(theData, this);
return dataNode;
}
// Head node has no data, it just points
// to the very beginning of the list
class HeadNode : public Node
{
public:
HeadNode();
virtual ~HeadNode() { delete myNext; }
virtual Node * Insert(Data * theData);
virtual void Show() { myNext->Show(); }
private:
Node * myNext;
};
// As soon as the head is created
// it creates the tail
HeadNode::HeadNode()
{
myNext = new TailNode;
}
// Nothing comes before the head so just
// pass the data on to the next node
Node * HeadNode::Insert(Data * theData)
{
myNext = myNext->Insert(theData);
return this;
}
// I get all the credit and do none of the work
class LinkedList
{
public:
LinkedList();
~LinkedList() { delete myHead; }
void Insert(Data * theData);
void ShowAll() { myHead->Show(); }
private:
HeadNode * myHead;
};
// At birth, i create the head node
// It creates the tail node
// So an empty list points to the head which
// points to the tail and has nothing between
LinkedList::LinkedList()
{
myHead = new HeadNode;
}
// Delegate, delegate, delegate
void LinkedList::Insert(Data * pData)
{
myHead->Insert(pData);
}
// test driver program
int main()
{
Data * pData;
int val;
LinkedList ll;
// ask the user to produce some values
// put them in the list
for (;;)
{
std::cout << "What value? (0 to stop): ";
std::cin >> val;
if (!val)
break;
pData = new Data(val);
ll.Insert(pData);
}
// now walk the list and show the data
ll.ShowAll();
return 0; // ll falls out of scope and is destroyed!
}
What value? (0 to stop): 1
What value? (0 to stop): 2
What value? (0 to stop): 3
What value? (0 to stop): 4
What value? (0 to stop): 0
1
2
3
4