[AOJ]双方向連結リストの問題で合格できません

前提・実現したいこと

AIZU ONLINE JUDGEの「双方向連結リスト」の問題で合格できません。

テストケースの9番目で実行時間オーバーになってしまいます。

以下のソースコードのどこに問題があるでしょうか？

お手数をおかけいたしますが、問題については以下のページをご覧ください。
テストケースについてもページの下の方に掲載されています。
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_3_C

どうぞよろしくお願いいたします。

該当のソースコード

C++
1#include <bits/stdc++.h>
2using namespace std;
3
4struct cell {
5    cell *prev;
6    cell *next;
7    long value;
8};
9
10class Doubly_linked_list {
11    cell *nil;
12
13  public:
14    Doubly_linked_list() {
15        nil = new cell;
16        nil->prev = nil;
17        nil->next = nil;
18    }
19
20    cell *list_search(int x) {
21        cell *c = nil->next;
22        while(c != nil && c->value != x) {
23            c = c->next;
24        }
25        return c;
26    }
27
28    void print_list() {
29        cell *c = nil->next;
30        bool is_flag = true;
31        while(true) {
32            if(c == nil) {
33                break;
34            }
35            if(is_flag == false) {
36                cout << " ";
37            }
38            cout << c->value;
39            c = c->next;
40            is_flag = false;
41        }
42        cout << endl;
43    }
44
45    void insert(int x) {
46        cell *c = new cell;
47        c->value = x;
48        c->prev = nil;
49        c->next = nil->next;
50        nil->next->prev = c;
51        nil->next = c;
52    }
53
54    void delete_cell(cell *c) {
55        if(c == nil) {
56            return;
57        }
58        c->prev->next = c->next;
59        c->next->prev = c->prev;
60        delete c;
61    }
62
63    void delete_first() {
64        delete_cell(nil->next);
65    }
66
67    void delete_last() {
68        delete_cell(nil->prev);
69    }
70
71    void delete_value(int x) { delete_cell(list_search(x)); }
72};
73
74int main() {
75    long n;
76    cin >> n;
77    Doubly_linked_list l;
78    for(int i = 0; i < n; i++) {
79        string str;
80        cin >> str;
81        if(str == "insert") {
82			int x;
83			cin >> x;	
84            l.insert(x);
85        } else if(str == "deleteFirst") {
86            l.delete_first();
87		} else if (str == "deleteLast") {
88			l.delete_last();
89        } else {
90			int x;
91			cin >> x;
92            l.delete_value(x);
93        }
94    }
95
96    l.print_list();
97    return 0;
98}