• The ADT definition
  • Specify the member functions
  • The value the function returns, parameter the function accepts
  • Pre and Post conditions
  • Pre condition specifies what should be the state of the programs before starting the function
    • If caller doesn't guarantee the precondition, then he cannot expect correct results
  • Post condition specifies the state of the program after the function is executed

template<class item_type,int max_size>

class list

{

list();

boolean is_empty();

boolean is_full();

void reset();

boolean end_of_list();

void advance();

item_type current_item();

void insert_before(item_type some_item);

void insert_after(item_type some_item);

void erase();

~list();

}

• Any good program starts with initializations and ends with clean-ups.
• Use of any data structure should start with initializations and end with proper clean-up.
• When you create the data structure, you should make it clear to the calling programs that the data structure will not work if it is not properly initialized and may leave garbage if they are not properly destroyed.
• Constructors and destructors eliminate the possibility that the calling programs are not doing the initialization and clean-up.
• A constructor is called when a variable is created and destructor is called when the variable goes out of scope
• Constructor has the same name as the data type and doesn't return anything (different from saying the return type is void). Destructor has the same name as the type except it is preceded by a tilde (~) and doesn't return anything.
• A constructor can accept parameters but a destructor cannot.

• Use an array to store the elements of the list
• An integer called cursor to store the current position
• An integer called size to keep track of the number of elements in the list
• cursor will keep the position of the current item. When there are no items the cursor will be zero. When the cursor is at the end of the list cursor will be size+1
• If we use C++ arrays, the index is one less than the position. The current item will have the index cursor-1.

list()

size = 0;

cursor = 1;

is_empty()

return size == 0;

if (size == 0)

return true

else

return false

is_full()

return size == max_size;

reset()

cursor = 1; // Precondition list is not empty

end_of_list()

return cursor== size+1;

advance()

cursor++;

current_item()

return a[cursor-1]

insert_before(item_type some_item)

for(j = size; j >=cursor; j--)

a[j] = a[j-1];

a[cursor-1] = some_item;

size++;

insert_after(item_type some_item)

for(j = size; j >cursor; j--)

a[j] = a[j-1];

a[cursor] = some_item;

cursor++; size++

erase()

for(j=cursor; j<size; j++)

a[j-1]=a[j];

size--;

• All operations except, insert(s) and erase take constant time. Insert(s) and erase take linear time.

• Separate the ADT into two parts header in HPP and implmentation in CPP
• HPP

template<class item_type,int max_size>

class list

{

item_type a[max_size];

int size,cursor;

public:

list();

boolean is_empty();

boolean is_full();

void reset();

boolean end_of_list();

void advance();

item_type current_item();

void insert_before(item_type some_item);

void insert_after(item_type some_item);

void erase();

~list();

};

• CPP

template<class item_type,int max_size>

list<item_type,max_size>::list()

{

size = 0;

cursor = 1;

}

template<class item_type,int max_size>

boolean list<item_type,max_size>::is_empty()

{

return size == 0;

}