Description of the extra credit program

The program is to use a double array of size MAX, declared as

int table[2][MAX];

to represent an ordered linked-list of integer data. The first row of the
array holds the data values. The entry in the row below a data value is
a subscript pointer (link) to the successor data value in the list.
MAX is the null pointer indicating the end of the list.
The array is always divided between the data elements and the "free"
locations. The free locations are to be accessed via a stack
(represented inside the same double array as another linked-list).

With MAX = 10, the contents of the array at a certain time might be as
follows:

 subscript       0    1    2     3    4    5   6    7     8     9

 row 1:
 data           33    0    66   -5   67    16  0    -3    32    12
 (or free)

 row 2:
 subscript of
 next element    6     5    9     7   10   8   4     1    10    0
 of data list 
 or of next
 subscript address  
 on the free stack.

                 start = 3
                 size = 5 (size of data list)
                 top = 2

In this example, the data list is -5, -3, 0, 16, 32,

and the free locations within the array are stacked

  (from top to bottom) as 2, 9, 0, 6, 4.


Define a class LL to implement this structure.

An object consists of

int table[2][MAX];
int start;//starting address of the data list
int size;//the size of the list
int top;//the top address of the free stack

The constructor should initialize an empty LL object:

start = MAX;//position MAX is NOT in the array
size = 0;
top = 0;
table[0][i] = 0; (i=0,....,MAX-1)
table[1][i] = i+1; (i=0,...,MAX-1) //each free node points to the next
(so the entire table is a free stack)

A subscript value MAX is the null pointer, indicating the end
of the data linked list and also the bottom of the free stack.

The insert operation should pop the top-most free location from the
stack and use that for the new data item. The del operation should
return a location from which data was deleted to the top of the stack.
Insert should check for overflow and del should check for underflow.
Appropriate error messages should be printed if an operation cannot
be carried out.

Public member functions should include

 void LL::insert(int y)//insert data value y in correct order position

and

 void LL::del(int y) //delete first occurance of data value y

The stack structure for the free list should not be public.
The stack operations

void push(int address)

and

int pop()

should be internal to the class LL and should be used to suppport
the insert and del list operations. These push and pop operations should
not appear in a user application program.

The main user application program should be in a file LLtest.cpp.
For this application, use MAX = 10 in class LL.
In the application program, declare an LL object:

LL x; //empty list

Then carry out the sequence of operations described on the handout sheets:

x.insert(3);

x.insert(6);

x.insert(5);

etc.

After EACH operation, use x.printlist() (another public member function
in class LL) to print (clearly) the contents of the table array and the
values of start, size, and top.