Java實(shí)現(xiàn)單向鏈表基本功能

idisfkj 發(fā)布于2019-08-16 11:10 / 2660人閱讀

摘要：一前言最近在回顧數(shù)據(jù)結(jié)構(gòu)與算法，有部分的算法題用到了棧的思想，說起棧又不得不說鏈表了。

一、前言

最近在回顧數(shù)據(jù)結(jié)構(gòu)與算法，有部分的算法題用到了棧的思想，說起棧又不得不說鏈表了。數(shù)組和鏈表都是線性存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)，棧和隊(duì)列都是線性存儲(chǔ)結(jié)構(gòu)的應(yīng)用～

本文主要講解單鏈表的基礎(chǔ)知識(shí)點(diǎn)，做一個(gè)簡(jiǎn)單的入門～如果有錯(cuò)的地方請(qǐng)指正

二、回顧與知新

說起鏈表，我們先提一下數(shù)組吧，跟數(shù)組比較一下就很理解鏈表這種存儲(chǔ)結(jié)構(gòu)了。

2.1回顧數(shù)組

數(shù)組我們無論是C、Java都會(huì)學(xué)過：

數(shù)組是一種連續(xù)存儲(chǔ)線性結(jié)構(gòu)，元素類型相同，大小相等

數(shù)組的優(yōu)點(diǎn)：

存取速度快

數(shù)組的缺點(diǎn)：

事先必須知道數(shù)組的長度

插入刪除元素很慢

空間通常是有限制的

需要大塊連續(xù)的內(nèi)存塊

插入刪除元素的效率很低

2.2鏈表說明

看完了數(shù)組，回到我們的鏈表：

鏈表是離散存儲(chǔ)線性結(jié)構(gòu)

n個(gè)節(jié)點(diǎn)離散分配，彼此通過指針相連，每個(gè)節(jié)點(diǎn)只有一個(gè)前驅(qū)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)只有一個(gè)后續(xù)節(jié)點(diǎn)，首節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)，尾節(jié)點(diǎn)沒有后續(xù)節(jié)點(diǎn)。

鏈表優(yōu)點(diǎn)：

空間沒有限制

插入刪除元素很快

鏈表缺點(diǎn)：

存取速度很慢

鏈表相關(guān)術(shù)語介紹，我還是通過上面那個(gè)圖來說明吧：

確定一個(gè)鏈表我們只需要頭指針，通過頭指針就可以把整個(gè)鏈表都能推導(dǎo)出來了～

鏈表又分了好幾類：

單向鏈表

一個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)

雙向鏈表

一個(gè)節(jié)點(diǎn)有兩個(gè)指針域

循環(huán)鏈表

能通過任何一個(gè)節(jié)點(diǎn)找到其他所有的節(jié)點(diǎn)，將兩種(雙向/單向)鏈表的最后一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)從而實(shí)現(xiàn)循環(huán)

操作鏈表要時(shí)刻記住的是：

節(jié)點(diǎn)中指針域指向的就是一個(gè)節(jié)點(diǎn)了！

三、Java實(shí)現(xiàn)鏈表

算法：

遍歷

查找

清空

銷毀

求長度

排序

刪除節(jié)點(diǎn)

插入節(jié)點(diǎn)

ps：我將head節(jié)點(diǎn)定義在成員變量上：

 private static Node head = new Node();

首先，我們定義一個(gè)類作為節(jié)點(diǎn)

數(shù)據(jù)域

指針域

為了操作方便我就直接定義成public了。

public class Node {

    //數(shù)據(jù)域
    public Integer data;
    
    //指針域，指向下一個(gè)節(jié)點(diǎn)
    public Node next;

    public Node() {
    }

    public Node(int data) {
        this.data = data;
    }

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
}

3.1創(chuàng)建鏈表(增加節(jié)點(diǎn))

向鏈表中插入數(shù)據(jù)：

找到尾節(jié)點(diǎn)進(jìn)行插入

