Balls
Objective
The objective of this problem is to test the students’ understanding on Doubly Linked List.
Problem Description
There are N balls labelled with 1, 2, 3,…, N, from left to right. Now, we want to do two kinds of operations:
1. “A x y”: move the ball labelled x to the left of the ball labelled y, where x ≠ y.
Reminder: if x is on the left of y, you may ignore this operation.
2. “B x y”: move the ball labelled x to the right of the ball labelled y, where x ≠ y.
Reminder: if x is on the right of y, you may ignore this operation.
3. “R x”: remove the ball labelled x.
Print the final arrangement after M operations.
Input
The first line contains two integers, N (1<= N <= 1,000) and M (1<= M <= 1,000). The next M lines contain the operations.
Output
Output the final arrangement of the N balls from left to right. Each number is followed by a whitespace.
Sample Input
10 5
A 2 1
A 10 1
A 5 6
B 6 9
R 3
Sample Output
2 10 1 4 5 7 8 9 6
Explanation
0th operation: 1 2 3 4 5 6 7 8 9 10
1st operation: 2 1 3 4 5 6 7 8 9 10
2nd operation: 2 10 1 3 4 5 6 7 8 9
3rd operation: 2 10 1 3 4 5 6 7 8 9
4th operation: 2 10 1 3 4 5 7 8 9 6
5th operation: 2 10 1 4 5 7 8 9 6
Algorithm Template
1. What data structure should be used to simulate the operations?
2. What should be updated for insertion and deletion operations?
3. What is the complexity for your algorithm?
