12.3 双链表
单链表的替代方案就是双链表。在一个双链表中，每个结点都包含两个指针---指向前一个节点的指针和指向后一个节点的指针。这可以使我们以任何方向遍历双链表，甚至可以随意在双链表中访问。
下面是节点类型的声明：
typedef struct NODE {
struct NODE *fwd;
struct NODE *bwd;
int value;
} Node;
现在，存在两个根指针：一个指向链表的第一个节点，另一个指向后一个节点。这两个指针允许从链表的任何一端开始遍历链表。
我们可能想把两个根指针分开声明为两个变量。但这样一来，我们必须把两个指针都传递给插入函数。为根指针声明一个完整的节点更为方便，只是它的值绝不会被使用。在我们的例子中，这个技巧只是浪费了一个整型值的内存空间。对于值非常大的链表，分开声明两个指针可能更好一些。另外，也可以在根节点的值字段中保存其他一些关于链表的信息，例如链表当前包含的节点数量。
根节点的fwd字段指向链表的第1个节点，根节点的bwd字段指向链表的最后一个节点。如果链表为空，这两个字段都为NULL。链表第1个节点的bwd字段和最后1个节点的fwd字段都为NULL。在一个有序的链表中，各个节点将根据value字段的值以升序排列。
12.3.1 在双链表中插入
要编写一个函数，把一个值插入到一个有序的双链表中。dll_insert函数接受2个参数，一个指向根节点的指针和一个整型值。先前所编写的单链表输入函数把重复的值也添加到链表中。在有些应用中，不插入重复的值可能更为合适。dll_insert函数只有当待插入的值原先不存在于链表中是才将其插入。
用一种更为规范的方法来编写这个函数。当把一个节点插入到一个链表时，可能出现4中情况：
1.新值可能必须插入到链表的中间位置；
2.新值可能必须插入到链表的起始位置；
3.新值可能必须插入到链表的结束位置；
4.新值可能必须既插入到链表的起始位置，又插入到链表的结束位置（即原链表为空）。
在每种情况下，有4个指针必须进行修改。
在情况1和情况2中，新节点的fwd字段必须设置为指向链表的下一个节点，链表下一个节点的bwd字段必须设置为指向这个新节点。
在情况3和情况4中，新节点的fwd字段必须设置为NULL，根节点的bwd字段必须设置为指向新节点。
在情况1和情况3中，新节点的bwd字段必须设置为指向链表的前一个节点，而链表前一个节点的fwd字段必须设置为指向新节点。
在情况2和情况4中，新节点的bwd字段必须设置为NULL，根节点的fwd字段必须设置为指向新节点。
程序12.4简明的实现方法可以帮助你加深理解。
#include
#include
#include"doubly_linked_list_node.h"
int dll_insert( Node *rootp, int value ){
Node *this;
Node *next;
Node *newnode;
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 ){
if( this != rootp ){
newnode->fwd = next;
this->fwd = newnode;
newnode->bwd = this;
next->bwd = newnode;
}else{
newnode->fwd = next;
rootp->fwd = newnode;
newnode->bwd = NULL;
next->bwd = newnode;
}
}else{
if( this != rootp ){
newnode->fwd = NULL;
this->fwd = newnode;
newnode->bwd = this;
rootp->bwd = newnode;
}else{
newnode->fwd = NULL;
rootp->fwd = newnode;
newnode->bwd = NULL;
rootp->bwd = newnode;
}
}
return 1;
}
程序12.4 简明的双链表插入函数 dll_ins1.c
#ifndef DOUBLY_LINKED_LIST_NODE_H
#define DOUBLY_LINKED_LIST_NODE_H
typedef struct NODE {
struct NODE *fwd;
struct NODE *bwd;
int value;
} Node;
extern int dll_insert( Node *rootp, int value );
extern void dll_free( Node *rootp );
#endif
#include
#include
#include"doubly_linked_list_node.h"
int dll_insert( Node *rootp, int value ){
Node *this2;
Node *next;
Node *newnode;
for( this2 = rootp; (next = this2->fwd) != NULL; this2 = 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 ){
if( this2 != rootp ){
newnode->fwd = next;
this2->fwd = newnode;
newnode->bwd = this2;
next->bwd = newnode;
}else{
newnode->fwd = next;
rootp->fwd = newnode;
newnode->bwd = NULL;
next->bwd = newnode;
}
}else{
if( this2 != rootp ){
newnode->fwd = NULL;
this2->fwd = newnode;
newnode->bwd = this2;
rootp->bwd = newnode;
}else{
newnode->fwd = NULL;
rootp->fwd = newnode;
newnode->bwd = NULL;
rootp->bwd = newnode;
}
}
return 1;
}
void dll_free( Node *rootp ){
Node *current;
Node *temp;
current = rootp;
while( current ){
temp = current->fwd;
printf( "after temp = current->fwd, current = %p, temp = %pn", current, temp );
free( current );
printf( "after free( current ), current = %p, current->fwd = %pn", current, current->fwd );
current = temp;
printf( "after current = temp, current = %pn", current );
}
}
#include
#include
#include "doubly_linked_list_node.h"
int main( void ){
Node *root;
Node *pt;
Node *node, *node2, *node3;
int result;
node = (Node *)malloc( sizeof(Node) );
node2 = (Node *)malloc( sizeof(Node) );
node3 = (Node *)malloc( sizeof(Node) );
if( node && node2 && node3 ){
root = node;
node->value = 5;
node->fwd = node2;
node->bwd = NULL;
node2->value = 10;
node2->fwd = node3;
node2->bwd = node;
node3->value = 15;
node3->fwd = NULL;
node3->bwd = node2;
}
printf( "print original elements in linked list from left to right:n" );
pt = root;
while( pt ){
printf( "%d ", pt->value );
pt = pt->fwd;
}
printf( "n" );
printf( "print original elements in linked list from right to left:n" );
pt = node3;
while( pt ){
printf( "%d ", pt->value );
pt = pt->bwd;
}
printf( "n" );
result = dll_insert( node3, 12 );
printf( "after result = dll_insert( root, 12 ), result = %dn", result );
printf( "print elements in linked list:n" );
pt = root;
while( pt ){
printf( "%d ", pt->value );
pt = pt->fwd;
}
printf( "n" );
result = dll_insert( node3, 20 );
printf( "after result = dll_insert( root, 20 ), result = %dn", result );
printf( "print elements in linked list:n" );
pt = root;
while( pt ){
printf( "%d ", pt->value );
pt = pt->fwd;
}
printf( "n" );
result = dll_insert( node3, 4 );
printf( "after result = dll_insert( root, 4 ), result = %dn", result );
printf( "print elements in linked list:n" );
pt = root;
while( pt ){
printf( "%d pt = %p,", pt->value, pt );
pt = pt->fwd;
printf( "after pt = pt->fwd, pt = %pn", pt );
}
printf( "n" );
dll_free( root );
return EXIT_SUCCESS;
}
一开始，函数使this指向根节点。next指针始终指向this之后的那个节点。它的思路是这两个指针同步前进，直到新节点应该插入到这两者之间。for循环检查next所指节点的值，判断是否达到需要插入的位置。
如果在链表中找到新值，函数就简单地返回；否则，当到达链表尾部或找到适当的插入位置时循环终止。在任何一种情况下，新节点都应该插入到this所指的节点后面。注意，在决定新值是否应该插入到链表之前，并不为它分配内存。如果实现分配内存，但发现新值原先已经存在于链表中，就有可能发生内存泄漏。
4种情况是分开实现的。让我们通过把12插入到链表中来观察情况1。
然后，函数为新节点分配内存。
newnode->fwd = next;
this->fwd = newnode;
然后，执行下列语句：
newnode->bwd = this;
next->bwd = newnode;
这就完成了把新值插入到链表的过程。
请研究一下代码，确定应该如何处理剩余的几种情况，确保它们都能正确工作。
简化插入函数
提示：
细心的程序员会发现，在函数中各个嵌套的if语句群存在大量的相似之处，而优秀的程序员会对程序员出现这么多的重复代码感到厌烦。所以，我们现在将使用两个技巧消除这些重复的代码。第1个技巧是语句提炼（statement factoring），如下面的例子所示：
if( x == 3 ){
i = 1;
something;
j = 2;
}else{
i = 1;
something different;
j = 2;
}
注意，不管表达式x==3的值是真还是假，语句i=1和j=2都将执行。在if之前执行i=1不会影响x==3的测试结果，所以这两条语句都可以被提炼出来，这样就产生了更为简单但同样完整的语句：
i = 1;
if( x == 3 ){
something;
} else{
something different;
}
j = 2;
警告：
如果if之前的语句会对测试的结果产生影响，则千万不要把它提炼出来。例如，在下面的例子中：
if( x == 3 ){
x = 0;
something;
} else{
x = 0;
something different;
}
语句x=0不能被提炼出来，因为它会影响比较的结果。
把程序12.4最内层嵌套的if语句进行提炼，就产生了程序12.5的代码段。请将这段代码和前面的函数进行比较，确认它们是等价的。
if( next != NULL ){
newnode->fwd = next;
if( this != rootp ){
this->fwd = newnode;
newnode->bwd = this;
}else{
rootp->fwd = newnode;
newnode->bwd = NULL;
}
next->bwd = newnode;
}else{
newnode->fwd = NULL;
if( this != rootp ){
this->fwd = newnode;
newnode->bwd = this;
}else{
rootp->fwd = newnode;
newnode->bwd = NULL;
}
rootp->bwd = newnode;
}
程序12.5 双链表插入逻辑的提炼 dll_ins2.c
#include
#include
#include"doubly_linked_list_node.h"
int dll_insert( Node *rootp, int value ){
Node *this2;
Node *next;
Node *newnode;
for( this2 = rootp; (next = this2->fwd) != NULL; this2 = 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 ){
newnode->fwd = next;
if( this2 != rootp ){
this2->fwd = newnode;
newnode->bwd = this2;
}else{
rootp->fwd = newnode;
newnode->bwd = NULL;
}
next->bwd = newnode;
}else{
newnode->fwd = NULL;
if( this2 != rootp ){
this2->fwd = newnode;
newnode->bwd = this2;
}else{
rootp->fwd = newnode;
newnode->bwd = NULL;
}
rootp->bwd = newnode;
}
return 1;
}
void dll_free( Node *rootp ){
Node *current;
Node *temp;
current = rootp;
while( current ){
temp = current->fwd;
printf( "after temp = current->fwd, current = %p, temp = %pn", current, temp );
free( current );
printf( "after free( current ), current = %p, current->fwd = %pn", current, current->fwd );
current = temp;
printf( "after current = temp, current = %pn", current );
}
}
newnode->fwd = next;
if( this != rootp ){
this->fwd = newnode;
newnode->bwd = this;
} else{
rootp->fwd = newnode;
newnode->bwd = NULL;
}
if( next != NULL ){
next->bwd = newnode;
} else{
rootp->bwd = newnode;
}
程序12.6 双链表插入逻辑的进一步提炼 dll_ins3.c
#include
#include
#include"doubly_linked_list_node.h"
int dll_insert( Node *rootp, int value ){
Node *this2;
Node *next;
Node *newnode;
for( this2 = rootp; (next = this2->fwd) != NULL; this2 = 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;
newnode->fwd = next;
if( this2 != rootp ){
this2->fwd = newnode;
newnode->bwd = this2;
} else{
rootp->fwd = newnode;
newnode->bwd = NULL;
}
if( next != NULL ){
next->bwd = newnode;
} else{
rootp->bwd = newnode;
}
return 1;
}
void dll_free( Node *rootp ){
Node *current;
Node *temp;
current = rootp;
while( current ){
temp = current->fwd;
printf( "after temp = current->fwd, current = %p, temp = %pn", current, temp );
free( current );
printf( "after free( current ), current = %p, current->fwd = %pn", current, current->fwd );
current = temp;
printf( "after current = temp, current = %pn", current );
}
}
#include
#include
#include"doubly_linked_list_node.h"
int dll_insert( Node *rootp, int value ){
Node *this;
Node *next;
Node *newnode;
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;
newnode->fwd = next;
this->fwd = newnode;
if( this != rootp ){
newnode->bwd = this;
} else{
newnode->bwd = NULL;
}
if( next != NULL ){
next->bwd = newnode;
} else{
rootp->bwd = newnode;
}
return 1;
}
程序12.7 双链表插入函数的最终简化版本 dll_ins4.c
#include
#include
#include"doubly_linked_list_node.h"
int dll_insert( Node *rootp, int value ){
Node *this2;
Node *next;
Node *newnode;
for( this2 = rootp; (next = this2->fwd) != NULL; this2 = 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;
newnode->fwd = next;
this2->fwd = newnode;
if( this2 != rootp ){
newnode->bwd = this2;
} else{
newnode->bwd = NULL;
}
if( next != NULL ){
next->bwd = newnode;
} else{
rootp->bwd = newnode;
}
return 1;
}
void dll_free( Node *rootp ){
Node *current;
Node *temp;
current = rootp;
while( current ){
temp = current->fwd;
printf( "after temp = current->fwd, current = %p, temp = %pn", current, temp );
free( current );
printf( "after free( current ), current = %p, current->fwd = %pn", current, current->fwd );
current = temp;
printf( "after current = temp, current = %pn", current );
}
}
这个函数无法再大幅度改善了，但我们可以让源代码更小一些。第一条if语句的目的是判断赋值语句右边一侧的值。我们可以用一个条件表达式来取代if语句。我们也可以用条件表达式取代第二条if语句，但这个修改的意义并不是很大。
提示：
程序12.8的代码确实更小一些，但它是不是真的更好？尽管它的语句数量减少了，但必须执行的比较和赋值操作还是和前面一样多，
所以这段代码的运行速度并不比前面的更快。这里存在两个微小的差别：newnode->bwd和->bwd = newnode都只编写了一次而不是两次。这些差别能不能产生更小的目标代码呢？也许会，这取决于你的编译器优化措施是否出色。但是，即使会产生更小的代码，其差别也是很小的，但这段代码的可读性较之前面的代码有所下降，尤其是对于那些缺乏经验的C程序员而言。因此，程序12.8维护起来或许更困难一些。
如果程序的大小或者执行速度确实至关重要，我们可能只好考虑用汇编语言来编写函数。但即便编码方式上采取如此巨大的变化，也不能保证肯定会有任何重大的改进。另外还要考虑到汇编代码难于编写、难于阅读和难于维护。所以，只有迫不得已的时候，才能求诸于汇编语言。
newnode->fwd = next;
this->fwd = newnode;
newnode->bwd = this != rootp ? this : NULL;
(next != NULL ? next : rootp)->bwd = newnode;
程序12.8 使用条件表达式实现插入函数 dll_ins5.c
#include
#include
#include"doubly_linked_list_node.h"
int dll_insert( Node *rootp, int value ){
Node *this2;
Node *next;
Node *newnode;
for( this2 = rootp; (next = this2->fwd) != NULL; this2 = 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;
newnode->fwd = next;
this2->fwd = newnode;
newnode->bwd = this2 != rootp ? this2 : NULL;
(next != NULL ? next : rootp)->bwd = newnode;
return 1;
}
void dll_free( Node *rootp ){
Node *current;
Node *temp;
current = rootp;
while( current ){
temp = current->fwd;
printf( "after temp = current->fwd, current = %p, temp = %pn", current, temp );
free( current );
printf( "after free( current ), current = %p, current->fwd = %pn", current, current->fwd );
current = temp;
printf( "after current = temp, current = %pn", current );
}
}