即使頭節(jié)點(diǎn).next為null，不走while循環(huán)，也是將頭節(jié)點(diǎn)與新節(jié)點(diǎn)連接的(我已經(jīng)將head節(jié)點(diǎn)初始化過了，因此沒必要判斷頭節(jié)點(diǎn)是否為null)～

    /**
     * 向鏈表添加數(shù)據(jù)
     *
     * @param value 要添加的數(shù)據(jù)
     */
    public static void addData(int value) {

        //初始化要加入的節(jié)點(diǎn)
        Node newNode = new Node(value);

        //臨時(shí)節(jié)點(diǎn)
        Node temp = head;

        // 找到尾節(jié)點(diǎn)
        while (temp.next != null) {
            temp = temp.next;
        }

        // 已經(jīng)包括了頭節(jié)點(diǎn).next為null的情況了～
        temp.next = newNode;

    }

3.2遍歷鏈表

上面我們已經(jīng)編寫了增加方法，現(xiàn)在遍歷一下看一下是否正確～～～

從首節(jié)點(diǎn)開始，不斷往后面找，直到后面的節(jié)點(diǎn)沒有數(shù)據(jù)：

    /**
     * 遍歷鏈表
     *
     * @param head 頭節(jié)點(diǎn)
     */
    public static void traverse(Node head) {

        
        //臨時(shí)節(jié)點(diǎn)，從首節(jié)點(diǎn)開始
        Node temp = head.next;

        while (temp != null) {

            if (temp.data != null) {
                System.out.println("關(guān)注公眾號(hào)Java3y：" + temp.data);
            }

            //繼續(xù)下一個(gè)
            temp = temp.next;
        }
    }

結(jié)果：

3.3插入節(jié)點(diǎn)

插入一個(gè)節(jié)點(diǎn)到鏈表中，首先得判斷這個(gè)位置是否是合法的，才能進(jìn)行插入～

找到想要插入的位置的上一個(gè)節(jié)點(diǎn)就可以了～

    /**
     * 插入節(jié)點(diǎn)
     *
     * @param head  頭指針
     * @param index 要插入的位置
     * @param value 要插入的值
     */
    public static void insertNode(Node head, int index, int value) {


        //首先需要判斷指定位置是否合法，
        if (index < 1 || index > linkListLength(head) + 1) {
            System.out.println("插入位置不合法。");
            return;
        }

        //臨時(shí)節(jié)點(diǎn)，從頭節(jié)點(diǎn)開始
        Node temp = head;

        //記錄遍歷的當(dāng)前位置
        int currentPos = 0;

        //初始化要插入的節(jié)點(diǎn)
        Node insertNode = new Node(value);

        while (temp.next != null) {

            //找到上一個(gè)節(jié)點(diǎn)的位置了
            if ((index - 1) == currentPos) {

                //temp表示的是上一個(gè)節(jié)點(diǎn)

                //將原本由上一個(gè)節(jié)點(diǎn)的指向交由插入的節(jié)點(diǎn)來指向
                insertNode.next = temp.next;

                //將上一個(gè)節(jié)點(diǎn)的指針域指向要插入的節(jié)點(diǎn)
                temp.next = insertNode;

                return;

            }

            currentPos++;
            temp = temp.next;
        }

    }

3.4獲取鏈表的長度

獲取鏈表的長度就很簡(jiǎn)單了，遍歷一下，每得到一個(gè)節(jié)點(diǎn)+1即可～

    /**
     * 獲取鏈表的長度
     * @param head 頭指針
     */
    public static int  linkListLength(Node head) {

        int length = 0;

        //臨時(shí)節(jié)點(diǎn)，從首節(jié)點(diǎn)開始
        Node temp = head.next;

        // 找到尾節(jié)點(diǎn)
        while (temp != null) {
            length++;
            temp = temp.next;
        }

        return length;
    }

3.5刪除節(jié)點(diǎn)

