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.