在鏈表中保持?jǐn)?shù)據(jù)有序是有用的，具有這個(gè)特性的鏈表叫做有序鏈表

一般，在大多數(shù)需要使用有序數(shù)組的場(chǎng)合也可以使用有序鏈表，有序鏈表優(yōu)于有序數(shù)組的地方是插入的速度，因?yàn)樵夭恍枰苿?dòng)，另外鏈表可以擴(kuò)展到全部有效的使用內(nèi)存，而數(shù)組只能局限于一個(gè)固定的大小中，但是，有序鏈表實(shí)現(xiàn)起來(lái)比有序數(shù)組更困難一些

在有序鏈表中插入一個(gè)數(shù)據(jù)項(xiàng)的Java代碼

為了在一個(gè)有序鏈表中插入數(shù)據(jù)項(xiàng)，算法必須首先搜索鏈表，直到找到合適的位置，它恰好在第一個(gè)比他大的數(shù)據(jù)項(xiàng)的前面，當(dāng)算法找到了要插入的位置，用通常的方式插入數(shù)據(jù)項(xiàng)，把新連接點(diǎn)的next字段指向下一個(gè)鏈接點(diǎn)，然后與把前一個(gè)鏈接點(diǎn)的next字段改為指向新的鏈接點(diǎn)。然而，需要考慮一些特殊的情況，鏈接點(diǎn)有可能插在表頭，或者插在表尾，看下這段代碼

public void insert(long key){
    Link newLink=new Link(key);
    Link previous=null;
    Link current=first;
     
    while(current!=null &&key>current.dData){
        previous=current;
        current=current.next;
    }
    
    if(previous==null){
        first=newLink;
    }else{
        previous.next=newLink;
        newLink.next=current;
    }
}

在鏈表上移動(dòng)時(shí)，需要用一個(gè)previous的引用，這樣才能把前一個(gè)鏈接點(diǎn)的next字段指向新的鏈接點(diǎn)。創(chuàng)建新鏈接點(diǎn)后，把current標(biāo)量設(shè)為first，準(zhǔn)備搜索正確的插入點(diǎn)。這時(shí)也把previous設(shè)為null值，這步操作很重要，因?yàn)楹竺嬉眠@個(gè)null值判斷是否仍在表頭

while循環(huán)和以前用來(lái)搜索插入點(diǎn)的代碼類(lèi)似，但是有一個(gè)附加的條件。如果當(dāng)前檢查的鏈接點(diǎn)的關(guān)鍵值不再小于待插入的鏈接點(diǎn)的關(guān)鍵值，則循環(huán)結(jié)束；這是最常見(jiàn)的情況，即新關(guān)鍵值插在鏈表中部的某個(gè)地方，那么當(dāng)while循環(huán)結(jié)束時(shí)，current可能在表頭，中間或者表尾，或者鏈表是空的，如果current在表頭，或者鏈表為空，previous將為null值；所以讓first指向新的鏈接點(diǎn)，否則current處在鏈表中部或表尾，就讓previous的next字段指向新的鏈接點(diǎn)

不論哪種情況，都讓新鏈接點(diǎn)的next字段指向current,如果在表尾，current為null值，則新鏈接點(diǎn)的next字段也本應(yīng)該設(shè)為null值