CSSE 2 A&DS 3: Worksheet 5 Linked List Implementation

A node that contains an integer x and a pointer to a node called next may be represented as follows:

typedef struct node{

int x;

struct node *next;

} IntNode;

This node can now be referred to as IntNode.

MakeNode is a function that creates a new node that contains the value e and a pointer that points to NULL. This function has the following prototype: IntNode * MakeNode(int e); It returns a pointer to a node.

QUESTION 1:

Using this struct and makenode function, write a class that implements a linked list. The class should have the following private attributes:

IntNode *head; //always points to the first element of the list, Null if the list is

empty

IntNode *current; //always points to the current element of the list, Null if the

current is empty

IntNode *previous; //always points to the node before the current node in the list, Null

if the current is empty or pointing at the head

int size; // maintains a record of the number of elements in the list

It should also have the following public methods:

Linkedlist(); // Constructor which initialises the list attributes to appropriate

default values

int ListSize(); //Returns the size of the list

void ToFirst(); // Moves Current to the first element in the list. All other pointers should be set to //appropriate values

void ToLast(); // Moves Current to the last element in the list. All other pointers should be set to //appropriate values

int ListisEmpty(); //Returns 1 if the list is empty, 0 otherwise

void Advance(); //Moves the current pointer on one node. All other pointers should be set to //appropriate values

void InsertAtHead(int x); //Calls MakeNode to create a new node and then adds this new node at the head of the list

void InsertAfterCurrent(int x); //Calls MakeNode to create a new node and then adds this new node after the current node in the list

void InsertBeforeCurrent(int x); //Calls MakeNode to create a new node and then adds this new node before the current node in the list

void DeleteCurrentNode(); Deletes the node current is pointing at - don't lose the end of the list.

QUESTION 2:

Rewrite your Linked list implementation so that it implements the behaviour of a stack (LIFO)

QUESTION 3:

Rewrite your Linked list implementation so that it implements the behaviour of a queue (FIFO)

NB: Todays Tutorial - Solutions to last weeks class exam.