Description

In this homework, you are asked to implement some common functions used in linked list. For example, insert, delete, reverse, clear, and print. Notice: there exist no duplicated elements in the linked list.

1. InsertFront NewData: Insert NewData to the front of linked list.
   (NewData is an integer and is in the range of [0,500000] )
2. InsertBack NewData: Insert NewData to the end of linked list.
3. InsertBefore K NewData: Insert NewData before the node containing K.
4. InsertBack K NewData: Insert NewData after the node containing K.
   (For command InsertBefore and InsertBack, if there is no node containing K, then do nothing.)
5. Delete K: Delete the node containing K and free the memory.
6. DeleteFront: Delete the first node in linked list and free the memory.
7. DeleteBack: Delete the last node in linked list and free the memory.
   (For command Delete, DeleteFront, and DeleteBack, if there is no node containing K or the linked list is empty, do nothing.)
8. Reverse K J: Reverse all nodes between K and J, including K and J.
   (For command Reverse, if K and J do not both exist in the linked list, then do nothing. If K and J both exist in the linked list, then K is near the head of linked list compared to J.)
9. Clear: Clear the linked list and free the memory.
10. Print: Output all the data in the linked list from the first one to the last.
    (For command Print, every element is followed by a blank character and a newline character in the end of line.)

Input

N lines of commands with N<=200000. Every element following a command is an integer. No duplicate numbers exist in the linked list at the same time.

Output

For output command “Print”, print out all the integers stored in the linked list. If the linked list is empty, print nothing but a new line character.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss