狠久操精品,9191精品在线,日本免费最新区

先聲明：我比較懶，所以沒有畫圖，不理解代碼的請自行百度或者查看相關書籍??

鏈表是最常用的一種數(shù)據(jù)結(jié)構(gòu)，作為線性表的一種，與數(shù)組相比，鏈表在插入修改操作多的環(huán)境中有著非常大的優(yōu)勢。下面我們用Java實現(xiàn)一個完整的鏈表。

鏈表是有多個節(jié)點構(gòu)成的，每個節(jié)點應當包含 數(shù)據(jù)域（用來存放數(shù)據(jù)）和 next指針（Java中是下一個節(jié)點的引用）兩部分。

在這里插入圖片描述

同時需要提供以下操作鏈表的方法：

初始化鏈表
判斷鏈表是否為空
清空鏈表
獲取第i個位置的元素
根據(jù)對應的值查找元素的位置
插入新元素（頭插法和尾插法）
刪除元素
獲取鏈表長度

分析完畢，下面開始實現(xiàn)~

public class LinkList {

}

節(jié)點

首先我們需要實現(xiàn)鏈表中用來存儲數(shù)據(jù)的節(jié)點結(jié)構(gòu)。我們使用一個靜態(tài)內(nèi)部類來表示節(jié)點，假設我們實現(xiàn)的鏈表是用來存取整形的數(shù)據(jù)。

代碼實現(xiàn)如下：

/**
     * 鏈表的節(jié)點
     */
    public static class Node{
        /**
         * 節(jié)點存儲的值
         */
        public int value;
        /**
         * 下一個節(jié)點
         */
        public Node next;
    }

操作

初始化鏈表

要想后邊使用鏈表，我們必須擁有一個指向鏈表頭部的引用，否則我們無法對其進行任何操作。這里我又添加了一個尾節(jié)點，為的是后面尾插法方便。我們再鏈表類的構(gòu)造方法中調(diào)用初始化方法，主要是用來初始化頭節(jié)點和尾節(jié)點。其中頭節(jié)點的next指向鏈表的第一個節(jié)點，尾節(jié)點指向鏈表的最后一個節(jié)點。

在這里插入圖片描述

代碼如下：
```
// 用來存儲鏈表的頭部
    private Node head;
    // 用來存儲鏈表的尾部
    private Node tail;

    public LinkList(){
        // 初始化鏈表
        initList();
    }

    /**
     * 初始化鏈表
     */
    public void initList(){
        // 創(chuàng)建頭節(jié)點 鏈表的第一個節(jié)點的引用將保存在head.next中
        head = new Node();
        head.value = 0;
        head.next = null;
        // 初始時沒有元素 尾節(jié)點指向頭節(jié)點
        tail = head;
    }
```

判斷鏈表是否為空

這個實現(xiàn)就比較簡單了，如果鏈表為空，那么我們頭節(jié)點的next引用一定時null，所以代碼實現(xiàn)如下：

在這里插入圖片描述
```
/**
     * 判斷鏈表是否為空
     * @return
     */
    public boolean isEmpty(){
        return head.next == null;
    }
```
清空鏈表

這個操作再C/C++中比較麻煩，但是用Java實現(xiàn)確實非常簡單，我們僅僅只需要把head節(jié)點next引用改為null即可，因為可以獲得這個鏈表的引用沒有，再GC的可達性分析中，這個鏈表被認為時不可達的，在GC時鏈表就會作為垃圾被從內(nèi)存中清除掉。所以，我們要做的僅僅是把head節(jié)點的next引用置為null。

在這里插入圖片描述
```
/**
     * 清空鏈表
     */
    public void clear(){
        head.next = null;
    }
```

獲取鏈表第i個位置的值

終于需要遍歷鏈表了??，我們需要一個計數(shù)器，用來記錄我們遍歷的位置，這一點與數(shù)組相比就比較難受了，數(shù)組因為在內(nèi)存中是連續(xù)存儲的，因此可以直接使用數(shù)組頭部的地址和每個元素的大小直接計算出需要查找元素的位置，而鏈表由于在內(nèi)存中不是連續(xù)存儲的，所以無法通過計算得出，只能是遍歷鏈表。因此在查詢比較多的場景中，數(shù)組更占優(yōu)勢。

