- #ifndef LINKEDLIST
- #define LINKEDLIST
- struct node{
- friend class linkedlist;
- private:
- double data;
- node* next;
- node* prev;
- node(double d,node* n=0,node* p=0);
- };
- class linkedlist
- {
- node *head,*tail;
- int size;
- class out_of_index{} index_error;
- public:
- linkedlist();
- ~linkedlist();
- node* get_head();
- node* get_tail();
- int get_size();
- bool empty();
- double operator[](int);
- //插入位置为index的元素之后,插入首位则index为-1
- void insert(double d,int index);
- //在尾部插入
- void push_back(double);
- bool contains(double);
- //删除位于index处的元素
- void remove(int index);
- //返回值表示表中被删除的元素的个数
- int remove(double d);
- };
- node::node(double d,node* n,node* p){
- data=d;
- next=n;
- prev=p;
- }
- linkedlist::linkedlist():head(0),tail(0),size(0){}
- linkedlist::~linkedlist(){
- if(!empty()){
- node* tmp=head;
- while(tmp){
- delete tmp;
- tmp=tmp->next;
- }
- }
- }
- inline node* linkedlist::get_head(){
- return head;
- }
- inline node* linkedlist::get_tail(){
- return tail;
- }
- inline int linkedlist::get_size(){
- return size;
- }
- inline bool linkedlist::empty(){
- return size==0;
- }
- double linkedlist::operator[](int index){
- if(index<0 || index>=size)
- throw index_error;
- if(index<size/2){
- node* tmp=head;
- for(int i=0;i<index;i++){
- tmp=tmp->next;
- }
- return tmp->data;
- }else{
- node* tmp=tail;
- for(int i=size-1;i>index;i--){
- tmp=tmp->prev;
- }
- return tmp->data;
- }
- }
- void linkedlist::insert(double d,int index){
- if(index<-1 || index>=size)
- throw index_error;
- if(index==-1){
- node* newnode=new node(d);
- if(size==0){
- head=newnode;
- tail=newnode;
- size++;
- }else{
- head->prev=newnode;
- newnode->next=head;
- head=newnode;
- size++;
- }
- return;
- }
- if(index==size-1){
- node* newnode=new node(d);
- tail->next=newnode;
- newnode->prev=tail;
- tail=newnode;
- size++;
- return;
- }
- if(index<size/2){
- node* tmp=head;
- for(int i=0;i<index;i++){
- tmp=tmp->next;
- }
- node* newnode=new node(d,tmp->next,tmp);
- tmp->next->prev=newnode;
- tmp->next=newnode;
- size++;
- }else{
- node* tmp=tail;
- for(int i=size-1;i>index+1;i--){
- tmp=tmp->prev;
- }
- node* newnode=new node(d,tmp,tmp->prev);
- tmp->prev->next=newnode;
- tmp->prev=newnode;
- size++;
- }
- }
- void linkedlist::push_back(double d){
- insert(d,size-1);
- }
- bool linkedlist::contains(double d){
- node* tmp=head;
- while(tmp){
- if(tmp->data==d)
- return true;
- tmp=tmp->next;
- }
- return false;
- }
- void linkedlist::remove(int index){
- if(size==0 || index<0 || index>=size)
- throw index_error;
- if(index==0){
- if(size==1){
- delete head;
- head=0;
- tail=0;
- size--;
- }else{
- head=head->next;
- delete head->prev;
- head->prev=0;
- size--;
- }
- return;
- }
- if(index==size-1){
- tail=tail->prev;
- delete tail->next;
- tail->next=0;
- size--;
- return;
- }
- if(index<size/2){
- node* tmp=head;
- for(int i=0;i<index;i++){
- tmp=tmp->next;
- }
- tmp->prev->next=tmp->next;
- tmp->next->prev=tmp->prev;
- delete tmp;
- size--;
- }else{
- node* tmp=tail;
- for(int i=size-1;i>index;i--){
- tmp=tmp->prev;
- }
- tmp->prev->next=tmp->next;
- tmp->next->prev=tmp->prev;
- delete tmp;
- size--;
- }
- }
- int linkedlist::remove(double d){
- if(size==0){
- return 0;
- }
- int num=0;
- node* tmp=head;
- while(tmp){
- if(tmp->data==d){
- if(tmp==head){
- if(size==1){
- head=0;
- tail=0;
- delete tmp;
- size--;
- num++;
- break;
- }else{
- head=head->next;
- head->prev=0;
- delete tmp;
- tmp=head;
- size--;
- num++;
- }
- }else if(tmp==tail){
- tail=tail->prev;
- tail->next=0;
- delete tmp;
- tmp=tail;
- num++;
- size--;
- }else{
- tmp->prev->next=tmp->next;
- tmp->next->prev=tmp->prev;
- node* anothertmp=tmp;
- tmp=tmp->next;
- delete anothertmp;
- size--;
- num++;
- }
- }else{
- tmp=tmp->next;
- }
- }
- return num;
- }
- #endif
- //该片段来自于http://www.codesnippet.cn/detail/141120137159.html
来源: http://www.codesnippet.cn/detail/141120137159.html