双链表概述

双链表也是线性表的一种，它的全称是：线性双向链接表，它有以下特点：
在每个节点中除包含有数值域外,设置有两个指针域，分别用以指向其前驱节点和后继节点。
既可以依次向后访问每一个节点，也可以依次向前访问每一个节点。

这里写图片描述

代码实现

dlinklist.h如下：

c

#include <stdio.h>
#include <malloc.h>


typedef int ElemType;
typedef struct Node{
	ElemType data;
	struct Node * prior;
	struct Node * next;
}DLinkList;

DLinkList.cpp如下：

c

#include "dlinklist.h"
#include <stddef.h>
void headInit(DLinkList * &dll,ElemType arr[], int n);
void printDoubleLinkList(DLinkList * dll);
void tailInit(DLinkList * &dll,ElemType arr[], int n);
bool insertElement(DLinkList *&dll, int pos, ElemType e);
bool deleteElement(DLinkList *&dll, int pos, ElemType &e);
int main() {
	DLinkList * dll;
	ElemType arr[] = {1,2,3,4,5};
	headInit(dll,arr,5);
	printf("头插法:\t");
	printDoubleLinkList(dll);

	tailInit(dll,arr,5);
	printf("尾插法:\t");
	printDoubleLinkList(dll);

	insertElement(dll,3,6);
	printf("在第3个位置上插入6之后:\t");
	printDoubleLinkList(dll);

	ElemType e;
	deleteElement(dll,3,e);
	printf("删除第3个元素之后:\t");
	printDoubleLinkList(dll);
}

//头插法
void headInit(DLinkList * &dll,ElemType arr[], int n){
	int i;
	dll = (DLinkList *) malloc(sizeof(DLinkList));
	//头节点两个指针为NULL
	dll->next = dll->prior = NULL;
	DLinkList * node;
	for(i = 0; i<n; i++){
		node = (DLinkList *) malloc(sizeof(DLinkList));
		node->data = arr[i];
		/*
		 *插入,画图，依次赋值node->next，node->prior，dll->next(dll->prior永远为null)
		 *可以发现除了第一次插入，以后插入的节点都要设置dll->next->prior = node
		 */
		node->next = dll->next;
		if(dll->next != NULL){
			dll->next->prior = node;
		}
		node->prior = dll;
		dll->next = node;
	}
}

//尾插法
void tailInit(DLinkList * &dll,ElemType arr[], int n){
	int i;
	dll = (DLinkList *) malloc(sizeof(DLinkList));
	//头节点两个指针为NULL
	dll->next = dll->prior = NULL;
	DLinkList * node, *r;
	r = dll;
	for (i = 0; i < n; ++i) {
		node = (DLinkList *) malloc(sizeof(DLinkList));
		node->data = arr[i];
		//尾插,画图很简单
		node->prior = r;
		r->next = node;
		r=node;
	}
	r=NULL;
}

//插入节点，找出前一个节点
bool insertElement(DLinkList *&dll, int pos, ElemType e){
	int i = 0;
	DLinkList *p = dll, *node;
	while(i<pos-1 && p!=NULL){
		p = p->next;
		i++;
	}
	if(p==NULL){
		printf("插入的位置不合法");
		return false;
	}else{
		//分配节点
		node = (DLinkList *)malloc(sizeof(DLinkList));
		node->data = e;
		node->next = p->next;
		node->prior = p;
		if(p->next != NULL){
			p->next->prior = node;
		}
		p->next = node;
		return true;
	}
}

bool deleteElement(DLinkList *&dll, int pos, ElemType &e){
	int i = 0;
	DLinkList *p = dll, *node;
	while(i<pos-1 && p!=NULL){
		p = p->next;
		i++;
	}
	if(p==NULL){
		return false;
	}else{
		node = p->next;
		if(node == NULL){//如果p是尾节点，要删除的是尾节点的下一个节点，错误
			return false;
		}
		e = node->data;
		p->next = node->next;
		if(p->next != NULL){ //此时p->next已经改变，如果node->next为NULL.NULL不需要设置prior
			node->next->prior = p;
		}
		free(node);
		return true;
	}

}
void printDoubleLinkList(DLinkList * dll){
	//不需要输出头节点的data
	DLinkList *p = dll->next;
	while(p != NULL){
		printf("%d\t",p->data);
		p = p->next;
	}
	printf("\n");
}

输出结果

plaintext

头插法:	5	4	3	2	1	
尾插法:	1	2	3	4	5	
在第3个位置上插入6之后:	1	2	6	3	4	5	
删除第3个元素之后:	1	2	3	4	5