在這里插入圖片描述

/**
     * 獲取第i個節(jié)點的元素
     * @param i
     * @return
     */
    public int getNode(int i){
        // 獲取第一個節(jié)點
        Node node = head.next;
        // 記錄遍歷到的索引
        int index = 0;
        // 遍歷
        while(node != null){
            // 找到對應的索引后返回節(jié)點存儲的值
            if(index == i){
                return node.value;
            }
            // 指向下一個節(jié)點
            node = node.next;
            index++;
        }
        // 遍歷完畢后還沒有找到，說明索引越界 返回-1
        return -1;
    }

獲取對應值的索引

這個實現(xiàn)與上面的思路就比較類似了，不在進行贅述，直接實現(xiàn)

/**
     * 獲取對應值的索引
     * @param value
     * @return
     */
    public int getIndex(int value){
        // 獲取第一個節(jié)點
        Node node = head.next;
        // 記錄索引
        int index = 0;
        while(node != null){
            // 將遍歷到節(jié)點的值與要查找的值比較
            if(node.value == value){
                return index;
            }
            node = node.next;
            index++;
        }
        return -1;
    }

插入元素

插入元素分為兩種，一種是尾插法，一種是頭插法。相比而言，尾插法比較簡單，我們先實現(xiàn)尾插法。

在這里插入圖片描述

/**
     * 尾部插入
     */
    public void tailInsert(int value){
        // 構(gòu)造節(jié)點
        Node node = new Node();
        node.value = value;
        node.next = null;
        if(isEmpty()){
            // 鏈表為空時，此時head節(jié)點指向為null
            // node會作為第一個元素，因此需要將head的next指向node
            head.next = node;
        }else{
            // 鏈表不為空時，head已經(jīng)指向鏈表的第一個元素了，只需要將尾節(jié)點的next指向新插入的節(jié)點即可
            tail.next = node;
        }
        // 更新尾節(jié)點
        tail = node;
    }

頭插法實現(xiàn)起來稍微復雜，因為head的next已經(jīng)指向了鏈表的第一個節(jié)點（鏈表不為空時），因為是頭插法，新插入的節(jié)點將會作為新的頭節(jié)點，因此，需要更新head的next指向新插入的節(jié)點，同時需要將新插入的節(jié)點的next指向原來的第一個節(jié)點，代碼實現(xiàn)如下：

在這里插入圖片描述

/**
     * 頭部插入法
     */
    public void headInsert(int value){
        // 構(gòu)造節(jié)點
        Node node = new Node();
        node.value = value;
        node.next = null;

        if(isEmpty()){
            // 鏈表為空時比較簡單，只需要將頭節(jié)點的next指向新插入的節(jié)點
            // 注意：需要更新尾節(jié)點
            head.next = node;
            tail = node;
        }else{
            // 鏈表不為空時，順序不能亂，不需要更新尾節(jié)點
            // 先將新節(jié)點的next指向原來的第一個節(jié)點
            node.next = head.next;
            // 再將頭節(jié)點的next指向新插入的節(jié)點
            head.next = node;
        }
    }

刪除第i個元素

這個要考慮的情況比較復雜，我直接寫在注釋上了，結(jié)合注釋看應該更加好

在這里插入圖片描述

/**
     * 刪除
     * @param i 要刪除的索引
     * @return 刪除元素的值
     */
    public int delete(int i){
        // 鏈表為空時返回-1
        if(isEmpty())return -1;
        // 遍歷的索引 這次從-1開始
        int index = -1;
        // 這次使用的時head 不是head的next，因為下面的遍歷包含刪除第一個節(jié)點的情況
        Node node = head;
        while(node != null){
            // 遍歷到刪除目標節(jié)點的前一個節(jié)點
            if( index == (i-1) ){
                // 獲取目標節(jié)點
                Node target = node.next;
                if(target == null){
                    // 如果要刪除的節(jié)點剛好越界 返回-1
                    return -1;
                }
                // 將目標節(jié)點上個節(jié)點的next引用直接修改為目標節(jié)點的next指向的節(jié)點
                // 可以理解為用下下個節(jié)點覆蓋下個節(jié)點
                node.next = node.next.next;
                if(target.next == null){
                    // 如果刪除的節(jié)點是尾節(jié)點 需要更新尾節(jié)點
                    tail = node;
                }
                // 成功刪除后返回刪除的值
                return target.value;
            }

            node = node.next;
            index++;
        }
        return -1;
    }

