中午写了一篇关于单链表的博客。好吧，我并没有搜到我写的这篇文章。但我还是要写下去，万一有人看到了呢……不过，呵呵。。。
双链表和单链表的操作大同小异，只是多了一个前驱指针，我是这样定义的。
typedef struct node { int data; struct node * previous; struct node * next; } Node; typedef struct dlist { Node * head; } Dlist;
与单链表相比，它只多了一个前驱节点。请看图示！
这里用prev代表previous，我在第一次写双链表时，previous与next到底指向哪里纠结了半天，从图上来看，previous好像指向了前驱的next，然而并不是。
previous和next指向的都是节点的首地址，并不是previous或者next。也就是说previous和next里面存的是前驱节点和后继节点的地址值。
为了操作方便，我们设计了一个头节点。
void d_init(Dlist * list) { list->head = make_node(INT_MIN);//创建头节点，并赋值一个整形的最小值 }
因为双链表具有前驱指针，所以我们可以方便的找到要操作的节点的前驱和后继。
插入操作，要实现顺序链表，所以第一步还是找到插入位置，第二步进行插入。请看图示！
先做1、2步，再做3、4步，这里主要是想先讲新节点链接到链表上，1、2谁先并没有关系。然后将3节点的后继与5节点的前驱链接到新节点上。
这里还有一种情况，就是在最后的位置插入新节点。这样只需将将新节点与前驱节点链接就可以了。就是不做1、4步，先做2、再做3就可以了。
if ( current->next == NULL )//在链表的尾端插入和中间插入不同 { current->next = node; node->previous = current; } else { node->previous = current->previous; //将新节点的前驱指向当前节点的前驱 node->next = current;//将新节点的后继指向当前节点，所以这时一个前插方式 current->previous->next = node;//将当前节点的前驱的后继指向新节点 current->previous = node;//将当前节点的前驱指向新节点 }
删除操作，还是先找到删除节点。然后将删除节点从链表中摘出来，释放内存。请看图示！
由于我们只知道current指针，所以我们找到3节点的后继指针的办法是current->previous->next。而找5节点前驱指针也是类似的，current->next->privous。然后就可以释放删除节点了。
主要的操作已经讲完了，接下来看源码吧。
还是有两部分组成，dlist.h和dlist.c
dlist.h
#ifndef _DLIST_H #define _DLIST_H typedef struct node { int data; struct node * previous; struct node * next; } Node; typedef struct dlist { Node * head; } Dlist; void d_init(Dlist * list);//初始化 bool d_insert(Dlist * list, const int data);//插入 bool d_remove(Dlist * list, const int key);//移除 bool d_modify(Dlist * list, const int key, const int data);//修改 Node* d_find(Dlist * list, const int key);//查找 void d_treaverse(Dlist * list, void (*func)(void * pointer) );//遍历 void d_destroy(Dlist * list);//销毁 #endif //_DLIST_H
dlist.c
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <stdbool.h> #include "dlist.h" static Node* make_node(const int data);//创建节点 static void destroy_node(void * pointer);//销毁节点 static void treaverse_list(Node * current, void (*func)(void * pointer) );//遍历链表，包括头节点 void d_init(Dlist * list) { list->head = make_node(INT_MIN);//创建头节点，并赋值一个整形的最小值 } bool d_insert(Dlist * list, const int data) { Node * current = list->head;//当前指向头节点 Node * node;//新节点指针 while ( current->next != NULL && current->data < data) //找到插入位置 current = current->next;//在不是尾节点结束时，当前指针的值要大于新值，所以插入在当前节点之前 if ( current->data == data )//如果数据重复,插入失败 return false; node = make_node(data); if ( current->next == NULL )//在链表的尾端插入和中间插入不同 { current->next = node; node->previous = current; } else { node->previous = current->previous; //将新节点的前驱指向当前节点的前驱 node->next = current;//将新节点的后继指向当前节点，所以这时一个前插方式 current->previous->next = node;//将当前节点的前驱的后继指向新节点 current->previous = node;//将当前节点的前驱指向新节点 } return true; } bool d_remove(Dlist * list, const int key) { Node * current = list->head;//当前指针指向头节点 while ( (current = current->next) != NULL && current->data < key) ;//找到关键元素,由于是顺序链表,所以不用全部遍历全部链表，只要找到第一不小于关键key的位置 if ( current->next == NULL && current->data == key )//删除最后一个节点和中间节点方法不同 current->previous->next = NULL;//删除最后一个节点 else if ( current->data == key )//删除中间节点 { current->previous->next = current->next;//当前节点的前驱的后继指向当前节点的后继 current->next->previous = current->previous;//当前节点的后继的前驱指向当前节点的前驱 } else return false;//没有找到关键字,返回false free(current);//释放当前指针内存 return true; } bool d_modify(Dlist * list, const int key, const int data)//修改元素，因为是有序链表，所以要先删除后插入 { if ( d_remove(list, key) ) if ( d_insert(list, data) ) return true; return false; } Node* d_find(Dlist * list, const int key) { Node * current = list->head;//当前指针指向头节点 while ( (current = current->next) != NULL && current->data < key );//找到关键字位置 if (current->data == key)//判断查找的元素是否存在 return current; else return NULL; } void d_treaverse(Dlist * list, void (*func)(void * pointer) ) { treaverse_list(list->head->next, func);//遍历，不包括头节点 } void d_destroy(Dlist * list) { treaverse_list(list->head, destroy_node); //遍历，销毁链表 list->head = NULL; } static void treaverse_list(Node * current, void (*func)(void * pointer) )//这里使用函数指针，是为了程序的可扩展行，本程序中，d_treaverse 和 d_destroy 函数都用该函数实现不同功能 { while ( current != NULL )//遍历，包括头节点 { func(current); current = ( (Node *)current)->next; //强制类型转换，由于->的优先级高于()，所以用括号改变结合顺序 } } static void destroy_node(void * pointer)//释放内存 { free((Node *)pointer); } static Node* make_node(const int data)//创建节点 { Node * node = (Node *)malloc( sizeof(Node) ); if ( node == NULL ) { exit(1); printf("动态分配内存失败，程序结束."); } node->data = data; node->previous = NULL; node->next = NULL; return node; }
还有一件事忘说了，这些代码都是在gcc下调试过的，我电脑没装Windows，所以就没有实验，不过问题应该不大，如果哪里出现问题，请联系我，欢迎大家指正。。。
2016-01-10
原文：http://www.cnblogs.com/ITgaozy/p/5119825.html