刪除某個(gè)位置上的節(jié)點(diǎn)其實(shí)是和插入節(jié)點(diǎn)很像的，同樣都要找到上一個(gè)節(jié)點(diǎn)。將上一個(gè)節(jié)點(diǎn)的指針域改變一下，就可以刪除了～

    /**
     * 根據(jù)位置刪除節(jié)點(diǎn)
     *
     * @param head  頭指針
     * @param index 要?jiǎng)h除的位置
     */
    public static void deleteNode(Node head, int index) {


        //首先需要判斷指定位置是否合法，
        if (index < 1 || index > linkListLength(head) + 1) {
            System.out.println("刪除位置不合法。");
            return;
        }

        //臨時(shí)節(jié)點(diǎn)，從頭節(jié)點(diǎn)開始
        Node temp = head;

        //記錄遍歷的當(dāng)前位置
        int currentPos = 0;


        while (temp.next != null) {

            //找到上一個(gè)節(jié)點(diǎn)的位置了
            if ((index - 1) == currentPos) {

                //temp表示的是上一個(gè)節(jié)點(diǎn)

                //temp.next表示的是想要?jiǎng)h除的節(jié)點(diǎn)

                //將想要?jiǎng)h除的節(jié)點(diǎn)存儲(chǔ)一下
                Node deleteNode = temp.next;

                //想要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)交由上一個(gè)節(jié)點(diǎn)來控制
                temp.next = deleteNode.next;


                //Java會(huì)回收它，設(shè)置不設(shè)置為null應(yīng)該沒多大意義了(個(gè)人覺得,如果不對(duì)請(qǐng)指出哦～)
                deleteNode = null;

                return;

            }
            currentPos++;
            temp = temp.next;
        }
    }

3.6對(duì)鏈表進(jìn)行排序

前面已經(jīng)講過了8種的排序算法了【八種排序算法總結(jié)】，這次挑簡(jiǎn)單的冒泡排序吧(其實(shí)我是想寫快速排序的，嘗試了一下感覺有點(diǎn)難.....)

    /**
     * 對(duì)鏈表進(jìn)行排序
     *
     * @param head
     *
     */
    public static void sortLinkList(Node head) {


        Node currentNode;

        Node nextNode;

        for (currentNode = head.next; currentNode.next != null; currentNode = currentNode.next) {

            for (nextNode = head.next; nextNode.next != null; nextNode = nextNode.next) {


                if (nextNode.data > nextNode.next.data) {

                    int temp = nextNode.data;
                    nextNode.data = nextNode.next.data;

                    nextNode.next.data = temp;

                }
            }


        }
    }

3.7找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

這個(gè)算法挺有趣的：設(shè)置兩個(gè)指針p1、p2，讓p2比p1快k個(gè)節(jié)點(diǎn)，同時(shí)向后遍歷，當(dāng)p2為空，則p1為倒數(shù)第k個(gè)節(jié)點(diǎn)

    /**
     * 找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)(設(shè)置兩個(gè)指針p1、p2，讓p2比p1快k個(gè)節(jié)點(diǎn)，同時(shí)向后遍歷，當(dāng)p2為空，則p1為倒數(shù)第k個(gè)節(jié)點(diǎn)
     *
     * @param head
     * @param k    倒數(shù)第k個(gè)節(jié)點(diǎn)
     */
    public static Node findKNode(Node head, int k) {

        if (k < 1 || k > linkListLength(head))
            return null;
        Node p1 = head;
        Node p2 = head;

        // p2比怕p1快k個(gè)節(jié)點(diǎn)
        for (int i = 0; i < k - 1; i++)
            p2 = p2.next;


        // 只要p2為null，那么p1就是倒數(shù)第k個(gè)節(jié)點(diǎn)了
        while (p2.next != null) {

            p2 = p2.next;
            p1 = p1.next;
        }
        return p1;


    }

3.8刪除鏈表重復(fù)數(shù)據(jù)

