一、鏈表 

1. 概念

鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的引用鏈接次序?qū)崿F(xiàn)的

上章介紹到順序表適合用作查詢(xún)和修改，而不適合用作插入和刪除。并且它增容時(shí)容易造成空間浪費(fèi)。而鏈表則具有以下的特點(diǎn)

適合用作插入和刪除隨用隨取，避免了空間的浪費(fèi)不適合用作查詢(xún)和修改 

2. 結(jié)構(gòu)

鏈表其實(shí)可以想象成一條被打了一些結(jié)的繩子

而實(shí)際上，鏈表就是由一個(gè)個(gè)節(jié)點(diǎn)構(gòu)成的，只不過(guò)每個(gè)節(jié)點(diǎn)一般有兩個(gè)域

數(shù)值域 data： 里面存儲(chǔ)數(shù)據(jù)

next 域： 里面存儲(chǔ)的是下一個(gè)節(jié)點(diǎn)的地址（是引用變量）

其中

尾節(jié)點(diǎn)： 當(dāng)這個(gè)節(jié)點(diǎn)的 next 域?yàn)?null 時(shí)，該節(jié)點(diǎn)就是尾節(jié)點(diǎn)

頭節(jié)點(diǎn)： 整個(gè)鏈表的第一個(gè)節(jié)點(diǎn)就是頭節(jié)點(diǎn)

實(shí)際中的鏈表結(jié)構(gòu)非常多，通過(guò)以下的情況的組合可以有8種鏈表的結(jié)構(gòu)（比如帶頭單向循環(huán)鏈表就是一種）

單向、雙向

帶頭節(jié)點(diǎn)、不帶頭

節(jié)點(diǎn)循環(huán)、非循環(huán)

而上圖所示，就是一個(gè)單向不帶頭非循環(huán)鏈表。

可能有人會(huì)疑問(wèn)，上述圖片中不是存在頭節(jié)點(diǎn)嗎？那為啥它又是一個(gè)不帶頭節(jié)點(diǎn)的鏈表呢？我將上述圖片實(shí)例稍稍改一下就是帶頭節(jié)點(diǎn)的了

我在原有的頭節(jié)點(diǎn)前面又多了一個(gè)節(jié)點(diǎn)，并且這個(gè)節(jié)點(diǎn)的數(shù)值域里面的數(shù)據(jù)可有可無(wú)，因?yàn)閷?duì)其沒(méi)有影響。而這里面的頭節(jié)點(diǎn)只是一個(gè)標(biāo)志，標(biāo)識(shí)這個(gè)節(jié)點(diǎn)是該鏈表的頭

那帶頭節(jié)點(diǎn)的和不帶頭結(jié)點(diǎn)的鏈表有啥差別呢？

不帶頭： 這個(gè)鏈表的頭節(jié)點(diǎn)可能發(fā)生改

變帶頭： 這個(gè)鏈表的頭節(jié)點(diǎn)不會(huì)發(fā)生改變

那循環(huán)鏈表又是啥樣的呢？我們可以將上述單向不帶頭非循環(huán)鏈表稍微修改一下

即將尾節(jié)點(diǎn)的 next 域存儲(chǔ)了頭節(jié)點(diǎn)的地址

我們知道一個(gè)節(jié)點(diǎn)一般就兩個(gè)域，但如果是雙向鏈表，則就有三個(gè)域了

數(shù)值域 data： 里面存儲(chǔ)數(shù)據(jù)

next 域： 里面存儲(chǔ)的是下一個(gè)節(jié)點(diǎn)的地址（是引用變量）

prev 域： 里面存儲(chǔ)的是上一個(gè)節(jié)點(diǎn)的地址（是引用變量）

我們畫(huà)一個(gè)不帶頭雙向非循環(huán)鏈表就是這樣的

接下來(lái)我將主要介紹單向不帶頭非循環(huán)鏈表和雙向不帶頭非循環(huán)鏈表，這兩種鏈表也是經(jīng)常出現(xiàn)在面試題中的

二、單向不帶頭非循環(huán)鏈表 

1. 概念及結(jié)構(gòu)

上述通過(guò)圖解，大家應(yīng)該對(duì)單向不帶頭非循環(huán)鏈表應(yīng)該有了了解。那么代碼中該怎么實(shí)現(xiàn)呢？

我們知道，鏈表應(yīng)該可以看作一個(gè)類(lèi)，而節(jié)點(diǎn)本身其實(shí)也可以抽象的看作成一個(gè)類(lèi)

首先對(duì)于節(jié)點(diǎn)類(lèi)，代碼可以寫(xiě)出這樣

class Node{
    public int val;
    public Node next;
    public Node(int val){
        this.val=val;
    }
}

先定義了數(shù)值域，再定義了 next 域（由于 next 存儲(chǔ)的是下一個(gè)節(jié)點(diǎn)的地址，故寫(xiě)出上述那樣）。而我們初始時(shí)可以知道 val，所以可以寫(xiě)個(gè)構(gòu)造函數(shù)對(duì) val 進(jìn)行初始化，而該節(jié)點(diǎn)的 next 域初始時(shí)是不可能知道的，所以不對(duì) next 做初始化

如果創(chuàng)造一個(gè) Node 對(duì)象就可以寫(xiě)出

Node node = new Node(10);

即頭節(jié)點(diǎn)的數(shù)值域?yàn)?0。

