main函数
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
int m, k, x;
char oper[4];
scanf("%d", &m);
StaticDList dList;
for (int i = 0; i < m; ++i) {
scanf("%2s", oper);
if (!strcmp("L", oper)) {
scanf("%d", &x);
dList.pushFront(x);
} else if (!strcmp("R", oper)) {
scanf("%d", &x);
dList.pushBack(x);
} else if (!strcmp("D", oper)) {
scanf("%d", &k);
dList.erase(k);
} else if (!strcmp("IL", oper)) {
scanf("%d%d", &k, &x);
dList.insertBefore(k, x);
} else if (!strcmp("IR", oper)) {
scanf("%d%d", &k, &x);
dList.insertAfter(k, x);
}
}
for (int i = dList.beginIndex(); i != dList.endIndex(); i = dList.nextIndex(i)) {
printf("%d ", dList[i]);
}
puts("");
return 0;
}
双链表
class StaticDList {
struct ListNode {
int prev;
int next;
int value;
};
public:
explicit StaticDList(int capacity = 64) {
nodeVec.reserve(capacity);
nodeVec.push_back({0, 0, 0});
}
void pushFront(int value) { insertAfter(0, value); }
void pushBack(int value) { insertBefore(0, value); }
void insertBefore(int index, int value) {
const int n = nodeVecSize();
nodeVec.push_back({nodeVec[index].prev, index, value});
nodeVec[nodeVec[index].prev].next = n;
nodeVec[index].prev = n;
}
void insertAfter(int index, int value) {
const int n = nodeVecSize();
nodeVec.push_back({index, nodeVec[index].next, value});
nodeVec[nodeVec[index].next].prev = n;
nodeVec[index].next = n;
}
void erase(int index) {
nodeVec[nodeVec[index].prev].next = nodeVec[index].next;
nodeVec[nodeVec[index].next].prev = nodeVec[index].prev;
}
inline int beginIndex() const { return nodeVec[0].next; }
inline int endIndex() const { return 0; }
inline int prevIndex(int index) const { return nodeVec[index].prev; }
inline int nextIndex(int index) const { return nodeVec[index].next; }
inline int &operator[](int index) { return nodeVec[index].value; }
private:
inline int nodeVecSize() const { return nodeVec.size(); }
vector<ListNode> nodeVec;
};