這里之前有問題，大家可以到：https://blog.csdn.net/ifollow...

進(jìn)行參考

3.9查詢鏈表的中間節(jié)點(diǎn)

這個(gè)算法也挺有趣的：一個(gè)每次走1步，一個(gè)每次走兩步，走兩步的遍歷完，然后走一步的指針，那就是中間節(jié)點(diǎn)

    /**
     * 查詢單鏈表的中間節(jié)點(diǎn)
     */

    public static Node searchMid(Node head) {

        Node p1 = head;
        Node p2 = head;


        // 一個(gè)走一步，一個(gè)走兩步，直到為null，走一步的到達(dá)的就是中間節(jié)點(diǎn)
        while (p2 != null && p2.next != null && p2.next.next != null) {

            p1 = p1.next;
            p2 = p2.next.next;

        }

        return p1;


    }

3.10通過遞歸從尾到頭輸出單鏈表

    /**
     * 通過遞歸從尾到頭輸出單鏈表
     *
     * @param head 頭節(jié)點(diǎn)
     */
    public  static  void printListReversely(Node head) {
        if (head != null) {
            printListReversely(head.next);
            if (head.data != null) {
                System.out.println(head.data);
            }
        }
    }

3.11反轉(zhuǎn)鏈表

 /**
     * 實(shí)現(xiàn)鏈表的反轉(zhuǎn)
     *
     * @param head 鏈表的頭節(jié)點(diǎn)
     */
    public static Node reverseList(Node head) {

        Node pre = null;
        Node cur = head;
        while (cur != null) {
            Node next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
  // 翻轉(zhuǎn)完，使用下面的代碼進(jìn)行遍歷吧：
  public static void traverse4Reverse(Node head) {

        //臨時(shí)節(jié)點(diǎn)，從首節(jié)點(diǎn)開始
        Node temp = head;

        while (temp != null) {

            if (temp.data != null) {
                System.out.println("關(guān)注公眾號(hào)Java3y：" + temp.data);
            }

            //繼續(xù)下一個(gè)
            temp = temp.next;
        }
    }

反轉(zhuǎn)鏈表參考自：

http://www.cnblogs.com/hanxue112253/p/8533426.html

四、最后

理解鏈表本身并不難，但做相關(guān)的操作就弄得頭疼，head.next  next next next ....(算法這方面我還是薄弱啊..腦子不夠用了.....)寫了兩天就寫了這么點(diǎn)東西...

操作一個(gè)鏈表只需要知道它的頭指針就可以做任何操作了

添加數(shù)據(jù)到鏈表中

遍歷找到尾節(jié)點(diǎn)，插入即可(只要while(temp.next != null)，退出循環(huán)就會(huì)找到尾節(jié)點(diǎn))

遍歷鏈表

從首節(jié)點(diǎn)(有效節(jié)點(diǎn))開始，只要不為null，就輸出

給定位置插入節(jié)點(diǎn)到鏈表中

首先判斷該位置是否有效(在鏈表長度的范圍內(nèi))

找到想要插入位置的上一個(gè)節(jié)點(diǎn)

將原本由上一個(gè)節(jié)點(diǎn)的指向交由插入的節(jié)點(diǎn)來指向

上一個(gè)節(jié)點(diǎn)指針域指向想要插入的節(jié)點(diǎn)

獲取鏈表的長度

每訪問一次節(jié)點(diǎn)，變量++操作即可

刪除給定位置的節(jié)點(diǎn)

首先判斷該位置是否有效(在鏈表長度的范圍內(nèi))

找到想要插入位置的上一個(gè)節(jié)點(diǎn)

將原本由上一個(gè)節(jié)點(diǎn)的指向后面一個(gè)節(jié)點(diǎn)

對(duì)鏈表進(jìn)行排序

使用冒泡算法對(duì)其進(jìn)行排序

找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

設(shè)置兩個(gè)指針p1、p2，讓p2比p1快k個(gè)節(jié)點(diǎn)，同時(shí)向后遍歷，當(dāng)p2為空，則p1為倒數(shù)第k個(gè)節(jié)點(diǎn)

刪除鏈表重復(fù)數(shù)據(jù)

操作跟冒泡排序差不多，只要它相等，就能刪除了～

查詢鏈表的中間節(jié)點(diǎn)

這個(gè)算法也挺有趣的：一個(gè)每次走1步，一個(gè)每次走兩步，走兩步的遍歷完，然后走一步的指針，那就是中間節(jié)點(diǎn)

遞歸從尾到頭輸出單鏈表

只要下面還有數(shù)據(jù)，那就往下找，遞歸是從最后往前翻。

反轉(zhuǎn)鏈表

有遞歸和非遞歸兩種方式，我覺得是挺難的。可以到我給出的鏈接上查閱～

PS：每個(gè)人的實(shí)現(xiàn)都會(huì)不一樣，所以一些小細(xì)節(jié)難免會(huì)有些變動(dòng)，也沒有固定的寫法，能夠?qū)崿F(xiàn)對(duì)應(yīng)的功能即可～

參考資料：

http://www.cnblogs.com/whgk/p/6589920.html

https://www.cnblogs.com/bywallance/p/6726251.html

如果文章有錯(cuò)的地方歡迎指正，大家互相交流。習(xí)慣在微信看技術(shù)文章，想要獲取更多的Java資源的同學(xué)，可以關(guān)注微信公眾號(hào):Java3y

GPU云服務(wù)器云服務(wù)器單向鏈表詳解 java實(shí)現(xiàn)鏈表插入單向鏈表的操作c語言簽到功能java實(shí)現(xiàn)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/71055.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

idisfkj

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

tensorflow.compat

閱讀 1445·2023-04-25 15:21
寶塔linux怎么修改php.ini?怎么編輯寶塔linux面板php.ini文件

閱讀 2759·2021-11-24 10:23
IBM 為 Linux 內(nèi)核提出新的命名空間機(jī)制

閱讀 3459·2021-10-11 10:59
【51單片機(jī)】??萬物互聯(lián)??一招搞定單片機(jī)（持續(xù)更新中......）

閱讀 3321·2021-09-03 10:28
【譯】三分鐘掌握 React 高階組件

閱讀 1788·2019-08-26 13:45
腳本化HTTP 取得響應(yīng) 指定請(qǐng)求

閱讀 2387·2019-08-26 12:11
手動(dòng)實(shí)現(xiàn)bind函數(shù)（附MDN提供的Polyfill方案解析）

閱讀 986·2019-08-26 12:00
html界面構(gòu)建，react - Hook基礎(chǔ)：useState、useEffect簡(jiǎn)述

閱讀 1772·2019-08-26 10:44

亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

Java實(shí)現(xiàn)單向鏈表基本功能

相關(guān)文章

List集合就這么簡(jiǎn)單【源碼剖析】

Java技術(shù)面試“小抄”——集合類（實(shí)時(shí)更新）

**近期Java高級(jí)工程師面試總結(jié)**

**學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（二）：鏈表**

發(fā)表評(píng)論

0條評(píng)論

idisfkj

男|高級(jí)講師

TA的文章

tensorflow.compat

寶塔linux怎么修改php.ini?怎么編輯寶塔linux面板php.ini文件

IBM 為 Linux 內(nèi)核提出新的命名空間機(jī)制

【51單片機(jī)】??萬物互聯(lián)??一招搞定單片機(jī)（持續(xù)更新中......）

【譯】三分鐘掌握 React 高階組件

腳本化HTTP 取得響應(yīng) 指定請(qǐng)求

手動(dòng)實(shí)現(xiàn)bind函數(shù)（附MDN提供的Polyfill方案解析）

html界面構(gòu)建，react - Hook基礎(chǔ)：useState、useEffect簡(jiǎn)述

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

Java實(shí)現(xiàn)單向鏈表基本功能

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！