#include <iostream>
using namespace std;
struct DLinkNode{
int data;
DLinkNode* prior;
DLinkNode* next;
};
void Initalize(DLinkNode*& L) { //创建双向链表
L = new DLinkNode;
L->prior = 0;
L->next = 0;
}
void Push_Back(DLinkNode*& L, int x) { //头部插入
DLinkNode* p = L, * A = new DLinkNode;
A->data = x;
while (p->next != 0) {
p = p->next;
}
p->next = A;
A->prior = p;
A->next = 0;
}
void Push_Head(DLinkNode*& L, int x) { //尾部插入
DLinkNode* A = new DLinkNode;
A->data = x;
A->next = L->next;
L->next->prior = A;
L->next = A;
A->prior = L;
}
int Length(DLinkNode* L) { //计算单链表的长度
DLinkNode* p;
p = L->next;
int len = 0;
while (p) {
len++;
p = p->next;
}
return len;
}
DLinkNode* Find(DLinkNode*& L, int i) { //找到第i个元素的地址
if (i<0 || i>Length(L)) return 0;
DLinkNode* p;
p = L;
int j = 0;
while (j < i) {
p = p->next;
j++;
}
return p;
}
void Insert(DLinkNode*& L, int i, int x) { //在第i个位置插入
if (i<0 || i>Length(L) + 1) return;
if (i == Length(L) + 1)
Push_Back(L, x);
else {
DLinkNode* p = Find(L, i - 1);
Push_Head(p, x);
}
}
void Pop_Back(DLinkNode*& L) { //尾部删除
DLinkNode* p;
p = L;
while (p->next != 0) {
p = p->next;
}
p->prior->next = 0;
delete p;
}
void Pop_Head(DLinkNode*& L) { //头部删除
DLinkNode* p;
p = L;
p->next->prior = L;
L = L->next;
delete p;
}
void Delete(DLinkNode*&L,int i) { //删除第i个元素
if (i<0 || i>Length(L)) return;
if (i == 0)
Pop_Head(L);
if (i == Length(L))
Pop_Back(L);
else {
DLinkNode* p = Find(L, i);
p->prior->next = p->next;
p->next->prior = p->prior;
delete p;
}
}
void Print(DLinkNode* L) { //打印链表
DLinkNode* p;
p = L->next;
while (p) {
cout << p->data;
p = p->next;
if (p)
cout << ' ';
}
cout << endl;
}
int main() {
DLinkNode* L;
Initalize(L);
Push_Back(L, 1);
Push_Back(L, 2);
Push_Back(L, 3);
Push_Back(L, 4);
Push_Head(L, 5);
Push_Head(L, 6);
Push_Head(L, 7);
Push_Head(L, 8);
Print(L);
Delete(L, 3);
Print(L);
Pop_Head(L);
Print(L);
return 0;
}
