一、前言

鏈表是一個和陣列不一樣的存盤方式，我們都知道陣列的存盤地址是連續的，這樣就不能很好的利

用好記憶體空間，而鏈表就解決了這個問題，鏈表是一存盤地址不連續的的存盤結構，這樣的好處

就是能節省空間，

二、鏈表的簡介

鏈表是由一系列的結點構成的，鏈表的第一個元素為頭結點，頭結點的特點是；不存放具體的數

表示單鏈表的表頭，比如要找一個結點就是從頭結點一個一個往下找的，

每一個結點有一個類似于指標的next，用來指向下一個結點，和一個date區域用于存盤資料

頭結點不存放資料，最后一個結點不指向null，

三、單向鏈表的API設定

代碼實作

結點類：鏈表的設定結點類少不了

   //定義節點類(成員內部類)
    private class Node{
        //存盤資料
        T item;
        //下一個節點
        Node next;
        public Node(T item,Node next){
            this.item=item;
            this.next=next;
        }
    }

成員變數和構造方法

   //記錄頭節點
    private Node head;
    //記錄鏈表的長度
    private int N;
    //構造方法用來初始化成員變數
    public LinkList(){
        this.head=new Node(null,null);
        this.N=0;
    }

清空鏈表，鏈表的長度，鏈表是否為空

 //方法1：清空鏈表
    public void clear(){
        head.next=null;//將頭結點的指向置空
        this.N=0;//元素個數變為0
    }
    //方法2：鏈表的長度
    public int length(){
        return N;//N就是鏈表長度
    }
    //方法3：判斷鏈表是否為空
    public boolean isEmpty(){
        return this.N==0;//只需判斷N是否為0即可
    }

獲取指定位置處的元素

//方法4：獲取指定位置處的元素
    public T get(int i){
             Node node=head.next;//node是下一個結點
          if(node!=null){//有下一個結點
            for(int index=0;index<i;index++){
                node=node.next;//往下一個結點移動
            }
            return node.item;
        }
        return null;
    }

插入元素t(在鏈表的最后以結點后插入元素)

 //方法5：插入元素t(在鏈表的最后以結點后插入元素)
    public void insert(T t){
        //創建一個結點
        Node node=head;
        while(node.next!=null){//找到最后一個結點的前一個結點
            node=node.next;
        }

        Node newLast=new Node(t, null);
        //之前的最后指向現在的最后結點
       node.next=newLast;
       //元素個數加一
        N++;
    }

在指定i處，添加元素t

 //方法6：在指定i處，添加元素t
    public void insert(int i,T t){
        //創建一個結點，從頭結點開始
        Node node =head;
        for(int index=0;index<i;index++){//找到i位置處的前一個元素
            node=node.next;
        }
        //當前i位置的結點
        Node oldNode=node.next;
        //創建結點t
        Node newNode=new Node(t, null);
        //此時node表示的還是前一個結點，所以只需要把前一個結點指向創建的新結點
        node.next=newNode;
        //新結點指向原來i位置處的結點，即可完成連接
        newNode.next=oldNode;
        //元素個數加一
        N++;
    }

洗掉指定位置i處的元素并回傳被洗掉的元素

 //方法7：洗掉指定位置i處的元素并回傳被洗掉的元素
    public T remove(int i) {
        //創建一個結點，從頭節點開始
        Node node=head;
        //因為是從頭結點開始的，所以下面回圈會找到i位置的前一個結點
        for(int index=0;index<i;index++){
            node=node.next;
        }
        //i位置處的結點
        Node iNode=node.next;
        //直接讓i位置處的前以結點指向i位置的后一結點就可以洗掉i位置處的結點
        node.next=iNode.next;//或者也可以node.next=node.next.next;
        //元素減1
        N--;
        return iNode.item;
    }

查找元素t在鏈表中第一次出現的位置

//方法8：查找元素t在鏈表中第一次出現的位置
    public int indexOf(T t){
        Node node=head;
        for(int index=0;node.next!=null;index++){
            node=node.next;
            if(node.item.equals(t)){
                return index;
            }

        }
        //找不到
        return -1;
    }

提供一個遍歷的方法，實作Iterable介面

public class LinkList<T> implements Iterable{}

//實作Iterable介面，重寫iterator方法
    @Override
    //因為要的介面物件(介面不能直接new)，所以我們必須創建一個物件去實作這個介面
    public Iterator iterator() {
        return new LIterator()  ;
    }
    public class LIterator implements Iterator{
     //實作Iterator介面重寫hasNext()和next()兩個方法
        private Node n;
        public LIterator(){
            this.n=head;//從頭結點開始
        }
        @Override
        public boolean hasNext() {//是否有元素
            return n.next!=null;
        }

        @Override
        public Object next() {//回傳下一個元素
            n=n.next;
            return n.item;
        }
    }

