Doubly Linked List 

Your task is to implement a double linked list.

Write a program which performs the following operations:

• insert x: insert an element with key x into the front of the list
• delete x: delete the first element which has the key of x from the list
• deleteFirst: delete the first element from the list
• deleteLast: delete the last element from the list

Input

The input is given in the following format:

n

command₁

command₂

...

command_n

In the first line, the number of operations n is given. In the following n lines, the above mentioned operations are given in the following format:

• insert x
• delete x
• deleteFirst
• deleteLast

Output

Print all the element (key) in the list after the given operations. Two consequtive keys should be separated by a single space.

Constraints

• The number of operations ≤ 2,000,000
• The number of delete operations ≤ 20
• 0 ≤ value of a key ≤ 10⁹
• the number of elements in the list does not exceed 10⁶

Sample Input 1

7insert 5insert 2insert 3insert 1delete 3insert 6delete 5

Sample Output 1

6 1 2

Sample Input 2

9insert 5insert 2insert 3insert 1delete 3insert 6delete 5deleteFirstdeleteLast

Sample Output 2

1

题目意思是指写一个支持插入元素，删除特定元素，删除头元素，删除尾元素，打印整条链表操作的链表。

下面是初始化操作:

然后是各种普通操作顺序：

在理解后就可以看代码了，本题为了快速的删除尾，所使用的是环型链表，上代码：

1     #include 
     
         2     #include 
      
          3     #include 
       
           4     #include 
        
            5     using namespace std;   6        7     struct Node{   8       int key;   9       Node *prev;  10       Node *next;  11     };  12       13     Node *head;  14       15     Node *listSearch(int key){  16       Node *cur = head->next;  17       while(cur != head && cur->key != key){  18         cur = cur->next;  19       }  20       return cur;  21     }  22       23     void init(){  24       head = new Node;  25       head->prev = head;  26       head->next = head;  27     }  28       29     void printlist(){  30       Node *cur = head->next;  31       int isf = 0;  32       while(1){  33         if(cur == head)break;  34         if(isf++ > 0)printf(" ");  35         printf("%d",cur->key);  36         cur = cur->next;  37       }  38       printf("\n");  39     }  40       41     void insert(int key){  42       Node *x = new Node;  43       x->key = key;  44       x->next = head->next;  45       head->next->prev = x;  46       head->next = x;  47       x->prev = head;  48     }  49       50     void deleteNode(Node *t){  51       if(t == head)return;  52       t->prev->next = t->next;  53       t->next->prev = t->prev;  54       free(t);  55     }  56       57     void deleteFirst(){  58       deleteNode(head->next);  59     }  60       61     void deleteLast(){  62       deleteNode(head->prev);  63     }  64       65     void deletekey(int key){  66       deleteNode(listSearch(key));  67     }  68       69     int main(){  70       int key,n,i;  71       char com[20];  72       scanf("%d",&n);  73       init();  74       for(i = 0;i < n; i++){  75         scanf("%s%d",com,&key);  76         if(com[0] == 'i'){insert(key);}  77         else if(com[0] == 'd'){  78           if(strlen(com) > 6){  79             if(com[6] == 'F')deleteFirst();  80             else if(com[6] == 'L')deleteLast();  81           }  82           else{  83             deletekey(key);  84           }        85         }  86       }  87       printlist();  88       return 0;  89     }