文章目錄

目錄

文章目錄

一、什么是鏈表?

線性表:

順序表:

二、鏈表的分類和實(shí)現(xiàn)

分類:

實(shí)現(xiàn):

1.創(chuàng)建節(jié)點(diǎn)類

2.創(chuàng)建單鏈表?

1.addTail(尾增)

?

2.刪除節(jié)點(diǎn)值為key的第一個(gè)節(jié)點(diǎn)

?3.插入節(jié)點(diǎn)(在指定位置)

4.獲取鏈表長度?

總結(jié)

大家好,這篇博客給大家講一下什么是鏈表以及單鏈表的實(shí)現(xiàn)過程

一、什么是鏈表?

再講解什么是鏈表時(shí),先給大家講一下大體上的分類線性表和順序表

線性表:

線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié) 構(gòu)，常見的線性表：鏈表、棧、隊(duì)列... 線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物 理上存儲時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。

?

可以看到鏈表在內(nèi)存中并不是連續(xù)的,只是在邏輯上是連續(xù)的,鏈表中的節(jié)點(diǎn)見縫插針般的在內(nèi)存中存儲?

順序表:

順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成 數(shù)據(jù)的增刪查改。

二、鏈表的分類和實(shí)現(xiàn)

分類:

鏈表根據(jù)是否包含頭結(jié)點(diǎn)來分可以分為兩類,根據(jù)是否循環(huán)來分也可以分為兩類

其中循環(huán)和非循環(huán)相對來說差別不大,下面我們將圍繞是否包含頭節(jié)點(diǎn)來進(jìn)行談?wù)?/p>

問題1:含頭節(jié)點(diǎn)的鏈表和不含頭節(jié)點(diǎn)的鏈表有什么不同?

帶頭結(jié)點(diǎn)的鏈表的第一個(gè)節(jié)點(diǎn)不存數(shù)據(jù),實(shí)現(xiàn)起來相對比較容易

不帶頭結(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)就是數(shù)據(jù)節(jié)點(diǎn),實(shí)現(xiàn)起來比帶頭結(jié)點(diǎn)的難一些,并且是刷題和面試的重點(diǎn)

下面我將帶大家來實(shí)現(xiàn)最經(jīng)典的單鏈表:不帶頭節(jié)點(diǎn)的非循環(huán)鏈表

實(shí)現(xiàn):

思路分析:

1.創(chuàng)建節(jié)點(diǎn)類Node,用來表示鏈表中的節(jié)點(diǎn)

2.創(chuàng)建單鏈表 SingleList

3.實(shí)現(xiàn)方法 增,刪,查.......

1.創(chuàng)建節(jié)點(diǎn)類

來思考一下節(jié)點(diǎn)類中應(yīng)該存在的信息?

日常工作生活中節(jié)點(diǎn)中記錄的信息是多種多樣的,為了簡單起見我們按最簡單的來,即節(jié)點(diǎn)中只包含

val和指向下一個(gè)節(jié)點(diǎn)的指針next

class Node{
    public int val;
    public Node next;

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

2.創(chuàng)建單鏈表?

有了節(jié)點(diǎn)類,我們就可以把一個(gè)個(gè)節(jié)點(diǎn)組合起來,組合成為一個(gè)在邏輯上是連續(xù)的鏈表了

那么在單鏈表中應(yīng)該存在什么呢?

首先應(yīng)該有個(gè)頭結(jié)點(diǎn),要不然無法知道鏈表從哪里開始,也不能將鏈表作為參數(shù)傳遞出去

其次應(yīng)該有構(gòu)造方法,不然寫這么個(gè)鏈表就會(huì)毫無意義

還有就是一些方法,基礎(chǔ)代碼給出,下面我們來一個(gè)一個(gè)實(shí)現(xiàn)方法

public class SingleListDemo {
    private Node head;

    public SingleListDemo(){
    }

}


class Node{
    public int val;
    public Node next;

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

1.addTail(尾增)

?

public void addTail(int val) {
    Node newNode = new Node(val);

    if (head == null) {
        head = newNode;
        return;
    }

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

    cur.next = newNode;
}

在這里我們可以延伸出在頭部插入節(jié)點(diǎn)的情況,即將新的節(jié)點(diǎn)的next指針指向頭結(jié)點(diǎn),將頭結(jié)點(diǎn)的指向更改為新的節(jié)點(diǎn)即可?

2.刪除節(jié)點(diǎn)值為key的第一個(gè)節(jié)點(diǎn)

// 刪除節(jié)點(diǎn)的Data值為key的第一個(gè)節(jié)點(diǎn)
public void DeleteKey(int key) {
    // 判斷鏈表是否為空
    if (head == null) {
        System.out.println("鏈表為空");
        return;
    }
    // 判斷第一個(gè)節(jié)點(diǎn)是否是要?jiǎng)h除的節(jié)點(diǎn)
    if (head.val == key) {
        HeadDelete();
        return;
    }
    Node cur = head;
    while (cur.next != null) {
        if (cur.next.val == key) {
            cur.next = cur.next.next;
            return;
        }
        cur = cur.next;
    }
}

?拓展: 刪除值為key的所有節(jié)點(diǎn),要求時(shí)間復(fù)雜度不超過O(n)

// 法一 循環(huán)遍歷
public void Delete(int Data) {
    if (head == null) {
        return;
    }
    while (head.val == Data) {
        head = head.next;
        if (head == null) {
            return;
        }
    }
    Node cur = head;// 定義臨時(shí)節(jié)點(diǎn)代替頭結(jié)點(diǎn)遍歷鏈表并刪除元素
    while (true) {
        if (cur.next == null) {
            return;
        }

        if (cur.next.val == Data) {
            System.out.println("刪除成功!");
            cur.next = cur.next.next;
            continue;
        }
        cur = cur.next;
    }

}

// 法二 - 雙指針
public void Delete2(int Data) {
    if (head == null) {
        return;
    }
    Node pre = head;
    Node cur = head.next;

    while (cur != null) {
        if (cur.val == Data) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    if (head.val == Data) {
        head = head.next;
    }
}

?3.插入節(jié)點(diǎn)(在指定位置)

// 在指定位置插入節(jié)點(diǎn),第一個(gè)節(jié)點(diǎn)為0號下標(biāo)
public void InsertAny(int index, int val) {
    // 判斷鏈表下標(biāo)是否合法
    if (index < 0 && index > getSize()) {
        System.out.println("下標(biāo)不合法!");
        return;
    }
    if (index == 0) {
        HeadAdd(val);
        return;
    }
    Node node = new Node(val);
    Node cur = head;
    // 遍歷鏈表找到下標(biāo)為index-1的元素
    while (index > 1) {//index-1
        index--;
        cur = cur.next;
    }
    node.next = cur.next;
    cur.next = node;
}

4.獲取鏈表長度?

public int getSize() {
    Node node = head;
    int size = 0;
    while (node != null) {
        node = node.next;
        size++;
    }
    return size;
}?

以上就是一些比較重要的方法了,下期見。?

總結(jié)

大家多多刷題吧,鏈表可是面試中筆試題的重點(diǎn)!文章來源地址http://www.zghlxwxcb.cn/news/detail-703406.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) - 單鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！