C语言双向链表的原理与使用操作

一.引入

我们在单链表中，有了next指针，这个指针是用来指向下一个节点的，如果我们需要查找下一个结点的时间复杂度为o(1),如果我们需要查找上一个节点的时候，那么时间复杂度就变为o(n)了，需要从头进行遍历一遍；这时我们就会想：如果可以向前查找就方便了许多，因此我们引入了双向链表。

二.双向链表的定义

双向链表：是在单链表的每个节点中，再设置一个指向前驱结点的指针域。

顾名思义就是链表由单向的变成了双向的，每一个节点由原来的一个指针变为两个指针，一个用来指向直接后继，另一个用来指向直接前驱。

三.双向链表与单链表对比

通过对比可以更好认识二者的联系与区别。

3.1图示对比

单链表：

双向链表：

3.2代码对比

单链表代码如下：

typedef struct Node{ //定义单链表结点类型
	int data; //数据域，可以是别的各种数据类型
	struct Node *next; //指针域
}LNode, *LinkList;

双向链表代码如下：

typedef struct DulNode{
	int data;			// 	数据域
	struct DulNode *prior;		//  向前的指针
	struct DulNode *next;		//  向后的指针
}DulNode,*DuLinkList;

四.双向链表的操作

双向链表是单链表中扩展出来的结构，所以有很多的操作是和单链表相同的，如求长度，查找元素，获取一个元素，这里我们对双向链表进行创建，插入，删除，销毁的一系列操作。

4.1双向链表的创建

双向链表在初始化时，要给首尾两个节点分配内存空间。成功分配后，需要将首节点的prior指针和尾节点的next指针都指向NULL，这是十分关键的一步，因为这是之后用来判断空表的条件。并且当链表为空时，要将首节点的next指向尾节点，尾节点的prior指向首节点。

pElem CreatList(){
	pElem head = (pElem)malloc( sizeof(eElem) );
	assert( head != NULL );		//进行断言
	head->next = head->prior = NULL；//初始化链表指针置空
	return head;
}

4.2双向链表的插入

双向链表的插入其实并不复杂，只是在原有单链表的基础上多了连接一个向前的指针而已。但是需要注意的是操作的顺序很重要，不可以写反了。

以下面这个为例，假设存储元素e的结点为s，要实现将结点s插入到结点p和p->next之间

核心代码就只有以下四行：

s->prior=p; //把p赋值给s的前驱
s->next=p->next;// 把p->next赋值给s的后继
p->next->prior=s;// 把s赋值给p->next的前驱
p->next=s; //把s赋值给p的后继

切记顺序不可以记错 在写代码的时候可以将操作步骤画出来，理清实施步骤的顺序。

4.3双向链表的删除

如果将插入操作的原理理解后，那么删除就很好理解了。

删除只需要两个步骤：

核心代码只有三行：

p->prior->next=p->next; //把p->next赋值给p->prior的后继
p->next->prior=p->prior;//把p->prior赋值给p->next的前驱
free(p); //释放结点

4.4双向链表的销毁

销毁一个双向链表的操作同单链表的相似。指针不断向后运动，每运动一个结点，释放上一个结点。

代码如下：

void DestroyList( pElem head ){
	pElem tmp;
	while( head->next != NULL ){
		tmp = head;		//  指针不断后移
		head = head->next;
		free(tmp);
	}
	free(head);
}

五.总结

双向链表相比于单链表来说，是更复杂一些的，毕竟多了一个prior指针，对于插入和删除需要特别注意这两种操作的核心思想以及操作顺序。另外双向链表，带来了方便，可以有效提高算法的时间性能。

六.全部代码

