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 字段逐個通路連結清單，我們可以發現這個新節點己被正确地插入到連結清單中。