The input to all the programs

MUST

be read from a file and

NOT

from command line unless specified. A

command line should specify asking for the input file name for all the programs.

1. Implement insertion, deletion and search for a doubly-linked list as defined in class. The input has a list of

pairs of an integer key followed with an operation delimited by spaces. An example of input file contents

would look like

1.in 3.in 5.in 3.del 2.in 1.sch

. There are a total of 3 operations in the input

file given:

1.

in

operation: Insertions to the doubly-linked list are to be performed at the head unless

otherwise specified. Duplicate insertions are to be rejected and

DUPLICATE KEY

should be output to the

console

.

3.in Insert node with value 3 at the head of the list

5.in_8 - Insert node with value 5 between the node with value 8

and the next node. If the node with value 8 is a tail

node, insert at the end.

2.

del

operation: Delete the node with the value of the integer key as specified.

6.del Delete the node that has value 6 in the doubly linked

list. If no such node exists, ignore the command.

3.

sch

operation: Search for the node with the value of the integer key as specified. If such a node

exists, output

FOUND

to the console, else

NOT FOUND

.

2.sch Search for a node with value 2 in the doubly linked

list. If present output FOUND to the console. If not,

output NOT FOUND to the console.

Output:

The list before operation and the list after operation displayed on the screen standard outout (not

into a file).

Example:

Input file contents:

1.in 3.in 5.in 3.del 2.in 1.sch 4.in_5

Output of the program should look like:

Operation: 1.in

List before: NULL

List after: 1

Operation: 3.in

List before: 1

List after: 3 -> 1

Operation: 5.in

List before: 3 -> 1

List after: 5 -> 3 -> 1

Operation: 3.del

List before: 5 -> 3 -> 1

List after: 5 -> 1

Operation: 2.in

List before: 5 -> 1

List after: 2 -> 5 -> 1

Operation: 1.sch

FOUND

Operation: 4.in_5

List before: 2 -> 5 -> 1

List after: 2 -> 5 -> 4 -> 1

Please do in C++ or C