代码:
typedef struct MyLinkList {
int val;
struct MyLinkList *next;
struct MyLinkList *pre;
MyLinkList(): val(-1),pre(NULL),next(NULL){}
MyLinkList(int t): val(t),pre(NULL),next(NULL){}
MyLinkList(int t,MyLinkList *p,MyLinkList *s): val(t),pre(p),next(s){}
}MyLinkedNode;
class MyLinkedList {
private:
MyLinkedNode *head;
MyLinkedNode *tail;
int size;
public:
MyLinkedList() {
head=new MyLinkList(-1);
tail=new MyLinkList(-1);
size=0;
head->next=tail;
tail->pre=head;
}
int get(int index) {
if(index<0||index>=size) return -1;
MyLinkedNode *p=head;
while(index>=0){
--index;
p=p->next;
}
return p->val;
}
void addAtHead(int val) {
MyLinkedNode *newNode=new MyLinkList(val,head,head->next);
head->next->pre=newNode;
head->next=newNode;
++size;
}
void addAtTail(int val) {
MyLinkedNode *newNode=new MyLinkList(val,tail->pre,tail);
tail->pre->next=newNode;
tail->pre=newNode;
++size;
}
void addAtIndex(int index, int val) {
if(index==size){
addAtTail(val); return;
}
else if(index>size)
return;
else if(index<0){
addAtHead(val);
return;
}
MyLinkedNode *p=head;
while(index>=0){
--index;
p=p->next;
}
MyLinkedNode *newNode=new MyLinkList(val,p->pre,p);
p->pre->next=newNode;
p->pre=newNode;
}
void deleteAtIndex(int index) {
if(index<0||index>=size) return;
MyLinkedNode *p=head;
while(index>=0){
--index;
p=p->next;
}
p->pre->next=p->next;
p->next->pre=p->pre;
delete(p);
--size;
}
};