这里引用一位大佬写的代码，将头插法和尾插法创建表都写了，写的很细节，很清楚大家可以参考一下。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int status;
typedef int elemtype;
typedef struct node{
  elemtype data;
  struct node * next;
  struct node * prior;
}node;
typedef struct node* dlinklist;
status visit(elemtype c){
  printf("%d ",c);
}
/*双向链表初始化*/
status initdlinklist(dlinklist * head,dlinklist * tail){
  (*head)=(dlinklist)malloc(sizeof(node));
  (*tail)=(dlinklist)malloc(sizeof(node));
  if(!(*head)||!(*tail))
      return ERROR;
  /*这一步很关键*/ 
  (*head)->prior=NULL;
  (*tail)->next=NULL;
  /*链表为空时让头指向尾*/
  (*head)->next=(*tail);
  (*tail)->prior=(*head);
}
/*判定是否为空*/
status emptylinklist(dlinklist head,dlinklist tail){
  if(head->next==tail)
     return TRUE;
  else
     return FALSE;
} 
/*尾插法创建链表*/ 
status createdlinklisttail(dlinklist head,dlinklist tail,elemtype data){
  dlinklist pmove=tail,pinsert;
  pinsert=(dlinklist)malloc(sizeof(node));
  if(!pinsert)
       return ERROR;
  pinsert->data=data;
  pinsert->next=NULL;
  pinsert->prior=NULL;
  tail->prior->next=pinsert;
  pinsert->prior=tail->prior;
  pinsert->next=tail;
  tail->prior=pinsert;
} 
/*头插法创建链表*/ 
status createdlinklisthead(dlinklist head,dlinklist tail,elemtype data){
  dlinklist pmove=head,qmove=tail,pinsert;
  pinsert=(dlinklist)malloc(sizeof(node));
  if(!pinsert)
      return ERROR;
  else{
      pinsert->data=data;
      pinsert->prior=pmove;
      pinsert->next=pmove->next;
      pmove->next->prior=pinsert;
      pmove->next=pinsert;
  }
}
/*正序打印链表*/ 
status traverselist(dlinklist head,dlinklist tail){
  /*dlinklist pmove=head->next;
  while(pmove!=tail){
      printf("%d ",pmove->data);
      pmove=pmove->next;
  }
  printf("\n");
  return OK;*/
  dlinklist pmove=head->next;
  while(pmove!=tail){
      visit(pmove->data);
      pmove=pmove->next;
  }
  printf("\n");
}
/*返回第一个值为data的元素的位序*/
status locateelem(dlinklist head,dlinklist tail,elemtype data){
  dlinklist pmove=head->next;
  int pos=1;
  while(pmove&&pmove->data!=data){
      pmove=pmove->next;
      pos++;
  }
  return pos;
}
/*返回表长*/
status listlength(dlinklist head,dlinklist tail){
  dlinklist pmove=head->next;
  int length=0;
  while(pmove!=tail){
      pmove=pmove->next;
      length++;
  }
  return length;
}
/*逆序打印链表*/
status inverse(dlinklist head,dlinklist tail){
  dlinklist pmove=tail->prior;
  while(pmove!=head){
      visit(pmove->data);
      pmove=pmove->prior;
  }
  printf("\n");
}
/*删除链表中第pos个位置的元素，并用data返回*/
status deleteelem(dlinklist head,dlinklist tail,int pos,elemtype *data){
  int i=1;
  dlinklist pmove=head->next;
  while(pmove&&i<pos){
      pmove=pmove->next;
      i++;
  }
  if(!pmove||i>pos){
      printf("输入数据非法\n");
      return ERROR;
  }
  else{
      *data=pmove->data;
      pmove->next->prior=pmove->prior;
      pmove->prior->next=pmove->next;
      free(pmove);
  }
}
/*在链表尾插入元素*/
status inserttail(dlinklist head,dlinklist tail,elemtype data){
  dlinklist pinsert;
  pinsert=(dlinklist)malloc(sizeof(node));
  pinsert->data=data;
  pinsert->next=NULL;
  pinsert->prior=NULL;
  tail->prior->next=pinsert;
  pinsert->prior=tail->prior;
  pinsert->next=tail;
  tail->prior=pinsert;
  return OK;
} 
int main(void){
  dlinklist head,tail;
  int i=0;
  elemtype data=0;
  initdlinklist(&head,&tail);
  if(emptylinklist(head,tail))
      printf("链表为空\n");
  else
      printf("链表不为空\n");
  printf("头插法创建链表\n"); 
  for(i=0;i<10;i++){
      createdlinklisthead(head,tail,i);
  }
  traverselist(head,tail);
  for(i=0;i<10;i++){
      printf("表中值为%d的元素的位置为",i); 
      printf("%d位\n",locateelem(head,tail,i));
  }
  printf("表长为%d\n",listlength(head,tail));
  printf("逆序打印链表");
  inverse(head,tail);
  for(i=0;i<10;i++){
      deleteelem(head,tail,1,&data);
      printf("被删除的元素为%d\n",data);
  }
  traverselist(head,tail);
  if(emptylinklist(head,tail))
      printf("链表为空\n");
  else
      printf("链表不为空\n");
      printf("尾插法创建链表\n");
  for(i=0;i<10;i++){
      //inserttail(head,tail,i);
      createdlinklisttail(head,tail,i);
  }
  traverselist(head,tail);
  printf("逆序打印链表");
  inverse(head,tail);
}

关于C语言双向链表的原理与使用操作的文章就介绍至此，更多相关C语言双向链表内容请搜索编程宝库以前的文章，希望以后支持编程宝库！

 staticstatic修饰全局变量static修饰的全局变量只能在当前声明文件内使用，不能够在其他文件中使用。举例：static int a=0; //static修饰后变量a仅在本文件中可见 ...