节点结构：

 

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 ;
}