12.2.1 Inserting into a Singly Linked List
How would we insert a new node into an ordered singly linked list? Suppose we had a new value, say 12, to insert into the previous list. Conceptually this task is easy: start at the beginning of the list, follow the pointers until you find the first node whose value is larger than 12, and then insert the new value into the list just before that node.
我们怎么才能把一个新节点插入到一个有序的单链表中呢?假定我们有一个新值，比如12 ，想把它插入到前面那个链表中。从概念上说，这个任务非常简单:从链表的起始位置开始，跟随指针直到找到第1 个值大于12 的节点，然后把这个新值插入到那个节点之前的位置。
In practice the algorithm is more interesting. We traverse the list and stop when we reach the node containing 15, the first value greater than 12. We know that the new value should be added to the list just before this node, but the pointer field of the previous node must be modified to accomplish the insertion. However, weʹve passed this node, and we cannot go back. The solution is to always save a pointer to the previous node in the list.
We will now develop a function to insert a node into an ordered, singly linked list. Program 12.1 is our first attempt.
实际的算法则比较有趣。我们按顺序访问链表， 当到达内容为15 的节点(第1 个值大于12 的节点)时就停下来。我们知道这个新值应该添加到这个节点之前，但前一个节点的指针字段必须进行修改以实现这个插入。但是，我们已经越过了这个节点，无法返回去。解决这个问题的方法就是始终保存一个指向链表当前节点之前的那个节点的指针。我们现在将开发一个函数，把一个节点插入到一个有序的单链表中。程序12 .1是我们的第1 次尝试。
#include <stdlib.h>
#include <stdio.h>
#include "sll_node.h"
#define FALSE 0
#define TRUE 1
int
sll_insert( Node *current, int new_value )
{
Node *previous;
Node *new;
while( current->value < new_value ){
previous = current;
current = current->link;
}
new = (Node *)malloc( sizeof( Node ) );
if( new == NULL )
return FALSE;
new->value = new_value;
new->link = current;
previous->link = new;
return TRUE;
}
Program 12.1 Insert into an ordered, singly linked list: first try insert1.c
We call the function in this manner:
我们用下面这种方法调用这个函数:
result = sll_insert( root, 12 );
Letʹs trace this code and see whether it correctly inserts the new value 12 into the list. First, the function is called with the value of the root variable, a pointer to the first node in the list. Here is the state of the list when the function begins:
让我们仔细跟踪代码的执行过程， 看看它是否把新值12 正确地插入到链表中。首先，传递给函数的参数是root 变量的值，它是指向链表第1 个节点的指针。当函数刚开始执行时，链表的状态如下:
This diagram does not show the root variable because the function cannot access it. A copy of its value came into the function as the parameter current, but the function cannot access root. Now current->value is 5, which is less than 12, so the body of the loop is executed once. When we get back to the top of the loop, our pointers will have advanced.
这张图并没有显示root 变量，因为函数不能访问它。它的值的一份拷贝作为形参current 传递给函数，但函数不能访问root 。现在current->value 是5 ，它小于12,所以循环体再次执行。当我们回到循环的顶部时， current 和previous 指针都向前移动了一个节点。
current->value is now 10, so the body of the loop executes again, with this result:
现在， current- >v alue 的值为10 ， 因此循环体还将继续执行，结果如下:
Now current->value is greater than 12 so the loop breaks.
现在， current - >value 的值大于12 ， 所以退出循环。
At this point the previous pointer is the important one, because it points to the node that must be changed to insert the new value. But first, a new node must be obtained to hold the value. The next diagram shows the state of the list after the value is copied into the new node.
此时， 重要的是previous 指针， 因为它指向我们必须加以修改以插入新值的那个节点。但首先，我们必须得到一个新节点，用于容纳新值。下面这张图显示了新值被复制到新节点之后链表的状态。
Linking the new node into the list requires two steps. First,
把这个新节点链接到链表中需要两个步骤。首先，
new->link = current;
makes the new node point to what will be the next node in the list, the first one we found with a value larger than 12. After this step, the list looks like this:
使新节点指向将成为链表下一个节点的节点，也就是我们所找到的第1 个值大于12 的那个节点。在这个步骤之后，链表的内容如下所示:
The second step is to make the previous node, the last one whose value was smaller than 12, point to the new node. The following statement performs this task.
第二个步骤是让previ ou s 指针所指向的节点(也就是最后一个值小于1 2 的那个节点〉指向这个新节点。下面这条语句用于执行这项任务。
previous->link = new;
The result of this step is:
这个步骤之后，链表的状态如下:
The function then returns, leaving the list looking like this:
然后函数返回，链表的最终样子如下:
Starting at the root pointer and following the links verifies that the new node has been correctly inserted.
从根指针开始，随各个节点的link 字段逐个访问链表，我们可以发现这个新节点己被正确地插入到链表中。