链表可是个好东西， 那么我今天便拿出——自制链表！！！
它有着 精美丑陋的外观
class list
简洁的语言
public:
protected:
int len;
struct node {
T v;
node *pre, *nxt;
} *head, *tail;
比stl更丰富 6！
void insert(int x, const T &v) {
len++;
node *q = new node(), *p = head;
for (int i = 1; i <= x; i++) p = p->nxt;
q->nxt = p->nxt; q->nxt->pre = q;
p->nxt = q; q->v = v; q->pre = p;
}
可谓是男人的加油站，女人的美容院我在说什么
好！
那么我便拿出他——自制链表
template<typename T>
class List {
public:
protected://使外界不能访问
int len;
struct node {
T v;
node *pre, *nxt;
} *head, *tail;
public:
class iterator {
friend List;//能使用node
public:
protected://修复BUG 6.3
node *q;
public:
T operator * (){
return q->v;
}
bool operator != (const iterator &x) {//修复BUG 6.3
if (this->q== x.q) {
return 0;
}
return 1;
}
iterator operator = (const iterator &x) {
q = x.q;
return x;
}
iterator operator ++ () {
q = q->nxt;
iterator x;
x.q = q;
return x;
}
iterator operator ++ (int) {
q = q->nxt;
iterator x;
x.q = q;
return x;
}
};
public:
friend iterator;//能使用q
iterator begin() {
iterator x;
x.q = head->nxt;
return x;
}
iterator end() {
iterator x;
x.q = tail;
return x;
}
List() {//7.21 添加
len = 0;
head = new node();
tail = new node();
head->nxt = tail;
tail->pre = head;
}
void insert(int x, const T &v) {
len++;
node *q = new node(), *p = head;
for (int i = 1; i <= x; i++) p = p->nxt;
q->nxt = p->nxt; q->nxt->pre = q;
p->nxt = q; q->v = v; q->pre = p;
}
int size() {
return len;
}
void print(int l = 1, int le = -1) {//添加新功能 6.3,可不传参
iterator it;
it.q = head;
it++;//修复BUG 7.21
for (int i = 1; i <= l; i++) it++;//利用迭代器输出
if (le != -1) {
for (int i = 1; i <= le; i++) {
cout << *it << " ";
it++;
}
cout << "\n";
}
else {
for (int i = 1; i <= len && it.q->nxt != tail; i++) {
cout << *it << " ";
it++;
}
cout << *it;
cout << "\n";
}
}
void erase(int x) {//O(n)
node *p = head;
len--;
for (int i = 1; i <= x; i++) p = p->nxt;
p->pre->nxt = p->nxt;
p->nxt->pre = p->pre;
delete p;
}
void clear() {
len = 0;
node *h = head;
while (h != tail) {
h = h->nxt;
delete head->pre;
};
}
bool empty() {
return len == 0;
}
void push_back(const T &v) {
len++;
node *p = new node();
tail->pre->nxt = p;
p->pre = tail->pre;
p->v = v;
tail->pre = p;
p->nxt = tail;
}
void push_front(const T &v) {
len++;
node *p = new node();
head->nxt->pre = p;
p->nxt = head->nxt;
p->v = v;
head->nxt = p;
p->pre = head;
}
void pop_front() {
len--;
node *p = head->nxt;
head->nxt = p->nxt;
p->nxt->pre = head;
delete p;
}
void pop_back() {
len--;
node *p = tail->pre;
p->pre->nxt = tail;
tail->pre = p->nxt;
delete p;
}
List operator = (List &l) {//添加等号6.3
clear();
iterator it;
for (it = l.begin(); it != l.end(); it++) {
push_back(*it);
}
return l;
}
};
食用方法：
List<int> l;
l.push_back(1);
l.pop_back();
l.insert(0, 4);//在第0后，添加4。
l.erase(1);//删除第 1个
l.push_back(1);
l.push_back(2);
List<int>::iterator it = l.begin();
++it;
l.print(1, 1);//输出