Java數據結構之鏈表的增刪查改詳解

目錄

一、鏈表的概念和結構

1.1 鏈表的概念

簡(jiǎn)單來(lái)說(shuō)鏈表是物理上不一定連續，但是邏輯上一定連續的一種數據結構

1.2 鏈表的分類(lèi)

實(shí)際中鏈表的結構非常多樣，以下情況組合起來(lái)就有8種鏈表結構. 單向和雙向，帶頭和不帶頭，循環(huán)和非循環(huán)。排列組合和會(huì )有8種。
但我這只是實(shí)現兩種比較難的鏈表，理解之后其它6種就比較簡(jiǎn)單了
1.單向不帶頭非循環(huán)鏈表
2.雙向不帶頭非循環(huán)鏈表

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

2.1 創(chuàng )建節點(diǎn)類(lèi)型

我們創(chuàng )建了一個(gè) ListNode 類(lèi)為節點(diǎn)類(lèi)型，里面有兩個(gè)成員變量，val用來(lái)存儲數值，next來(lái)存儲下一個(gè)節點(diǎn)的地址。
還有一個(gè)帶一個(gè)參數的構造方法在實(shí)例化對象的同時(shí)給val賦值，因為我們不知道下一個(gè)節點(diǎn)的地址所以next是默認值一個(gè)null