鏈表長度

這個實現(xiàn)的方式比較多，可以在鏈表類中添加一個記錄長度的字段len，在添加元素時len++，在刪除元素時len--，獲取鏈表長度的方法只需要返回這個字段的值即可。還有一種方法是遍歷鏈表時計數(shù)，這里實現(xiàn)的時第二種方法：
```
/**
     * 返回鏈表長度
     * @return
     */
    public int length(){
        int count = 0;
        Node node = head.next;
        while(node != null){
            count++;
            node = node.next;
        }
        return count;
    }
```

測試使用

為了方便測試，我在鏈表類中添加了一個展示的方法，可以遍歷輸出鏈表的所有元素，實現(xiàn)如下：

    public void display(){
        if(isEmpty())System.out.println("鏈表為空");
        Node node = head.next;
        while(node != null){
            System.out.print(node.value + "-");
            node = node.next;
        }
        System.out.println();
    }

下面使用我們自己實現(xiàn)的鏈表來完成測試

public class Test {
    public static void main(String[] args) {
        LinkList linkList = new LinkList();
        System.out.println("===初始化===");
        linkList.display();
        System.out.println("===尾插2 頭插1 尾插3 ===");
        linkList.tailInsert(2);
        linkList.headInsert(1);
        linkList.tailInsert(3);
        linkList.display();

        System.out.println("===獲取值為1的索引===");
        System.out.println(linkList.getIndex(1));
        System.out.println("===獲取索引為1的值===");
        System.out.println(linkList.getNode(1));

        System.out.println("===刪除索引為1的節(jié)點==");
        linkList.delete(1);
        linkList.display();

        System.out.println("===查看鏈表長度===");
        System.out.println(linkList.length());

        System.out.println("===清空鏈表===");
        linkList.clear();
        linkList.display();
       
    }
}

輸出如下：

===初始化===
鏈表為空

===尾插2 頭插1 尾插3 ===
1-2-3-
===獲取值為1的索引===
0
===獲取索引為1的值===
2
===刪除索引為1的節(jié)點==
1-3-
===查看鏈表長度===
2
===清空鏈表===
鏈表為空

這里只是實現(xiàn)了鏈表的基本操作，其他的諸如在指定位置插入元素等方法可以自行嘗試實現(xiàn)！

下面是完整的鏈表類代碼：

public class LinkList {
    
    /**
     * 鏈表的節(jié)點
     */
    public static class Node{
        /**
         * 節(jié)點存儲的值
         */
        public int value;
        /**
         * 下一個節(jié)點
         */
        public Node next;
    }

    // 用來存儲鏈表的頭部
    private Node head;
    // 用來存儲鏈表的尾部
    private Node tail;

    public LinkList(){
        // 初始化鏈表
        initList();
    }

    /**
     * 初始化鏈表
     */
    public void initList(){
        // 創(chuàng)建頭節(jié)點 鏈表的第一個節(jié)點的引用將保存在head.next中
        head = new Node();
        head.value = 0;
        head.next = null;
        // 初始時沒有元素 尾節(jié)點指向頭節(jié)點
        tail = head;
    }

    /**
     * 判斷鏈表是否為空
     * @return
     */
    public boolean isEmpty(){
        return head.next == null;
    }

    /**
     * 清空鏈表
     */
    public void clear(){
        head.next = null;
    }

