// Chapter 5, p 212
// Includes WriteForward.
#include <iostream.h>

typedef int itemType;
typedef struct nodeType* ptrType;
struct nodeType
{   itemType Data;
    ptrType  Next;
};  // end struct

void LinkedListInsert(ptrType& L, itemType NewValue)
{
   ptrType P;

   if ((L == NULL) || (NewValue < L->Data))
   {  // base case: insert NewValue at beginning
      // of the linked list to which L points
      P = new nodeType;
      P->Data = NewValue;
      P->Next = L;
      L = P;
   }

   else 
      LinkedListInsert(L->Next, NewValue);
}  // end LinkedListInsert

void WriteForward(ptrType StringPtr)
// ---------------------------------------------------------
// Writes a string.
// Precondition: The string is represented as a linked list
// to which the pointer StringPtr points.
// Postcondition: The string is displayed. The linked list
// and StringPtr are unchanged.
// ---------------------------------------------------------
{
   if (StringPtr != NULL)
   {  // write the first character
      cout << StringPtr->Data;

      // write the string minus its first character
      WriteForward(StringPtr->Next);
   }  // end if
}  // end WriteForward

// ******SAMPLE MAIN PROGRAM******
main()
{  const int MAX = 10;
   typedef int arrayType[MAX];
   arrayType Input;
   ptrType ListHead = NULL;
   int Counter;

   cout << "Enter a sequence of " << MAX << " integers:\n";
   for (Counter = 0; Counter < MAX; ++Counter)
      cin >> Input[Counter];

   // create a sorted linked list from
   // the integers entered by user
   for (Counter = 0; Counter < MAX; ++Counter)
      LinkedListInsert(ListHead, Input[Counter]);

   // write contents of linked list
   cout << "\n\nThe list written forward is ===> ";
   WriteForward(ListHead);
   cout << "\n\n";

   // test funny notation for chapter
   cout << ListHead->Next->Data << " should be 2nd item.\n";
   return 0;
}