class ListNode {
    public int val;//數值
    public ListNode next;//下一個(gè)節點(diǎn)的地址

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

我們在 MyLinkedList 里創(chuàng )建一個(gè)head變量來(lái)標識鏈表的頭部，接著(zhù)就是實(shí)現單鏈表的增刪查改了

2.2 頭插法

這個(gè)頭插法并不要考慮第一次插入，每次插入只需要把插入的節點(diǎn)node 的next值改成頭節點(diǎn)，再把頭節點(diǎn)指向node

//頭插法
public void addFirst(int data) {
    ListNode node = new ListNode(data);
    node.next = this.head;
    this.head = node;
}

2.3 尾插法

尾插法首先要考慮是不是第一次插入，如果是的話(huà)直接把head指向node就好了，如果不是第一次插入，則需要定義一個(gè)cur來(lái)找尾巴節點(diǎn)，把尾巴節點(diǎn)的next值改成node就好了。因為如果不用尾巴節點(diǎn)的話(huà)，head就無(wú)法標識到頭部了

//尾插法
public void addLast(int data) {
    ListNode node = new ListNode(data);
    ListNode cur = this.head;
    //第一次插入
    if(this.head == null) {
        this.head = node;
    }else{
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
}

2.4 獲取鏈表長(cháng)度

定義一個(gè)計數器count，當cur遍歷完鏈表的時(shí)候直接返回count就好

//得到單鏈表的長(cháng)度
public int size() {
    int count = 0;
    ListNode cur = this.head;
    while (cur != null) {
        cur = cur.next;
        count++;
    }
    return count;
}

2.5 任意位置插入

我們假設鏈表的頭是從0位置開(kāi)始的，任意位置插入需要考慮幾點(diǎn)
1.位置的合法性，如果位置小于0，或者大于鏈表長(cháng)度則位置不合法
2.如果要插入的是0位置直接使用頭插法
3.如果插入的位置等于鏈表長(cháng)度則使用尾插法，因為我們這鏈表是從0開(kāi)始的

最關(guān)鍵的就是從中間任意位置插入 要從中間位置插入，就需要找到要插入位置的前一個(gè)節點(diǎn)的位置。再插入到它們中間。

  /**
     * 讓 cur 向后走 index - 1 步
     * @param index
     * @return
     */
public ListNode findIndexSubOne(int index) {
    int count = 0;
    ListNode cur = this.head;
    while (count != index-1) {
        cur = cur.next;
        count++;
    }
    return  cur;
}
//任意位置插入,第一個(gè)數據節點(diǎn)為0號下標
public void addIndex(int index,int data) {
    //判斷合法性
    if(index < 0 || index > size()) {
            System.out.println("index位置不合法");
            return;
    }
    //頭插法
    if(index == 0) {
        this.addFirst(data);
        return;
    }
    //尾插法
    if(index == size()) {
        this.addLast(data);
        return;
    }
    //找前驅,cur指向的是 index 的前一個(gè)節點(diǎn)
    ListNode cur = findIndexSubOne(index);
    ListNode node = new ListNode(data);
    node.next = cur.next;
    cur.next = node;
}

2.6 查找關(guān)鍵字

當我們要查找鏈表中是否有某一個(gè)關(guān)鍵字時(shí)，只需要定義一個(gè)cur從頭開(kāi)始遍歷即可

//查找是否包含關(guān)鍵字key是否在單鏈表當中
public boolean contains(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

2.7 刪除第一次出現值為key的節點(diǎn)

這個(gè)思路其實(shí)也很簡(jiǎn)單，考慮到兩種情況即可

1.如果要刪除的是頭節點(diǎn)只需要把頭節點(diǎn)指向它的向一個(gè)節點(diǎn)即可
2.還有一種則是不存在key的情況，所以這里寫(xiě)了一個(gè)方法來(lái)判讀key是否存在，如果存在則返回key的前一個(gè)節點(diǎn)的位置
3.存在則把要刪除的節點(diǎn)的前驅的next改成它的next即可

/**
  * 找要刪除 key 的前一個(gè)節點(diǎn)
 * @return
 */
public ListNode searchPrev(int key) {
    ListNode prev = this.head;
    while (prev.next != null) {
        if (prev.next.val == key) {
            return prev;
        }
        prev = prev.next;
    }
    return null;
}
//刪除第一次出現關(guān)鍵字為key的節點(diǎn)
public void remove(int key) {
    if(this.head.val == key) {
        this.head = this.head.next;
        return;
    }
    //找 key 的前驅節點(diǎn)
    ListNode prev = searchPrev(key);
    if(prev == null) {
        System.out.println("沒(méi)有key這個(gè)關(guān)鍵字");
        return;
    }
    //刪除
    ListNode delete = prev.next;
    prev.next = delete.next;
}

2.8 刪除所有值為key的節點(diǎn)

假設要刪除的是3，思路：

定義兩個(gè)節點(diǎn)點(diǎn)類(lèi)型的變量，prev指向head，cur指向head的下一個(gè)節點(diǎn)。
如果判斷cur的val值是要刪除的值，如果是則直接跳過(guò)這個(gè)節點(diǎn) 如果不是則讓prev和cur往后走，直到整個(gè)鏈表遍歷完。
到最后會(huì )發(fā)現頭節點(diǎn)并沒(méi)有遍歷到，循環(huán)結束后則需要判讀頭節點(diǎn)是不是要刪除的節點(diǎn)

記住一定要邊畫(huà)圖邊寫(xiě)代碼！

//刪除所有值為key的節點(diǎn)
public void removeAllKey(int key) {
    ListNode prev = this.head;
    ListNode cur = this.head.next;
    while (cur != null) {
        if(cur.val == key) {
            prev.next = cur.next;
            cur = cur.next;
        }else {
            prev = cur;
            cur = cur.next;
        }
    }
    //判斷第一個(gè)節點(diǎn)是否是要刪除的節點(diǎn)
    if(this.head.val == key) {
        this.head = this.head.next;
    }
}

2.9 遍歷打印鏈表

定義一個(gè)cur直接遍歷打印就好

//打印鏈表
public void display() {
    ListNode cur = this.head;
    while (cur != null) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

置空鏈表

置空鏈表只需要一個(gè)個(gè)置空即可，并不建議直接把頭節點(diǎn)置空這種暴力做法

//置空鏈表
public void clear() {
    ListNode cur = this.head;
    //一個(gè)個(gè)制空
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.next = null;
        cur = curNext;
    }
    this.head = null;
}

三、雙向不帶頭非循環(huán)鏈表

雙向鏈表和單向鏈表的最大的區別就是多了一個(gè)前驅節點(diǎn)prev，同樣來(lái)實(shí)現雙向鏈表的增刪查改

public class TestLinkedList {
    public ListNode head;
    public ListNode last;
}

3.1 創(chuàng )建節點(diǎn)類(lèi)型

同樣先定義節點(diǎn)類(lèi)型，比單向鏈表多了一個(gè)前驅節點(diǎn)而已。

class ListNode {
    public int val;
    public ListNode prev;
    public ListNode next;

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

雙向鏈表還定義了一個(gè)last來(lái)標識尾巴節點(diǎn)，而單鏈表只是標識了頭節點(diǎn)。

3.2 頭插法

因為這是雙向鏈表，第一次插入要讓head和last同時(shí)指向第一個(gè)節點(diǎn)。
如果不是第一次插入，則需要
1.把head的前驅節點(diǎn)改成node,
2.再把node的next改成head，
3.然后把頭節點(diǎn)head再指向新的頭節點(diǎn)node。

//頭插法
public void addFirst(int data) {
    ListNode node = new ListNode(data);
    //第一次插入
    if(this.head == null) {
        this.head = node;
        this.last = node;
    }else {
        head.prev = node;
        node.next = this.head;
        this.head = node;
    }
}

3.3 尾插法

雙向鏈表有一個(gè)last來(lái)標識尾巴節點(diǎn)，所以在尾插的時(shí)候不用再找尾巴節點(diǎn)了。和頭插法類(lèi)似

//尾插法
public void addLast(int data) {
    ListNode node = new ListNode(data);
    //第一次插入
    if(this.head == null) {
        this.head = node;
        this.last = node;
    }else {
        this.last.next = node;
        node.prev = this.last;
        this.last = node;
    }
}

3.4 獲取鏈表長(cháng)度

這個(gè)和單鏈表一樣，直接定義個(gè)cur遍歷

//得到鏈表的長(cháng)度
public int size() {
    ListNode cur = this.head;
    int count = 0;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

3.5 任意位置插入

任意位置插入也和單鏈表類(lèi)似有三種情況。判斷合法性和頭插尾插就不多了主要還是在中間的隨機插入，一定要注意修改的順序！

要修改的地方一共有四個(gè)，一定要畫(huà)圖理解！

//找要插入的節點(diǎn)的位置
public ListNode searchIndex(int index) {
    ListNode cur = this.head;
    while (index != 0) {
        cur = cur.next;
        index--;
    }
    return  cur;
}
//任意位置插入,第一個(gè)數據節點(diǎn)為0號下標
public void addIndex(int index,int data) {
    //判斷index位置的合法性
    if(index < 0 || index > this.size()) {
        System.out.println("index的位置不合法");
        return;
    }
    //頭插法
    if(index == 0) {
        this.addFirst(data);
        return;
    }
    //尾插法
    if(index == this.size()) {
        this.addLast(data);
        return;
    }
    //中間插入
    ListNode node = new ListNode(data);
    ListNode cur = searchIndex(index);
    node.next = cur;
    node.prev = cur.prev;
    cur.prev.next = node;
    cur.prev = node;
}

3.6 查找關(guān)鍵字

這里和單鏈表一樣，直接定義個(gè)cur遍歷看看鏈表里有沒(méi)有這個(gè)值即可

//查找是否包含關(guān)鍵字key是否在單鏈表當中
public boolean contains(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

3.7 刪除第一次出現的關(guān)鍵字key的節點(diǎn)

思路：遍歷鏈表找第一次出現的節點(diǎn)，刪完return。一共分三種情況
1.頭節點(diǎn)是要刪除的節點(diǎn)
2.尾巴節點(diǎn)是要刪除的節點(diǎn)
3.中間的節點(diǎn)是要刪除的節點(diǎn)

//刪除第一次出現關(guān)鍵字為key的節點(diǎn)
public void remove(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            //要刪除的是頭節點(diǎn)
            if(this.head == cur) {
                this.head = this.head.next;
                this.head.prev = null;
            }else {
                //尾巴節點(diǎn)和中間的節點(diǎn)兩種情況
                cur.prev.next = cur.next;
                if(this.last == cur) {
                    //刪除尾巴節點(diǎn)
                    cur = cur.prev;
                }else {
                    cur.next.prev = cur.prev;
                }
            }
            //已經(jīng)刪完了
            return;
        }else {
            cur = cur.next;
        }
    }
}

3.8 刪除所有值為key的節點(diǎn)

思路和刪除一個(gè)key類(lèi)似，但需要注意兩個(gè)點(diǎn)。

1.刪完就不用return了，而是繼續往后走，因為這里是刪除所有為key需要把列表遍歷完
2.還有就是要考慮當整個(gè)鏈表都是要刪除的情況，if判斷一下不然會(huì )發(fā)生空指針異常

//刪除所有值為key的節點(diǎn)
public void removeAllKey(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            //要刪除的是頭節點(diǎn)
            if(this.head == cur) {
                this.head = this.head.next;
                //假設全部是要刪除的節點(diǎn)
                if(this.head != null) {
                    this.head.prev = null;
                }else {
                 //防止最后一個(gè)節點(diǎn)不能被回收
                 this.last = null;
                }
            }else {
                //尾巴節點(diǎn)和中間的節點(diǎn)兩種情況
                cur.prev.next = cur.next;
                if(this.last == cur) {
                    //刪除尾巴節點(diǎn)
                    cur = cur.prev;
                }else {
                    cur.next.prev = cur.prev;
                }
            }
            //走一步
            cur = cur.next;
        }else {
            cur = cur.next;
        }
    }
}

3.9 遍歷打印鏈表

//打印鏈表
public void display() {
    ListNode cur = this.head;
    while (cur != null) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

置空鏈表

遍歷鏈表一個(gè)一個(gè)置為null，再把頭節點(diǎn)和尾巴節點(diǎn)值為null。防止內存泄漏

//置空鏈表
public void clear() {
    ListNode cur = this.head;
    //一個(gè)一個(gè)置空
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.prev = null;
        cur.next = null;
        cur = curNext;
    }
    this.head = null;
    this.last = null;
}

四、總結

1.這里實(shí)現了兩種較難的鏈表：?jiǎn)蜗虿粠ь^非循環(huán)和雙向不帶頭非循環(huán)

2.鏈表物理上不一定連續，但邏輯上一定連續。

3.增：鏈表插入一個(gè)元素只需要修改指向，所以時(shí)間復雜度為O(1)

4:刪：鏈表刪除元素，同樣只需修改指向，時(shí)間復雜度為O(1)

5.查：鏈表如果需要查找一個(gè)元素需要遍歷鏈表，所以時(shí)間復雜度為O(n)

6.改：鏈表要去找到要修改的元素，所以時(shí)間復雜度為O(n).

什么時(shí)候用鏈表？
如果是插入和刪除比較頻繁的時(shí)候，使用鏈表。注意：是不涉及到移動(dòng)數據的情況！

到此這篇關(guān)于Java數據結構之鏈表的增刪查改詳解的文章就介紹到這了,更多相關(guān)Java鏈表內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！