双链表插入 删除详解

节点结构：

 

struct both_node
{
    int key;
    struct both_node *prev;
    struct both_node *next;
    both_node(int k)
        :key(k),prev(NULL),next(NULL)
    {}
};

 

不带头节点的双链表实现插入 删除，

 

    双链表  //插入  void insert_both(both_node *&head,int key)  {       if(head==NULL)      {           head= new both_node(key);      } else      {           both_node *tmp= new both_node(key);            if(head->next==NULL)//当插入时链表中只有一个节点的时候           {               head->next=tmp;               tmp->prev=head;           } else //链表中已经至少有两个节点           {               tmp->next=head->next;               head->next->prev=tmp;                 head->next=tmp;               tmp->prev=head;           }      }  }  //删除  bool remove_both(both_node *&head,int key)  {       if(head==NULL)            return false ;       if(head->key==key)//如果是头节点      {            if(head->next==NULL)//如果只有一个节点           {                delete head;               head=NULL;           } else//链表后面还有节点           {               both_node *tmp=head;               head=head->next;               head->prev=NULL;                delete tmp;               tmp=NULL;           }            return true ;      }      both_node *cur=head->next;       while(cur !=NULL && cur->key !=key)           cur=cur->next;       if(cur==NULL)//没有找到            return false ;       if(cur->next !=NULL)//删除的不是尾节点      {           cur->prev->next=cur->next;           cur->next->prev=cur->prev;      } else //删除的是尾节点      {           cur->prev->next=NULL;      }             delete cur;      cur=NULL;       return true ;  }
双链表
//插入
void insert_both(both_node *&head,int key)
{
     if(head==NULL)
    {
         head= new both_node(key);
    } else
    {
         both_node *tmp= new both_node(key);
          if(head->next==NULL)//当插入时链表中只有一个节点的时候
         {
             head->next=tmp;
             tmp->prev=head;
         } else //链表中已经至少有两个节点
         {
             tmp->next=head->next;
             head->next->prev=tmp;

             head->next=tmp;
             tmp->prev=head;
         }
    }
}
//删除
bool remove_both(both_node *&head,int key)
{
     if(head==NULL)
          return false ;
     if(head->key==key)//如果是头节点
    {
          if(head->next==NULL)//如果只有一个节点
         {
              delete head;
             head=NULL;
         } else//链表后面还有节点
         {
             both_node *tmp=head;
             head=head->next;
             head->prev=NULL;
              delete tmp;
             tmp=NULL;
         }
          return true ;
    }
    both_node *cur=head->next;
     while(cur !=NULL && cur->key !=key)
         cur=cur->next;
     if(cur==NULL)//没有找到
          return false ;
     if(cur->next !=NULL)//删除的不是尾节点
    {
         cur->prev->next=cur->next;
         cur->next->prev=cur->prev;
    } else //删除的是尾节点
    {
         cur->prev->next=NULL;
    }

     delete cur;
    cur=NULL;
     return true ;
}