Data Structures Homework #2
Description
Please implement a doubly linked list of 32bit signed integers with four functions: “InsertBack”, “InsertAfter”, “Delete” and “DeleteAll”.
Implement these functions in implement.cpp and implement.h.
Don’t try to modify files in readonly, since we will replace them and use stricter testing.
We provide a basic testing file 1.in in readonly and you can use it to evaluate correctness of your code.
Make sure your code can pass basic testing.
Note
STL is not allowed:
<list <vector <forward_list … are not allowed.
The length of linked list will not exceed 100,000.
The linked list is empty before the first input is processed.
The time limit is “60” second .
Input
There are 4 kinds of instructions in the input.
1. InsertBack (int num):
Insert num to the end of the linked list
2. InsertAfter (int num1, int num2):
Insert num2 after the first occurrence of num1
If num1 doesn’t exist in the linked list, do nothing
3. Delete (int num):
Remove the first node (from the head) with the num from the linked list.
If num doesn’t exist in the linked list, do nothing.
4. DeleteAll (int num):
Remove all the nodes with num from the linked list.
If num doesn’t exist in the linked list, do nothing.
Output
If your code is correct, the output will be “[Accepted]”.
