C语言双链表插入

有序双链表

typedef struct NODE { struct NODE* fwd; struct NODE* bwd; int value; }Node;

fwd指向下一个节点，bwd指向前一个节点。

可能的情况：

1）新值插入到链表中间位置；

2）新值插入到链表的起始位置；

3）新值插入到链表的结束位置；

4）新值插入到链表的起始位置，又插入到链表的结束位置（原链表为空）。

/* **把一个值插入到一个双链表，rootp是一个指向根节点的指针， **value是要插入的新值 **返回值：如果要插入的值已经存在，返回0 **如果内存不足导致无法插入，返回-1，如果插入成功，返回1。 */ #include <stdlib.h> #include <stdio.h> #include "doubly_linked_list_node.h" int dll_insert(Node *rootp, int value) { Node *this; Node *next; Node *newnode; /* **查看value是否已经存在于链表中，如果是就返回 **否则，创建一个新节点（让newnode指向它） **“this”将指向应该在新节点之前的那个节点 **“next”蒋指向应该在新节点之后的那个节点 */ for(this = rootp; (next = this->fwd) != NULL; this = next){ if(next->value == value) return 0; if(next->value > value) break; } newnode = (Node*)malloc(sizeof(Node)); if(newnode = NULL) return -1; newnode->value = value; /* **把新节点添加到链表中 */ if(next != NULL){ /* **情况1/2：不位于链表尾部 */ if(this != rootp){ /*情况1：不在起始位置*/ newnode->bwd = this; newnode->fwd = next; this->fwd = newnode; next->bwd = newnode; } else{ /*情况2：位于链表起始位置*/ rootp->fwd = newnode; next->bwd = newnode; newnode->bwd = NULL; newnode->fwd = next; } } else{ /* **情况3/4：位于链表的尾部 */ if(this != NULL){ /*情况3：位于结束位置，不在起始位置*/ newnode->fwd = NULL; newnode->bwd = this; this->fwd = newnode; rootp->bwd = newnode; } else{ /*情况4：位于链表起始位置也位于结束位置*/ newnode->fwd = NULL; newnode->bwd = NULL; rootp->fwd = newnode; rootp->bwd = newnode; } return 1; }

技巧一：statement factoring:

各个嵌套的if语句内存在大量相似之处，所以把他们提炼出来

/* **把新节点添加到链表中 */ if(next != NULL){ /* **情况1/2：不位于链表尾部 */ newnode->fwd = next; if(this != rootp){ /*情况1：不在起始位置*/ newnode->bwd = this; this->fwd = newnode; } else{ /*情况2：位于链表起始位置*/ rootp->fwd = newnode; newnode->bwd = NULL; } next->bwd = newnode; } else{ /* **情况3/4：位于链表的尾部 */ newnode->fwd = NULL; if(this != NULL){ /*情况3：位于结束位置，不在起始位置*/ newnode->bwd = this; this->fwd = newnode; } else{ /*情况4：位于链表起始位置也位于结束位置*/ newnode->bwd = NULL; rootp->fwd = newnode; } rootp->bwd = newnode; } return 1; }

技巧二：逻辑提炼

情况3/4的第一条，this=NULL的时候赋值给newnode->bwd=NULL相当于newnode->bwd=this，

/* **把新节点添加到链表中 */ newnode->fwd = next; if(this != rootp){ /*情况1：不在起始位置*/ newnode->bwd = this; this->fwd = newnode; } else{ /*情况2：位于链表起始位置*/ rootp->fwd = newnode; newnode->bwd = NULL; } if(next != NULL) next->bwd = NULL; else rootp->bwd = newnode;