各位讀者朋友們，

從今天開始，我將通過(guò)博文的形式，概述數(shù)據(jù)結(jié)構(gòu)中應(yīng)知必會(huì)的基本算法，

由于我更加熟悉 Java 語(yǔ)言，所以全程使用 Java 語(yǔ)言進(jìn)行敘述，

如果您發(fā)現(xiàn)了文章中的錯(cuò)誤，請(qǐng)您不吝賜教。

?什么是鏈表？

????????“鏈表”（Linked List）是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)和組織數(shù)據(jù)。它是由一系列節(jié)點(diǎn)（Node）組成的，每個(gè)節(jié)點(diǎn)包含兩部分：數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的引用（或指針）。每個(gè)節(jié)點(diǎn)中的數(shù)據(jù)可以是任意類型的數(shù)據(jù)，例如整數(shù)、字符、對(duì)象等。

????????鏈表中的節(jié)點(diǎn)通過(guò)指針相互連接，形成一個(gè)線性序列。與數(shù)組不同，鏈表的節(jié)點(diǎn)在內(nèi)存中可以不連續(xù)存儲(chǔ)，因?yàn)槊總€(gè)節(jié)點(diǎn)都包含指向下一個(gè)節(jié)點(diǎn)的指針，這使得鏈表具有動(dòng)態(tài)分配內(nèi)存的特性。

????????鏈表的主要特點(diǎn)是插入和刪除操作的高效性。在鏈表中插入或刪除節(jié)點(diǎn)時(shí)，只需要調(diào)整節(jié)點(diǎn)的指針，而不需要移動(dòng)其他節(jié)點(diǎn)，這使得鏈表在頻繁插入和刪除操作時(shí)比數(shù)組更加高效。

鏈表的類型？

????????常見(jiàn)的鏈表類型有單向鏈表和雙向鏈表：

• 單向鏈表（Singly Linked List）：每個(gè)節(jié)點(diǎn)只包含一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針。它的優(yōu)點(diǎn)是節(jié)點(diǎn)占用的內(nèi)存空間較小，但缺點(diǎn)是無(wú)法直接反向遍歷鏈表。

• 雙向鏈表（Doubly Linked List）：每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)指向前一個(gè)節(jié)點(diǎn)。這樣可以實(shí)現(xiàn)雙向遍歷鏈表，但相應(yīng)地，每個(gè)節(jié)點(diǎn)需要更多的內(nèi)存空間來(lái)存儲(chǔ)額外的指針。

單向鏈表的構(gòu)建？?

????????首先進(jìn)行逐步分解，最后會(huì)給出完整代碼。節(jié)點(diǎn)的構(gòu)造如下：

static class Node { // 靜態(tài)內(nèi)部類
    public int val;
    public Node next;

    Node(int x) { // 有參構(gòu)造器
        val = x;
        next = null;
    }
}

????????在堆內(nèi)存中新建節(jié)點(diǎn)時(shí)，使用的是如下代碼：

for (int i = 0; i < array.length; i++) {
    Node newNode = new Node(array[i]);
}

? ? ? ? 由上述代碼我們可以看出，每一次 for 循環(huán)都會(huì)產(chǎn)生一個(gè)新的 Node 類對(duì)象，此前存在棧中的 newNode 對(duì)象，一旦沒(méi)有被引用，就會(huì)被 JVM 回收，所以在這里我們需要定義兩個(gè) Node 類 “指針” 對(duì)象，這里分別命名為 head 和 cur，head 對(duì)象作為頭結(jié)點(diǎn)“指針”，持續(xù)指向頭結(jié)點(diǎn)，而 cur 對(duì)象是為了保證新建的節(jié)點(diǎn)一直有被引用，不被 JVM 回收，代碼及演示如下：

? ? ? ? （演示是為了更容易理解，當(dāng)值被賦予 null 時(shí)，在內(nèi)存中其實(shí)沒(méi)有指向關(guān)系）

Node head = null, cur = null;

? ? ? ? ?接下來(lái)創(chuàng)建第一個(gè) Node 節(jié)點(diǎn)，并改變“指針”的指向關(guān)系：

Node newNode = new Node(array[i]);
head = newNode;
cur = newNode;

? ? ? ? 此時(shí)，newNode 臨時(shí)對(duì)象的任務(wù)就完成了，可以創(chuàng)建第二個(gè)節(jié)點(diǎn)了。由于 head 對(duì)象已經(jīng)指向了頭結(jié)點(diǎn)，所以后續(xù)該對(duì)象指向?qū)ο缶筒粫?huì)再變化。而 cur 對(duì)象需要操作第一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向第二個(gè)節(jié)點(diǎn)的地址，代碼實(shí)現(xiàn)及演示如下：

Node newNode = new Node(array[i]);
cur.next = newNode;

? ? ? ? 第一個(gè)節(jié)點(diǎn)已經(jīng)配置完成，cur 可以指向第二個(gè)節(jié)點(diǎn)了，之后臨時(shí)變量 newNode 繼續(xù)彈棧、建立第三個(gè)節(jié)點(diǎn)、以此往復(fù)，直到循環(huán)結(jié)束：

cur = newNode;
Node newNode = new Node(array[i]);

? ? ? ? 隨著此步驟的不斷循環(huán)，最終就會(huì)建立一個(gè)鏈表，我們?cè)?IDEA 中調(diào)試，可以發(fā)現(xiàn)這種鏈?zhǔn)浇Y(jié)構(gòu)：?

? ? ? ? ?最后，給出完整代碼：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-602988.html

public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 5, 6};
    Node head = initLinkedList(a);
    System.out.println(head);
}

private static Node initLinkedList(int[] array) {
    Node head = null, cur = null;
    for (int i = 0; i < array.length; i++) {
        Node newNode = new Node(array[i]);
//      newNode.next = null;
        if (i == 0) {
            head = newNode;
            cur = newNode;
        } else {
            cur.next = newNode;
            cur = newNode;
        }
    }
    return head;
}

static class Node { // 靜態(tài)內(nèi)部類
    public int val;
    public Node next;

    Node(int x) {
        val = x;
        next = null;
    }
}

到了這里，關(guān)于[算法通關(guān)村] 1.1 單向鏈表的創(chuàng)建的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！