JAVA單鏈表的詳細介紹

這篇文章主要講解了“JAVA單鏈表的詳細介紹”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“JAVA單鏈表的詳細介紹”吧！

目錄

• 一、鏈表 

• 1. 概念

• 2. 結構

• 二、單向不帶頭非循環鏈表 

• 1. 概念及結構

• 2. 鏈表的實現

• 
  

一、鏈表 

1. 概念

鏈表是一種物理存儲結構上非連續的存儲結構，數據元素的邏輯順序是通過鏈表中的引用鏈接次序實現的

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

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

2. 結構

鏈表其實可以想象成一條被打了一些結的繩子

而實際上，鏈表就是由一個個節點構成的，只不過每個節點一般有兩個域

數值域 data： 里面存儲數據

next 域： 里面存儲的是下一個節點的地址（是引用變量）

其中

尾節點： 當這個節點的 next 域為 null 時，該節點就是尾節點

頭節點： 整個鏈表的第一個節點就是頭節點

實際中的鏈表結構非常多，通過以下的情況的組合可以有8種鏈表的結構（比如帶頭單向循環鏈表就是一種）

單向、雙向

帶頭節點、不帶頭

節點循環、非循環

而上圖所示，就是一個單向不帶頭非循環鏈表。

可能有人會疑問，上述圖片中不是存在頭節點嗎？那為啥它又是一個不帶頭節點的鏈表呢？我將上述圖片實例稍稍改一下就是帶頭節點的了

我在原有的頭節點前面又多了一個節點，并且這個節點的數值域里面的數據可有可無，因為對其沒有影響。而這里面的頭節點只是一個標志，標識這個節點是該鏈表的頭

那帶頭節點的和不帶頭結點的鏈表有啥差別呢？

不帶頭： 這個鏈表的頭節點可能發生改

變帶頭： 這個鏈表的頭節點不會發生改變

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

即將尾節點的 next 域存儲了頭節點的地址

我們知道一個節點一般就兩個域，但如果是雙向鏈表，則就有三個域了

數值域 data： 里面存儲數據

next 域： 里面存儲的是下一個節點的地址（是引用變量）

prev 域： 里面存儲的是上一個節點的地址（是引用變量）

我們畫一個不帶頭雙向非循環鏈表就是這樣的

接下來我將主要介紹單向不帶頭非循環鏈表和雙向不帶頭非循環鏈表，這兩種鏈表也是經常出現在面試題中的

二、單向不帶頭非循環鏈表 

1. 概念及結構

上述通過圖解，大家應該對單向不帶頭非循環鏈表應該有了了解。那么代碼中該怎么實現呢？

我們知道，鏈表應該可以看作一個類，而節點本身其實也可以抽象的看作成一個類

首先對于節點類，代碼可以寫出這樣

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

先定義了數值域，再定義了 next 域（由于 next 存儲的是下一個節點的地址，故寫出上述那樣）。而我們初始時可以知道 val，所以可以寫個構造函數對 val 進行初始化，而該節點的 next 域初始時是不可能知道的，所以不對 next 做初始化

如果創造一個 Node 對象就可以寫出

Node node = new Node(10);

即頭節點的數值域為10。

再定義鏈表類，代碼可以寫成這樣

public class MyLinkedList {
    public Node head;
}

我們定義了一個頭節點，這是我們很容易發現的，就比如我要對該鏈表進行頭插，則該鏈表的頭節點一直都在改變。所以寫上述的代碼就是為了標識單鏈表的頭節點。

2. 鏈表的實現

接下來我們來實現單向不帶頭非循環鏈表的一些操作

打印鏈表

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

求鏈表的長度

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

通過下標找到前驅節點（第一個節點下標為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;
}

通過值 key 找到前驅節點（第一個節點下標為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;
}

刪除第一次出現的值為 key 的節點

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("鏈表中無要刪除的元素");
    }else {
        node.next = node.next.next;
    }
}

刪除所有出現的值為 key 的節點

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單鏈表的詳細介紹”的內容了，經過本文的學習后，相信大家對JAVA單鏈表的詳細介紹這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！