CSCI 520

Programming Assignment #4

Simulate a linear linked-list by an array

Let L be a linear linked list. We will use array A to represent L. Your task is to write a C++ program that simulates operations on L by using A, and outputs results.

The following is an example snapshot of L and A at some given time:

struct node {

int data;

int next;

};

struct node A[100] ;

*here only the struct node given is used no other variables

ASSUME THAT THE LIST DOES NOT CONTAIN MORE THAN 100 ELEMENTS, AND ALL ELEMENTS IN THE LIST ARE DISTINCT

A:

Never used

0 not assigned

1 5 2

2 4 3

3 6 0

Again, we assume that each node in L contains a distinct data value

Do the following operations on A:

HERE WE IMAGINE OPERATIONS ON L, BUT ACTUALLY DO THEM ON A

NEVER USE A[0]

THE next field in A[i] GIVES YOU THE SUCCESSOR NODE

YOU MAY USE -1 IN THE NEXT FIELD TO MARK THE FREE CELLS IN A, AND WHEN YOU NEED A CELL FOR NEW NODE YOU CAN USE THESE FREE CELLS

A y : Create a new node with data value y, and append this node to L

I x y : Find the node t with value x, create a new node p with data value y, and insert node p after t in L

D y : Find the node with data value y, and delete that node from L

P: Double (multiply by two) all existing values (not indices) in nodes of L.

R : Reverse L

T : Output all data values in L

Sample Input/Output:

A 5

A 1

I 5 4

I 1 9

A 7

I 9 8

D 9

D 8

T

5 4 1 7

R

T

7 1 4 5

P

T

14 2 8 10