鏈表的機(jī)制靈活，用途廣泛，它適用于許多通用的數(shù)據(jù)庫(kù)。它也可以取代數(shù)據(jù)，作為其他存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)，例如棧和隊(duì)列，除非需要頻繁通過(guò)下標(biāo)隨機(jī)訪問(wèn)各個(gè)數(shù)據(jù)，否則在很多適用數(shù)組的地方都可以用鏈表代替。

鏈接點(diǎn)（Link）

在鏈表中，每個(gè)數(shù)據(jù)項(xiàng)都被包含在鏈接點(diǎn)中。一個(gè)鏈接點(diǎn)是某個(gè)類的對(duì)象，這個(gè)類可以叫做Link。因?yàn)橐粋€(gè)鏈表中有許多類似的鏈接點(diǎn)，所以有必要用一個(gè)不同于鏈表的類來(lái)表達(dá)鏈接點(diǎn)。每個(gè)Link對(duì)象中毒包含一個(gè)對(duì)下一個(gè)鏈接點(diǎn)引用的字段，通常叫做next,但是鏈表本身對(duì)象中有一個(gè)字段指向?qū)Φ谝粋€(gè)鏈接點(diǎn)的引用

單鏈表的實(shí)現(xiàn)

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的變量開(kāi)始時(shí)指向first，然后通過(guò)不斷地把自己復(fù)制給current.next，沿著鏈表向前移動(dòng)，在每個(gè)鏈接點(diǎn)處，find（）檢查鏈表節(jié)點(diǎn)的關(guān)鍵之是否和它尋找的相等，如果找到了，它返回對(duì)該鏈接點(diǎn)的引用。如果find（）到達(dá)鏈表的尾端，但沒(méi)有發(fā)現(xiàn)要找的鏈接點(diǎn)，則返回null

delete()方法

delete（）方法和find()方法類似，它先搜索要?jiǎng)h除的鏈接點(diǎn)。然而它需要掌握的不僅是指向當(dāng)前鏈接點(diǎn)的引用，還有指向當(dāng)前鏈接點(diǎn)的前一個(gè)（previous）鏈接點(diǎn)的引用，這是因?yàn)?，如果要?jiǎng)h除當(dāng)前的鏈接點(diǎn)必須把前一個(gè)鏈接點(diǎn)和后一個(gè)鏈接點(diǎn)連在一起，知道前一個(gè)鏈接點(diǎn)位置的唯一方法是擁有一個(gè)對(duì)它的引用

在while語(yǔ)句的每一次循環(huán)中，每當(dāng)current變量賦值為current.next之前，先把previous變量賦值為current，這保證了它總數(shù)指向current所指鏈接點(diǎn)的前一個(gè)鏈接點(diǎn)，一旦發(fā)現(xiàn)當(dāng)前鏈接帶你是要被刪除的鏈接點(diǎn)，就把前一個(gè)鏈接點(diǎn)的next字段賦值為當(dāng)前鏈接點(diǎn)的下一個(gè)鏈接點(diǎn)。如果當(dāng)前鏈接點(diǎn)是第一個(gè)鏈接點(diǎn)，這是一種特殊情況，因?yàn)檫@是由LinkList對(duì)象的first指向的鏈接點(diǎn)，而不是別的鏈接點(diǎn)的next字段所指的，在這種情況下，使first字段指向first.next，就可以刪除第一個(gè)鏈接點(diǎn)