有序链表

在链表中保持数据有序是有用的，具有这个特性的链表叫做有序链表

一般，在大多数需要使用有序数组的场合也可以使用有序链表，有序链表优于有序数组的地方是插入的速度，因为元素不需要移动，另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中，但是，有序链表实现起来比有序数组更困难一些

在有序链表中插入一个数据项的Java代码

为了在一个有序链表中插入数据项，算法必须首先搜索链表，直到找到合适的位置，它恰好在第一个比他大的数据项的前面，当算法找到了要插入的位置，用通常的方式插入数据项，把新连接点的next字段指向下一个链接点，然后与把前一个链接点的next字段改为指向新的链接点。然而，需要考虑一些特殊的情况，链接点有可能插在表头，或者插在表尾，看下这段代码

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;
    }
}

在链表上移动时，需要用一个previous的引用，这样才能把前一个链接点的next字段指向新的链接点。创建新链接点后，把current标量设为first，准备搜索正确的插入点。这时也把previous设为null值，这步操作很重要，因为后面要用这个null值判断是否仍在表头

while循环和以前用来搜索插入点的代码类似，但是有一个附加的条件。如果当前检查的链接点的关键值不再小于待插入的链接点的关键值，则循环结束；这是最常见的情况，即新关键值插在链表中部的某个地方，那么当while循环结束时，current可能在表头，中间或者表尾，或者链表是空的，如果current在表头，或者链表为空，previous将为null值；所以让first指向新的链接点，否则current处在链表中部或表尾，就让previous的next字段指向新的链接点

不论哪种情况，都让新链接点的next字段指向current,如果在表尾，current为null值，则新链接点的next字段也本应该设为null值