单向链表:http://blog.csdn.net/morixinguan/article/details/77756216
单向链表理解了,那双向就非常简单了,没什么好说的,看图:
双链表的引入是为了解决单链表的不足:
(1)双链表可以往前遍历,也可以往后遍历,具有两个方向
双链表的节点 = 有效数据 + 两个指针(分别指向前一个节点和后一个节点)
双向链表的图形结构描述:
可以用一个简单的数据结构来描述上面的这个图:
struct double_list struct double_list
{ {
数据域; ep :-------> int data ;
指针域(前向指针) ; struct double_list *prev ;
指针域(后向指针) ; struct double_list *next ;
}; };
2、双向链表的创建
struct list *create_node(int data) ; 创建步骤(与单链表类似,就是多了一个指针): (1)给节点申请空间: ep : struct double_list *p = malloc(sizeof(struct double_list)); (2)初始化数据域 ep : p->data = data ; (3)初始化指针域 ep : p->prev = NULL ; p->next = NULL ;3、双向链表的尾插
双向链表尾插节点的函数可以定义如下:
void double_list_tail_insert(struct double_list *header , struct double_list *new) ;
尾插图示操作:
尾插的步骤:
(1)找到链表的尾节点 ep : 和单链表差不多 DL *p = header ; while(NULL != p->next) p = p->next ; (2)将新的节点连接到尾节点的后面成为新的节点 1.原来的next指针指向新节点的首地址。 p->next = new ; 2.新节点的prev指针指向原来的尾节点的首地址。 new->prev = p;4、双向链表的头插
双向链表头插节点的函数可以定义如下:
void double_list_top_insert(struct double_list *header , struct double_list *new) ;
5、双向链表的遍历
5.1 正向遍历 void double_list_for_each(DL *header) 步骤:和单链表完全一致,没什么好写的。 5.2 反向遍历 void double_list_for_each_nx(DL *header) 步骤:(1)和单链表一样,先循环找到最后一个节点的地址 (2)再依靠prev指针循环往前移动 2.1 先打印最后一个数据 ep : printf("%d ",p->data); 2.2 向前循环遍历 ep : p = p->prev ; 判断条件:header->prev != p->prev, header保存的是头节点的地址, header->prev保存的是头节点的prev的地址, header->next保存的是头节点的next的地址, 头节点在创建的时候: header->prev = NULL ; header->next = NULL ; 所以这个条件这样写header->prev = NULL也是对的。6、双向链表节点的删除
假设需要删除节点1: 首先: (1)获取当前节点的地址: ep : p = header; (2)遍历所有的节点,找到要删除的节点: ep : while(NULL != p->next) { p = p->next ; if(p->data == data) { } } (3)找到要删除的数据以后,需要做判断,判断两种情况,这和单链表差不多 3.1 如果找到当前节点的下一个节点不为空 3.1.1 那就把当前节点的prev节点指向要删除的这个节点的prev 因为当前的prev节点保存的是要删除的上一个节点的指针 p->next->prev = p->prev ; 3.1.2 然后将当前节点的prev指针(也就是上一个节点的指针)指向当前节点(要删除的)的下一个节点: p->prev->next = p->next ; 3.1.3 最后释放删除指针的空间: free(p); 3.2 如果找到当前节点的下一个节点为空 3.2.1 直接把当前指针(要删除的节点)的prev指针(保存着当前指针的上一个节点的地址)的下一个next指针设置为空。 p->prev->next = NULL ; 3.2.2 将删除的指针的空间释放: free(p);看来,双链表学起来比单链表容易多了!确实啊,多了一个方向,操作起来就更加容易了,但是多了一个方向,一维多了一个指针,相比增加了一定的复杂度,但是,只要牢记prev指针和next指针的指向,那么,手画一图,代码即可写出!
下面给一个案例实现一下双向链表:
#include <stdio.h> #include <stdlib.h> #include <string.h> //创建一个双链表的数据结构 typedef struct __double_list { int data ; struct __double_list *prev ; struct __double_list *next ; }DL ; //创建双向链表并插入一个节点 DL *create_dl_node(int data) { DL *p = malloc(sizeof(DL)); if(NULL == p) { printf("create dl node fair!\n"); return NULL ; } //初始化数据 p->data = data ; //初始化指针 p->next = NULL ; p->prev = NULL ; } //双向链表的尾插 void double_list_tail_insert(DL *header , DL *new) { //取得当前节点的地址 DL *p = header ; //找到链表的尾节点 while(NULL != p->next) { //找不到接着找 p = p->next ; } //找到了尾节点,指向新节点的首地址 p->next = new ; //新节点的prev指针指向原来的尾节点的首地址。 new->prev = p; } //双向链表的头插(也就是插在两个节点之间的插入方式) void double_list_top_insert(DL *header , DL *new) { //新节点的next指针指向原来的节点一的地址 new->next = header->next ; //判断当前节点的下一个节点的地址是否为空 if(NULL != header->next) header->next->prev = new ; //节点1的prev指针指向新节点的地址 header->next = new ; new->prev = header ; } //双向链表的正向遍历 void double_list_for_each(DL *header) { DL *p = header ; while(NULL != p->next) { p = p->next ; printf("%d ",p->data); } } //双向链表的反向遍历 void double_list_for_each_nx(DL *header) { DL *p = header ; //先找到尾节点 while(NULL != p->next) { p = p->next ; } //已经找到了尾节点,向前遍历,注意,遍历到头节点之前 //限制条件: != 头结点 while(NULL != p->prev) { printf("%d ",p->data); p = p->prev ; } } //双向链表节点的删除 int double_list_delete_node(DL *header , int data) { //取得当前节点 DL *p = header; //遍历所有的节点 while(NULL != p->next) { p = p->next ; //找到了对应要删除的数据了 if(p->data == data) { //一样存在两种情况 //(1)当前节点的下一个节点不为空 if(p->next != NULL) { //那就把当前节点的prev节点指向要删除的这个节点的prev //因为当前的prev节点保存的是要删除的上一个节点的指针 p->next->prev = p->prev ; //还要指定它的next节点 p->prev->next = p->next ; free(p); } //(2)当前节点的下一个节点为空 else { //把 p->prev->next = NULL ; free(p); } return 0 ; } } printf("\n没有找到对应要删除的节点,或者节点已经被删除!\n"); return -1 ; } int main(void) { int i ; DL *header = create_dl_node(0); for(i = 0 ; i < 10 ; i++) { //双向链表的尾插 //double_list_tail_insert(header,create_dl_node(i)); //双向链表的头插 double_list_top_insert(header,create_dl_node(i)); } //双向链表的正向遍历 printf("双向链表的正向遍历:"); double_list_delete_node(header,5); double_list_for_each(header); // double_list_delete_node(header,9); double_list_delete_node(header,5); putchar('\n'); printf("双向链表的反向遍历:"); double_list_for_each_nx(header); return 0 ; }运行结果: