建立並列印串列

題目敘述

請用單向鏈結串列實作一個整數序列，支援在尾端加入、在頭端加入、依位置插入、依位置刪除、讀取與列印。每個元素必須放在各自的節點裡，節點以指標相連；不可以偷偷用陣列存資料再假裝成串列。

提交說明

請提交 list.h 與 list.c，自行定義串列結構，並實作以下介面：

typedef struct list list;

void list_init(list *l); /* (re)initialize to empty */
void list_push_back(list *l, int x);
void list_push_front(list *l, int x);
void list_insert(list *l, int i, int x); /* insert x so it becomes index i */
void list_erase(list *l, int i); /* remove the element at index i */
int list_get(list *l, int i);
int list_size(list *l);
void list_print(list *l); /* all values, space-separated, one line */

驅動程式先讀入操作數 Q，再依序讀入 Q 個操作：pushb x、pushf x、insert i x、erase i、get i、size、print。get 與 size 各輸出一個整數；print 把整個串列以空白分隔印在同一行，串列為空時印出一個空行。所有出現的索引都合法。

輸入格式

• 第 1 行：整數 Q，表示操作數量。
• 接下來 Q 行，每行是 pushb x、pushf x、insert i x、erase i、get i、size 或 print 其中之一。

輸出格式

依操作順序輸出：get 與 size 各輸出一行整數；print 輸出一行，內容為目前所有元素（以空白分隔），串列為空時輸出空行。

限制

• 0 ≤ Q ≤ 2000
• 所有給 insert、erase、get 的索引都合法

範例

範例 1

輸入

5
pushb 1
pushb 2
pushb 3
size
print

輸出

3
1 2 3

範例 2

輸入

1
print

輸出

範例 3

輸入

4
pushb 1
pushb 2
pushf 0
print

輸出

0 1 2

範例 4

輸入

6
pushb 10
pushb 20
insert 1 15
get 1
erase 0
print

輸出

15
15 20

範例 5

輸入

3
pushb 1
pushb 2
pushb 3
print

輸出

範例 6

輸入

1
pushb 42
print

輸出

說明

• pushb 加到尾端，pushf 加到頭端；insert i x 之後 x 會成為索引 i 的元素，原本在該位置及其後的元素各往後移一格。
• 空串列的 print 仍要輸出換行，不能什麼都不印（範例 2）。
• 建議同時記錄頭指標與尾指標，讓 list_push_back 只需 O(1)，不必每次從頭走到尾。
• 驅動程式只會執行前 Q 個操作，之後多出來的行會被忽略（例如部分範例中 Q 小於實際列出的操作數，因此沒有任何輸出）。