链表之单向链表

链表的机制灵活，用途广泛，它适用于许多通用的数据库。它也可以取代数据，作为其他存储结构的基础，例如栈和队列，除非需要频繁通过下标随机访问各个数据，否则在很多适用数组的地方都可以用链表代替。

链接点（Link）

在链表中，每个数据项都被包含在链接点中。一个链接点是某个类的对象，这个类可以叫做Link。因为一个链表中有许多类似的链接点，所以有必要用一个不同于链表的类来表达链接点。每个Link对象中毒包含一个对下一个链接点引用的字段，通常叫做next,但是链表本身对象中有一个字段指向对第一个链接点的引用

单链表的实现

public class Link {
    public int iData;
    public double dData;
    public Link next;

    public Link(int id,double dd){
        iData=id;
        dData=dd;
    }

    public void displayLink(){
        System.out.println("{"+iData+","+dData+"}");
    }
}


class LinkList{
    private Link first;

    public LinkList(){
        first=null;
    }

    public boolean isEmpty(){
        return (first==null);
    }

    public void insertFirst(int id ,double dd){
        Link newLink=new Link(id,dd);
        newLink.next=first;
        first=newLink;
    }

    public Link deleteFirst(){
        Link tmp=first;
        first=first.next;
        return tmp;
    }

    public void displayList(){
        Link current=first;
        while(current!=null){
            current.displayLink();
            current=current.next;
        }
    }

    public Link find(int key){
        Link current=first;
        while (current.iData!=key){
            if(current.next==null){
                return null;
            }else{
                current=current.next;
            }
        }
        return current;
    }

    public Link delete(int key){
        Link current=first;
        Link previous=first;
        while (current.iData!=key){
            if(current.next==null){
                return null;
            }else{
                previous=current;
                current=current.next;
            }
        }
        if(current==first){
            first=first.next;
        }else{
            previous.next=current.next;
        }
        return current;
    }

    public static void main(String[] args) {
        LinkList linkList=new LinkList();

        linkList.insertFirst(22,2.2);
        linkList.insertFirst(44,4.3);

        linkList.displayList();
//
//        while(!linkList.isEmpty()){
//            Link link=linkList.deleteFirst();
//            System.out.println("deleted");
//            link.displayLink();
//        }
//        linkList.displayList();

        Link link = linkList.find(44);

        if(link!=null){
            System.out.println("find it"+link.iData);
        }else{
            System.out.println("not find link");
        }

        Link d=linkList.delete(44);
        if(d!=null){
            System.out.println("delete"+d.iData);
        }else{
            System.out.println("not delete");
        }
        linkList.displayList();
    }
}

find()方法

find()方法中被称为current的变量开始时指向first，然后通过不断地把自己复制给current.next，沿着链表向前移动，在每个链接点处，find（）检查链表节点的关键之是否和它寻找的相等，如果找到了，它返回对该链接点的引用。如果find（）到达链表的尾端，但没有发现要找的链接点，则返回null

delete()方法

delete（）方法和find()方法类似，它先搜索要删除的链接点。然而它需要掌握的不仅是指向当前链接点的引用，还有指向当前链接点的前一个（previous）链接点的引用，这是因为，如果要删除当前的链接点必须把前一个链接点和后一个链接点连在一起，知道前一个链接点位置的唯一方法是拥有一个对它的引用

在while语句的每一次循环中，每当current变量赋值为current.next之前，先把previous变量赋值为current，这保证了它总数指向current所指链接点的前一个链接点，一旦发现当前链接带你是要被删除的链接点，就把前一个链接点的next字段赋值为当前链接点的下一个链接点。如果当前链接点是第一个链接点，这是一种特殊情况，因为这是由LinkList对象的first指向的链接点，而不是别的链接点的next字段所指的，在这种情况下，使first字段指向first.next，就可以删除第一个链接点