    /**
     * 獲取第i個節(jié)點的元素
     * @param i
     * @return
     */
    public int getNode(int i){
        // 獲取第一個節(jié)點
        Node node = head.next;
        // 記錄遍歷到的索引
        int index = 0;
        // 遍歷
        while(node != null){
            // 找到對應的索引后返回節(jié)點存儲的值
            if(index == i){
                return node.value;
            }
            // 指向下一個節(jié)點
            node = node.next;
            index++;
        }
        // 遍歷完畢后還沒有找到，說明索引越界 返回-1
        return -1;
    }

    /**
     * 獲取對應值的索引
     * @param value
     * @return
     */
    public int getIndex(int value){
        // 獲取第一個節(jié)點
        Node node = head.next;
        // 記錄索引
        int index = 0;
        while(node != null){
            // 將遍歷到節(jié)點的值與要查找的值比較
            if(node.value == value){
                return index;
            }
            node = node.next;
            index++;
        }
        return -1;
    }
    /**
     * 尾部插入
     */
    public void tailInsert(int value){
        // 構(gòu)造節(jié)點
        Node node = new Node();
        node.value = value;
        node.next = null;
        if(isEmpty()){
            // 鏈表為空時，此時head節(jié)點指向為null
            // node會作為第一個元素，因此需要將head的next指向node
            head.next = node;
        }else{
            // 鏈表不為空時，head已經(jīng)指向鏈表的第一個元素了，只需要將尾節(jié)點的next指向新插入的節(jié)點即可
            tail.next = node;
        }
        // 更新尾節(jié)點
        tail = node;
    }
    
    /**
     * 頭部插入法
     */
    public void headInsert(int value){
        // 構(gòu)造節(jié)點
        Node node = new Node();
        node.value = value;
        node.next = null;

        if(isEmpty()){
            // 鏈表為空時比較簡單，只需要將頭節(jié)點的next指向新插入的節(jié)點
            // 注意：需要更新尾節(jié)點
            head.next = node;
            tail = node;
        }else{
            // 鏈表不為空時，順序不能亂，不需要更新尾節(jié)點
            // 先將新節(jié)點的next指向原來的第一個節(jié)點
            node.next = head.next;
            // 再將頭節(jié)點的next指向新插入的節(jié)點
            head.next = node;
        }
    }

    /**
     * 刪除
     * @param i 要刪除的索引
     * @return 刪除元素的值
     */
    public int delete(int i){
        // 鏈表為空時返回-1
        if(isEmpty())return -1;
        // 遍歷的索引 這次從-1開始
        int index = -1;
        // 這次使用的時head 不是head的next，因為下面的遍歷包含刪除第一個節(jié)點的情況
        Node node = head;
        while(node != null){
            // 遍歷到刪除目標節(jié)點的前一個節(jié)點
            if( index == (i-1) ){
                // 獲取目標節(jié)點
                Node target = node.next;
                if(target == null){
                    // 如果要刪除的節(jié)點剛好越界 返回-1
                    return -1;
                }
                // 將目標節(jié)點上個節(jié)點的next引用直接修改為目標節(jié)點的next指向的節(jié)點
                // 可以理解為用下下個節(jié)點覆蓋下個節(jié)點
                node.next = node.next.next;
                if(target.next == null){
                    // 如果刪除的節(jié)點是尾節(jié)點 需要更新尾節(jié)點
                    tail = node;
                }
                // 成功刪除后返回刪除的值
                return target.value;
            }

            node = node.next;
            index++;
        }
        return -1;
    }

    /**
     * 返回鏈表長度
     * @return
     */
    public int length(){
        int count = 0;
        Node node = head.next;
        while(node != null){
            count++;
            node = node.next;
        }
        return count;
    }

    public void display(){
        if(isEmpty())System.out.println("鏈表為空");
        Node node = head.next;
        while(node != null){
            System.out.print(node.value + "-");
            node = node.next;
        }
        System.out.println();
    }

    


}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

花10分鐘用Java來自己實現(xiàn)鏈表吧（圖解）

花10分鐘用Java來自己實現(xiàn)鏈表吧（圖解）

節(jié)點

操作

測試使用

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

花10分鐘用Java來自己實現(xiàn)鏈表吧（圖解）

節(jié)點

操作

測試使用

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av