双向链表的基本操作

本文主要总结双向链表的基本操作，包括双向链表的创建，插入，按位置删除，按数据域删除，遍历，逆序等操作，细节见代码及注释。

#include <stdio.h>
#include <stdlib.h> 

typedef struct Node {
	int data;
	struct Node * prior;
	struct Node * next;
}NODE, *PNODE;

//在指定位置插入节点
/*
注意点:
插入不在最后要改变插如节点的后一个节点的前驱指针 
*/ 
bool insertNode(PNODE L, int i, int x) {
	PNODE p = L;
	while(p && --i) //让p指向第i-1个结点 
		p = p->next;
	if(!p) return false;	//链表不够长,插入失败 
	PNODE s = (NODE*)malloc(sizeof(NODE));
	s->data = x;
	s->next = p->next;
	if(p->next) //一定要记得判断插入不在最后才修改后继结点的前驱指针 
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

//删除指定数值的元素
/*
注意点：
1.删除位置不确定，用双指针遍历 
2.判断链表长度是否足够，只需要判断p指向的节点(需要删除的节点)是否为空;
3.记得判断删除节点的后一个节点是否存在，若存在，改变其前驱。 
*/
bool deletNode1(PNODE L, int x) {
	PNODE p = L->next, q = L;
	while(p && p->data != x) {
		q = p;
		p = p->next;
	}
	if(!p) return false; //链表长度不够，删除失败 
	q->next = p->next;	//从双向链表中删除值为x的节点 
	if(q->next)	//这里也可以是p->next 
		q->next->prior = q;
	free(p);
	return true;
}

//删除指定位置上的元素并保存删除元素的值 
/*
注意点：
1.判断链表长度是否足够，包括：p指向是否为空(删除节点的前一个节点) 和 p指向的后一个节点(需要删除的节点)是否为空;
2.记得预留删除节点的地址即p->next; 
2.记得判断删除节点的后一个节点是否存在，若存在，改变其前驱。 
*/ 
bool deletNode2(PNODE L, int i, int &e) {
	PNODE p = L, q;
	while(p && --i) //让p指向第i-1个结点 
		p = p->next;
	if(!p || !p->next) return false; //链表长度不够，删除失败 
	q = p->next;
	e = q->data;
	p->next = q->next; //从双向链表中删除第i个结点 
	if(p->next) //注意这里的p->next与前面预留的q含义已经改变，写q->next也行 
		p->next->prior = p;
	free(q); 
	return true;
}

//头插法创建链表
/*
注意点：
1.s节点(新插入节点)的右指针域始填充头结点的右指针域; 
2.一定要判断新插入节点的后一个节点是否存在，若存在，改变其前驱 。 
*/ 
void creatList(PNODE &L, int *a, int n) {
	L = (NODE*)malloc(sizeof(NODE));
	L->next = L->prior = NULL;
	for(int i=0;i<n;i++) {
		PNODE s = (NODE*)malloc(sizeof(NODE));
		s->data = a[i];
		s->next = L->next;
		if(s->next) //特判不是空表时插入位置后一个元素前驱指针处理方式，这里写L->next也行 
			s->next->prior = s;
		s->prior = L;
		L->next = s;
	}
} 

//尾插法创建链表
//和单向链表的操作基本一样，记得加上前驱指针就好 
void creatList2(PNODE &L, int *a, int n) {
	L = (NODE*)malloc(sizeof(NODE));
	L->next = L->prior = NULL;
	PNODE p = L;	 
	for(int i=0;i<n;i++) {
		PNODE s = (NODE*)malloc(sizeof(NODE));
		s->data = a[i]; 
		s->next = p->next;
		s->prior = p;
		p->next = s;
		p = p->next;
	}
}

//输出链表 
void displayNode1(PNODE L) {
	if(L == NULL || L->next == NULL)
		return;
	PNODE p = L->next;
	while(p) {
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

//用前驱指针逆序输出链表 
void displayNode2(PNODE L) {
	if(L == NULL || L->next == NULL)
		return;
	PNODE p = L->next;
	while(p->next) 
		p = p->next;
	printf("%d ",p->data);
	p = p->prior;
	while(p != L ) {
		printf("%d ",p->data);
		p = p->prior;
	} 
	printf("\n");	
}

//双向链表的逆序 
void reverse(PNODE L) {
	PNODE p = L->next, q = NULL, r; //注意这里q指针的处理方式 
	while(p) {
		r = p->next; //预留p指向节点的指针域
		p->prior = p->next;
		p->next = q; //改变p指向节点的指针域指向前一个节点
		q = p; //p,q指针后移 
		p = r;
	}
	L->next = q;//头结点归位 
    q->prior = L; //不要忘记最后一个节点的前驱指针指向头结点 
} 

int main() {
	int n = 5, m = 7;
	int a[n] = {9,3,0,6,1};
	int b[m] = {5,1,3,6,8,7,4};
	PNODE L;
	creatList2(L,a,n);
	displayNode1(L);
	int e;
	if(deletNode2(L,5,e)) {
		printf("删除的元素是:%d\n",e);
	} else {
		printf("该元素不存在\n");
	}
	displayNode1(L);
	return 0;
}

双向链表最重要的就是前驱指针的处理，因为存在前驱指针 所以在插入，删除等操作时，一定要记得判断后继结点是否存在，有的话才对后继节点的前驱指针进行修改。