C++ Tutorial/Data Types/linked list

Demonstrates an object-oriented approach to linked lists

<source lang="cpp">/* 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 <iostream>

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!
}</source>

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