JAVA單鏈表的詳細(xì)介紹

這篇文章主要講解了“JAVA單鏈表的詳細(xì)介紹”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“JAVA單鏈表的詳細(xì)介紹”吧！

目錄

• 一、鏈表 

• 1. 概念

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

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

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

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

• 
  

一、鏈表 

1. 概念

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

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

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

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;
    }
}

感謝各位的閱讀，以上就是“JAVA單鏈表的詳細(xì)介紹”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)JAVA單鏈表的詳細(xì)介紹這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！