• The contiguous design of stacks and queues worked just fine. All operations were constant time.
• But the contiguous design of the list ADT was not quite as good. Because insert and erase operations took linear time. We had to slide the rest of the elements in the list

template<class T,int Max >

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();

}

• The list will be implemented using a node that has two fields
  • First is the item and second field points to the next node in the list.
• We will use four variables: head, before, cursor which are pointers to various nodes
• size is an integer
• head always points to the first element in the list
• cursor points to the current element and before points to the element before the current element. The value of before is undefined if cursor is pointing to the first element.
• list()

size=0; head=cursor=0;

• is_empty()

return size==0;

• is_full()

return size==Max;

• reset()

cursor = head;

• end_of_list()

return cursor==0; // assuming that null == 0

• advance()

before = cursor; cursor = cursor->next;

• cursor->next is the next field of the node that cursor is pointing to

• current_item()

return cursor->item;

• insert_before(); // Post condition is a problem

create a new_node;

new_node->item=item;

new_node->next = cursor;

if(cursor == head)

head = new_node;

else

before->next=new_node;

cursor = new_node;

• insert_after()

create a new_node;

new_node->item=item;

new_node->next =cursor->next;

cursor->next = new_node;

before = cursor;

cursor = new_node;

• erase()

if (head == cursor)

{

head = cursor->next;

destroy cursor;

cursor = head;

}

else

{

before->next = cursor->next;

destroy cursor;

cursor = before->next;

}

• ~list()

for(cursor = head; cursor != 0;)

{

temp = cursor;

cursor = cursor->next;

destroy temp;

}

• Only destructor is linear time all other operations are constant time. This is acceptable because destructor is called only once.

• Define the node type;

template <class T>

struct node

{

T item;

node<T> *next;

};

• Pointers are special variables that CAN store addresses of another variable

int j, *ip;

• j is an integer and ip is a variable that can store address of an integer.
• If you try to use ip before initializing it, there could be disastrous effects.
• You can access the location that ip is pointing to by preceding ip with an asterisk (dereferencing a pointer)
• *ip = 20;
• One way of assigning a value to ip is through the use of new operator.
• ip = new int;
• The previous call asks OS for a memory location to store an int.
• ip now gets the address of this new memory location
• return the memory location back to the operating system by using the delete operator, e.g. delete ip;
• The pointer variables should not be assigned any absolute value. For example, ip = 20; is not a good idea.
• However, we do assign ip=0; where 0 is a special value and we will make sure that if (ip == 0) we don't use *ip;
• node<int> *x;
• x can store address of a type node<int>
• char takes one byte, int takes 4 bytes, short takes 2 bytes
• how much memory is required to store a pointer to char, int, short?
• it is always same 4 bytes
• If you had a class called something which needs 3000 bytes
• something *sp;
• sp only takes 4 bytes
• template <class T>
• struct node
• {
• T item;
• node<T> next;
• };
• The above definition doesn't work because compiler cannot calculate size of node

template <class T>

struct node

{

T item;

node<T> *next;

};

template<class T,int Max >

class list

{

private:

node<T> *head,*cursor,*before;

int size;

list();

bool is_empty();

bool is_full();

void reset();

bool end_of_list();

void advance();

T current_item();

void insert_before(T some_item);

void insert_after(T some_item);

void erase();

~list();

};

template<class T, int Max>

list<T,Max>::list()

{

size=0; head=cursor=0;

}

template<class T, int Max>

void list<T,Max>::insert_before(T item)

{

node<T> *new_node;

new_node = new node<T>;

new_node->item=item;

new_node->next = cursor;

if(cursor == head)

head = new_node;

else

before->next=new_node;

cursor = new_node;

}

template<class T, int Max>

void list<T,Max>::erase()

{

if (head == cursor)

{

head = cursor->next;

delete cursor;

cursor = head;

}

else

{

before->next = cursor->next;

delete cursor;

cursor = before->next;

}

}