数据结构（四）双向链表

一、概念

每个节点有一个数据域存放数据，一个前指针域指向前一节点，一个后指针域指向后一节点

优点是可以较低难度找到前一节点，缺点是占用内存空间较大

二、无头双向链表示意图

三、操作

（一）定义结构体

typedef struct twolist
{struct twolist *prv;int data; //以int型数据举例，可以放结构体成员struct twostack *next;
}ls_t;

（二）创建链表

1. 函数定义

int create_list(ls_t **my_list,int num);

创建第一个数据节点
初始化数据节点

2. 注意点

1. 入参合理性检查
2. 第一个数据节点的前指针和后指针均初始化为NULL

3. 代码实现

int create_list(ls_t **my_list,int num){if(NULL==my_list) return -1;*my_list=(ls_t *)malloc(sizeof(ls_t));if(NULL==*my_list) return -1;//初始化(*my_list)->prv=NULL;(*my_list)->next=NULL;(*my_list)->data=num;return 0;
}

（三）插入

1. 函数定义

2. 注意点

3. 代码实现

（四）删除

1. 函数定义

2. 注意点

3. 代码实现

（五）修改

1. 函数定义

2. 注意点

3. 代码实现

（六）查询

1. 函数定义

2. 注意点

3. 代码实现

（七）打印

1. 函数定义

int print_list(ls_t *my_list);

2. 注意点

1. 入参合理性检查

3. 代码实现

int print_list(ls_t *my_list){if(NULL==my_list) return -1;//打印除了最后一个元素的所有元素ls_t *ptemp=my_list;while(NULL!=ptemp->next){printf("%d ",ptemp->data);ptemp=ptemp->next;}//打印最后一个元素printf("%d ",ptemp->data);putchar(10);return 0;
}