全部代碼概覽：

import java.util.Iterator;

public class LinkList<T> implements Iterable{

    //定義節點類
    private class Node{
        //存盤資料
        T item;
        //下一個節點
        Node next;
        public Node(T item,Node next){
            this.item=item;
            this.next=next;
        }
    }
    //記錄頭節點
    private Node head;
    //記錄鏈表的長度
    private int N;
    //構造方法用來初始化成員變數
    public LinkList(){
        this.head=new Node(null,null);
        this.N=0;
    }
    //方法1：清空鏈表
    public void clear(){
        head.next=null;//將頭結點的指向置空
        this.N=0;//元素個數變為0
    }
    //方法2：鏈表的長度
    public int length(){
        return N;//N就是鏈表長度
    }
    //方法3：判斷鏈表是否為空
    public boolean isEmpty(){
        return this.N==0;//只需判斷N是否為0即可
    }
    //方法4：獲取指定位置處的元素
    public T get(int i){
             Node node=head.next;//node是下一個結點
          if(node!=null){//有下一個結點
            for(int index=0;index<i;index++){
                node=node.next;//往下一個結點移動
            }
            return node.item;
        }
        return null;
    }
    //方法5：插入元素t(在鏈表的最后以結點后插入元素)
    public void insert(T t){
        //創建一個結點
        Node node=head;
        while(node.next!=null){//找到最后一個結點的前一個結點
            node=node.next;
        }

        Node newLast=new Node(t, null);
        //之前的最后指向現在的最后結點
       node.next=newLast;
       //元素個數加一
        N++;
    }
    //方法6：在指定i處，添加元素t
    public void insert(int i,T t){
        //創建一個結點，從頭結點開始
        Node node =head;
        for(int index=0;index<i;index++){//找到i位置處的前一個元素
            node=node.next;
        }
        //當前i位置的結點
        Node oldNode=node.next;
        //創建結點t
        Node newNode=new Node(t, null);
        //此時node表示的還是前一個結點，所以只需要把前一個結點指向創建的新結點
        node.next=newNode;
        //新結點指向原來i位置處的結點，即可完成連接
        newNode.next=oldNode;
        //元素個數加一
        N++;
    }
    //方法7：洗掉指定位置i處的元素并回傳被洗掉的元素
    public T remove(int i) {
        //創建一個結點，從頭節點開始
        Node node=head;
        //因為是從頭結點開始的，所以下面回圈會找到i位置的前一個結點
        for(int index=0;index<i;index++){
            node=node.next;
        }
        //i位置處的結點
        Node iNode=node.next;
        //直接讓i位置處的前以結點指向i位置的后一結點就可以洗掉i位置處的結點
        node.next=iNode.next;//或者也可以node.next=node.next.next;
        //元素減1
        N--;
        return iNode.item;
    }
    //方法8：查找元素t在鏈表中第一次出現的位置
    public int indexOf(T t){
        Node node=head;
        for(int index=0;node.next!=null;index++){
            node=node.next;
            if(node.item.equals(t)){
                return index;
            }

        }
        //找不到
        return -1;
    }
    //實作Iterable介面，重寫iterator方法
    @Override
    //因為要的介面物件(介面不能直接new)，所以我們必須創建一個物件去實作這個介面
    public Iterator iterator() {
        return new LIterator()  ;
    }
    public class LIterator implements Iterator{
     //實作Iterator介面重寫hasNext()和next()兩個方法
        private Node n;
        public LIterator(){
            this.n=head;//從頭結點開始
        }
        @Override
        public boolean hasNext() {//是否有元素
            return n.next!=null;
        }

        @Override
        public Object next() {//回傳下一個元素
            n=n.next;
            return n.item;
        }
    }
}

測驗類下：

public class LinkListText {
    public static void main(String[] args) {
        //創建鏈表物件
        LinkList<String> list=new LinkList<String>();
        list.insert("張三");
        list.insert("李四");
        list.insert("王五");
        list.insert("李四");
        System.out.println("鏈表為空嗎："+list.isEmpty());
        for(Object s:list){
            System.out.println(s);
        }
        //元素個數
        System.out.println("初始元素個數："+list.length());
        System.out.println("----------------------");
        //插入
        list.insert(1,"趙六");
        list.insert(2,"歷七");
        //元素個數
        System.out.println("插入后元素個數:"+list.length());
       //第一次出現的位置
        System.out.println("張三第一次出現的位置:"+list.indexOf("張三"));
        System.out.println("----------------------");
        for(Object s:list){
        System.out.println(s);
    }
        //清除鏈表
        list.clear();
        System.out.println("清除后，鏈表為空嗎："+list.isEmpty());

    }
}