双向链表的创建、插入、删除

C语言实现

/*定义双向链表节点类型*/
typedef struct ListNode{
  int val;
  ListNode *prior;
  ListNode *next;
}ListNode;

/*尾插法创建双向链表——形成与输入相同的序列*/
ListNode* initDulList(){
  //创建头节点、对头节点初始化
  ListNode* head=(ListNode*)malloc(siezof(ListNode));
  head->val=0;
  head->prior=NULL;
  head->next=NULL;
  
  ListNode* p=head;//创建操作指针
  
  for(int i=1;i<5;i++){
    //创建节点并初始化
    ListNode* node=(ListNode*)malloc(siezof(ListNode));
    node->val=i;
    node->prior=NULL;
    node->next=NULL;
    
    //将节点连接到尾部并步进操作指针
    p->next=node;
    p->next->prior=p;
    p=p->next;
  }
  
  return head;
}

/*双向链表中间插入元素和头部插入元素，根据要插入的位置来找到节点*/
ListNode* insertElem(ListNode* head,int elem int location){
  ListNode* dummyHead=(ListNode*)malloc(siezof(ListNode));
  dummyHead->next=head;
  dummyHead->prior=NULL;
  head->prior=dumyHead;
  
  ListNode* p=dummyHead;//为了方便在头节点之前插入
  
  //创建节点封装要插入的数据
  ListNode* insert=(ListNode*)malloc(siezof(ListNode));
  insert->val=elem;
  insert->prior=NULL;
  insert->next=NULL;
  
  for(int i=0;i<location-1;i++){//根据下标位置来插入要用for
    //如果插入尾部
    if(p->next==NULL){
      p->next=last;
      last->prior=p;
      
      return head;
    }
    
    p=p->next;
  }
  
  //如果是插入中间或者头
  ListNode *temp=p->next;
  
  //以节点间隙为单位调整指针
  p->next=insert;
  insert->prior=p;
  insert->next=temp;
  temp->prior=insert;
  
  return head;
}

/*双向链表删除元素，根据要删除节点的值来找到节点*/
ListNode *delElem(ListNode *head,int target){
  ListNode* dummyHead=(ListNode*)malloc(siezof(ListNode));
  dummyHead->next=head;
  dummyHead->prior=NULL;
  head->prior=dumyHead;
  
  ListNode* p=dummyhead;//为了方便删除头节点
  
  while(p!=NULL){//不需要像单链表一样使用前驱节点
    if(p->val==target){
      ListNode* delTemp=p;
        
      p->prior->next=p->next;//不需要像单链表一样创建临时指针
      p->next->prior=p->prior;
      
      free(delTemp);//好习惯
    }
    p=p->next;
  }
  
  return head;
}

/*双向链表查找元素*/
ListNode* findElem(ListNode* head,int target){
  ListNode* p=head;
  
  while(p!=NULL){
    if(p->val==target){
      return p;
    }
    p=p->next;
  }
  
  return NULL;//???没找到是否返回NULL？
}

C++实现

/*双向链表节点类型定义*/
struct ListNode {
  int val;
  ListNode *prior;
  ListNode *next;
  ListNode(int x) : val(x), prior(NULL),next(NULL) {}//将属性初始化
};

class Solution {
public:
  ListNode* deleteNode(ListNode* head, int val) {
    ListNode* dummyNode=new ListNode(-1);
    dummyNode->prior=NULL;
    dummyNode->next=head;
    head->prior=dummyNode;

    ListNode* p=dummyNode;

    while(p!=NULL){
      if(p->val==val){
        ListNode* delTemp=p;//删除用
        p->prior->next=p->next;
        p->next->prior=p->prior;
        delete temp;
      }
      p=p->next;//不能丢
    }

    return dummyNode->next;
  }
};

将一个新的节点链接到双向链表尾部，先通过位于尾节点的操作指针p将next指针指向新建节点，再通过操作指针p将访问后继节点的prior指针指向自身，就把两个节点之间的指针设置好了，至于新节点的next，在初始化的时候就置空了。
在双向链表中间插入新建的节点时，由于p、temp、insert三个指针均不用移动且明确，故直接用这三个指针依次对两个间隙的4个指针进行赋值即可。
双向链表在删除节点时，完全不需要用到前驱节点，而且操作指针时只需要两次操作，建立前驱节点与后继节点之间的联系。
推荐在删除节点之后，通过节点指针将内存释放。