0 Preview

为啥要再单开一篇写双链表？

因为单链表写的太多了，翻着麻烦。所以这篇会很短很短。

《夜间破防ctfer借酒消愁》
haojiumeijian

1 双链表

在线性表的链式存储结构中，每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域

1.1双链表的优点

🔑从任一结点出发可以快速找到其前驱结点和后继结点；
🔑从任一结点出发可以访问其他结点。

1.2 结点类型DLinkNode声明

C
typedef struct DNode       	//双链表结点类型
{  ElemType data;
   struct DNode *prior;    	//指向前驱结点
   struct DNode *next;     	//指向后继结点
} DLinkNode;

1.3 双链表插入结点操作

操作语句：
📖 s->next = p->next
📖 p->next->prior = s
📖 s->prior = p
📖 p->next = s

2 双链表算法

2.1 建立双链表

整体建立双链表也有两种方法：头插法和尾插法。与单链表的建表算法相似，主要是插入和删除的不同。

头插法建立双链表：由含有n个元素的数组a创建带头结点的双链表L。

C
void CreateListF(DLinkNode *&L，ElemType a[]，int n)
{  DLinkNode *s; int i;
   L=(DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点
   L->prior=L->next=NULL;	//前后指针域置为NULL
   for (i=0;i<n;i++)		//循环建立数据结点
   {	s=(DLinkNode *)malloc(sizeof(DLinkNode));
	s->data=a[i];		//创建数据结点s
	s->next=L->next;		//将s插入到头结点之后
	if (L->next!=NULL)   	//若L存在数据结点，修改前驱指针
  	    L->next->prior=s;
       L->next=s;
       s->prior=L;
   }
}

尾插法：

CODE
void CreateListR(DLinkNode *&L，ElemType a[]，int n)
{  DLinkNode *s，*r;
   int i;
   L=(DLinkNode *)malloc(sizeof(DLinkNode));    //创建头结点
   r=L;					//r始终指向尾结点，开始时指向头结点
   for (i=0;i<n;i++)			//循环建立数据结点
   {  s=(DLinkNode *)malloc(sizeof(DLinkNode));
      s->data=a[i];			//创建数据结点s
      r->next=s;s->prir=r;		//将s插入r之后
      r=s;				//r指向尾结点
   }
   r->next=NULL;				//尾结点next域置为NULL
}

其余的都大差不差，看看上一篇的单链表就行。

2.2 插入

C
bool ListInsert(DLinkNode *&L，int i，ElemType e)
{  int j=0;
   DLinkNode *p=L，*s;	      	//p指向头结点，j设置为0
   while (j<i-1 && p!=NULL)	//查找第i-1个结点
   {  j++;
      p=p->next;
   }      
//以上部分完成操作：查找第i-1个结点p
   if (p==NULL)			//未找到第i-1个结点，返回false
     return false;
  else				//找到第i-1个结点p，在其后插入新结点s
  {
	s=(DLinkNode *)malloc(sizeof(DLinkNode));
	s->data=e;		//创建新结点s
	s->next=p->next;		//在p之后插入s结点
	if (p->next!=NULL)	//若存在后继结点，修改其前驱指针
   	     p->next->prior=s;
	s->prior=p;
	p->next=s;
	return true;
   }
}

另外解法：在双链表中，可以查找第i个结点，并在它前面插入一个结点。

2.3 双链表的删除算法：

C
bool ListDelete(DLinkNode *&L，int i，ElemType &e)
{  int j=0; DLinkNode *p=L，*q; 		//p指向头结点，j设置为0
   while (j<i-1 && p!=NULL)	  	//查找第i-1个结点
   {  j++;
      p=p->next;
   }

   if (p==NULL)			//未找到第i-1个结点
	return false;
   else			   	//找到第i-1个结点p
   {	q=p->next;		//q指向第i个结点
	if (q==NULL)	   	//当不存在第i个结点时返回false
	   return false;
	e=q->data;
	p->next=q->next;		//从双单链表中删除q结点
	if (q->next!=NULL)    	//若q结点存在后继结点
            q->next->prior=p;	//修改q结点后继结点的前驱指针
	free(q);		   	//释放q结点
	return true;
   }
}