再定義鏈表類(lèi)，代碼可以寫(xiě)成這樣

public class MyLinkedList {
    public Node head;
}

我們定義了一個(gè)頭節(jié)點(diǎn)，這是我們很容易發(fā)現(xiàn)的，就比如我要對(duì)該鏈表進(jìn)行頭插，則該鏈表的頭節(jié)點(diǎn)一直都在改變。所以寫(xiě)上述的代碼就是為了標(biāo)識(shí)單鏈表的頭節(jié)點(diǎn)。

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

接下來(lái)我們來(lái)實(shí)現(xiàn)單向不帶頭非循環(huán)鏈表的一些操作

打印鏈表

public void display(){
    Node cur =this.head;
    while(cur!=null){
        System.out.print(cur.val + " ");
        cur=cur.next;
    }
    System.out.println();
}

求鏈表的長(zhǎng)度

public int size(){
    Node cur=this.head;
    int count=0;
    while(cur!=null){
        count++;
        cur=cur.next;
    }
    return count;
}

查找值 key 是否在單鏈表中

public boolean contains(int key){
    Node cur=this.head;
    while(cur!=null){
        if(key==cur.val){
            return true;
        }
        cur=cur.next;
    }
    return false;
}

清除單鏈表

public void clear(){
    this.head.val=0;
    this.head.next=null;
}

頭插法

public void addFirst(int data){
    Node node=new Node(data);
    if(head==null){
        this.head=node;
    }else {
        node.next = this.head;
        this.head = node;
    }
}

尾插法

public void addLast(int data){
    Node node = new Node(data);
    if(this.head==null){
        this.head=node;
    }else {
        Node cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
}

通過(guò)下標(biāo)找到前驅(qū)節(jié)點(diǎn)（第一個(gè)節(jié)點(diǎn)下標(biāo)為0）

public Node searchPrev(int index){
    Node cur = this.head;
    int count=0;
    while(count!=index-1){
        cur=cur.next;
        count++;
    }
    return cur;
}

任意位置插入

public void addIndex(int index, int data){
    if(index<0 || index>size()){
        throw new RuntimeException("index 不合法");
    }
    if(index==0){
        addFirst(data);
        return;
    }
    if(index==size()) {
        addLast(data);
        return;
    }
    Node node =new Node(data);
    Node cur =searchPrev(index);
    node.next=cur.next;
    cur.next=node;
}

通過(guò)值 key 找到前驅(qū)節(jié)點(diǎn)（第一個(gè)節(jié)點(diǎn)下標(biāo)為0）

public Node searchPrevNode(int key){
    Node cur = this.head;
    while(cur.next!=null){
        if(cur.next.val==key) {
            return cur;
        }
        cur=cur.next;
    }
    return null;
}

刪除第一次出現(xiàn)的值為 key 的節(jié)點(diǎn)

public void remove(int key){
    if(this.head==null){
        return;
    }
    if(key==this.head.val){
        this.head=this.head.next;
        return;
    }
    Node node = searchPrevNode(key);
    if(node==null){
        System.out.println("鏈表中無(wú)要?jiǎng)h除的元素");
    }else {
        node.next = node.next.next;
    }
}

刪除所有出現(xiàn)的值為 key 的節(jié)點(diǎn)

public void removeAllKey(int key){
    if(this.head==null){
        return;
    }
    Node prev=this.head;
    Node cur=this.head.next;
    while(cur!=null){
        if(cur.val==key){
            cur=cur.next;
            prev.next=cur;
        }else{
            prev=cur;
            cur=cur.next;
        }
    }
    if(this.head.val==key){
        this.head=this.head.next;
    }
}

呼，寫(xiě)的我人傻了

你以為結(jié)束了嗎？NO！下面還有一大波鏈表面試題等著我和你，沖吧，牛牛！

三、鏈表面試題

刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn) OJ 鏈接

反轉(zhuǎn)一個(gè)單鏈表 OJ 鏈接

給定一個(gè)帶有頭結(jié)點(diǎn) head 的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn) OJ 鏈接

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn) OJ 鏈接

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的 OJ 鏈接

編寫(xiě)代碼，以給定值x為基準(zhǔn)將鏈表分割成兩部分，所有小于x的結(jié)點(diǎn)排在大于或等于x的結(jié)點(diǎn)之前 OJ 鏈接

在一個(gè)排序的鏈表中，存在重復(fù)的結(jié)點(diǎn)，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)，重復(fù)的結(jié)點(diǎn)不保留，返回鏈表頭指針 OJ 鏈接

鏈表的回文結(jié)構(gòu) OJ 鏈接

輸入兩個(gè)鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn) OJ 鏈接

給定一個(gè)鏈表，判斷鏈表中是否有環(huán) OJ 鏈接

給定一個(gè)鏈表，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無(wú)環(huán)，則返回 null OJ 鏈接

如果你已經(jīng)可以輕松應(yīng)對(duì)上述題目了，可以繼續(xù)去下面的鏈接中做題 Leetcode OJ 鏈接 和 牛客 OJ 鏈接

四、總結(jié)

今天簡(jiǎn)單了解了鏈表，以及對(duì)單向不帶頭非循環(huán)鏈表做了一些基操的實(shí)現(xiàn)。下章將包含個(gè)人的上述前11道 OJ 題的題解，以及了解雙向不帶頭非循環(huán)鏈表

本篇文章就到這里了，希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！