欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java集合中的鏈表與結(jié)構(gòu)詳解

 更新時(shí)間：2025年08月13日 10:51:15   作者：Y409001  
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序的通過鏈表中的引用鏈接次序?qū)崿F(xiàn),文章對比ArrayList與LinkedList的結(jié)構(gòu)差異,詳細(xì)講解了鏈表實(shí)現(xiàn)方法及常見面試題如反轉(zhuǎn)、中間節(jié)點(diǎn)查找等,感興趣的朋友跟隨小編一起看看吧

前情提要：在學(xué)習(xí) ArrayList 時(shí)，認(rèn)識(shí)到由于其底層是一段連續(xù)空間，當(dāng)在 ArrayList 任意位置插入或者刪除元素時(shí)，就需要將后序元素整體往前或者往后搬移，時(shí)間復(fù)雜度為O(n)，效率比較低，因此 ArrayList 不適合做任意位置插入和刪除比較多的場景。因此：java 集合中又引入了LinkedList，即鏈表結(jié)構(gòu)。

一、鏈表概念與結(jié)構(gòu)

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

其結(jié)構(gòu)總共有8種：

        帶頭鏈表中的第一個(gè)節(jié)點(diǎn)相當(dāng)于一個(gè)標(biāo)記，如果采用頭插法新增節(jié)點(diǎn)，只能在當(dāng)前頭的下一個(gè)節(jié)點(diǎn)插入；而如果是不帶頭的鏈表，頭插法是在第一個(gè)節(jié)點(diǎn)前面新增節(jié)點(diǎn)。

二、當(dāng)向單鏈表的實(shí)現(xiàn)

整個(gè)實(shí)現(xiàn)將圍繞下圖展開：

        定義一個(gè) cur 對象，表示當(dāng)前節(jié)點(diǎn)。用法：遍歷鏈表。

注意

1、cur 為空和 cur.next 為空的區(qū)別。     

2、單向鏈表不能回退。

2.1 準(zhǔn)備工作

        1、先定義一個(gè)類用來表示整個(gè)鏈表，名為 SingleLinkedList。

        2、而鏈表中包含節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)帶有兩個(gè)域，一個(gè)是數(shù)據(jù)域存儲(chǔ)整型數(shù)據(jù)；另一個(gè)是指針域，指針域中存放的是下一個(gè) 節(jié)點(diǎn) 的引用，因此其類型也就是節(jié)點(diǎn)；且注意兩個(gè)屬性都用 public 修飾，在測試時(shí)大有用途。將每個(gè)節(jié)點(diǎn)封裝成鏈表的內(nèi)部類。

        3、定義一個(gè)頭部節(jié)點(diǎn)，用于查找或者輸出鏈表數(shù)據(jù)，但這里并不代表鏈表帶頭。

        4、將對鏈表的操作封裝成一個(gè)接口，其功能包括打印鏈表數(shù)據(jù) display、計(jì)算鏈表長度 size、查找數(shù)據(jù) contains、頭插法插入數(shù)據(jù) addFirst、尾插法插入數(shù)據(jù) addLast、任意位置插入數(shù)據(jù) addIndex、刪除第一次出現(xiàn) key 的節(jié)點(diǎn) remove、刪除所有值為 key 的節(jié)點(diǎn) removeAllKey、清空。

SingleLinkedList 鏈表：

package test;
// 不帶頭 單向 鏈表
public class SingleLinkedList implements ILink{
    static class ListNode{   // 每一個(gè) 節(jié)點(diǎn) 都是對象，具有共同屬性，因此可以抽象成內(nèi)部類
        public int val;
        public ListNode next;  // 節(jié)點(diǎn)的地址，類型也應(yīng)該是節(jié)點(diǎn)的類型
        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode head;  // 頭節(jié)點(diǎn)
    @Override
    // ......
}

ILink 接口：

package test;
/**
 * 鏈表的操作
 */
public interface ILink {
    //頭插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號下標(biāo)
    void addIndex(int index,int data);
    //查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中
    boolean contains(int key);
    //刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
    void remove(int key);
    //刪除所有值為key的節(jié)點(diǎn)
    void removeAllKey(int key);
    //得到單鏈表的長度
    int size();
    // 清空
    void clear();
    // 打印鏈表數(shù)據(jù)
    void display();
}

        在實(shí)現(xiàn)具體的操作之前，還需要考慮鏈表是否為空，即 head == null ?

2.2 初始化鏈表

        在具體實(shí)現(xiàn)各項(xiàng)功能之前，需要有一個(gè)原始的鏈表，利于展示操作效果。其定義方法如下

package test;
public class SingleLinkedList implements ILink{
    // ......
    public void creatList(){  // 創(chuàng)建一個(gè)原始鏈表
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        this.head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
    }
    // ......
}

2.3 打印數(shù)據(jù)、鏈表長度、查找數(shù)據(jù)

        這三個(gè)功能都需要將鏈表從頭到尾遍歷一遍。而遍歷的條件只是當(dāng)前節(jié)點(diǎn)不為空。

package test;
public class SingleLinkedList implements ILink{
    // ......
    @Override
    public void display() {
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();   // 換行
    }
    @Override
    public int size() {
        ListNode cur = head;
        int count = 0;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
}
package test;
public class TestSingle {
    public static void main(String[] args) {
        // ILink iLink = new SingleLinkedList(); // 通過接口無法調(diào)用 creatList()
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.creatList();  // 還沒實(shí)現(xiàn)新增節(jié)點(diǎn)功能前調(diào)用的原始鏈表
        linkedList.display();
        System.out.println(linkedList.size());
    }
}

2.4 頭插法

@Override
public void addFirst(int data) {
    ListNode newNode = new ListNode(data);
    newNode.next = head;
    this.head = newNode;
}

        即使原先的鏈表是空的，代碼一樣能實(shí)現(xiàn)頭插法插入節(jié)點(diǎn)。

2.5 尾插法

@Override
public void addLast(int data) {
    ListNode newNode = new ListNode(data);
    if (head == null){  // 原來鏈表中一個(gè)節(jié)點(diǎn)都沒有的情況下
        head = newNode;
        return;
    }
    ListNode cur = head;
    while (cur.next != null){
        cur = cur.next;
    }  // 循環(huán)走完說明 cur.next == null 了
    cur.next = newNode;
}
package test_8_7;
public class TestSingle {
    public static void main(String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        // 實(shí)現(xiàn)新增節(jié)點(diǎn)功能之后，不需要調(diào)用 creatList()，也可以創(chuàng)建鏈表
        // 頭插法
        linkedList.addFirst(11);
        linkedList.addFirst(22);
        linkedList.addFirst(33);
        linkedList.addFirst(44);
        // 尾插法
        linkedList.addLast(55);
        linkedList.display();
        System.out.println(linkedList.size());
    }
}

2.6 任意位置插入節(jié)點(diǎn)

注意

1、指定位置的合法性；

2、指定下標(biāo)為 0 和 指定位置等于鏈表長度 的情況分開處理；

3、單向鏈表不能回退，因此注意 cur 的位置；

4、所有的插入，優(yōu)先綁定后面的節(jié)點(diǎn)。

    @Override
    public void addIndex(int index, int data) throws IllegalIndexException{
        int len = this.size();  // 存儲(chǔ)當(dāng)前長度，好處：提高效率
        if (index < 0 || index > len){
            throw new IllegalIndexException("指定位置不合法?。?！");
        }else {
            if (index == 0){
                this.addFirst(data);
                return;
            }
            if (index == len){
                this.addLast(data);
                return;
            }
            ListNode newNode = new ListNode(data);
            ListNode cur = head;
            while (index - 1 != 0){
                cur = cur.next;
                index--;
            }
            newNode.next = cur.next;
            cur.next = newNode;
        }
    }
package test;
// 處理指定位置的不合法異常
public class IllegalIndexException extends RuntimeException{
    public IllegalIndexException(){
    }
    public IllegalIndexException(String msg){
        super(msg);
    }
}

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

    @Override
    public void remove(int key) {
        if (head == null){
            return;
        }
        if(head.val == key){
            head = null;
        }
        ListNode cur = findNodeOfKey(key);
        if (cur == null){
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }
    public ListNode findNodeOfKey(int key){  // 找到存儲(chǔ)的數(shù)據(jù)是key的對象，并返回
        ListNode cur = head;
        while (cur.next != null){
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

提示

1、在鏈表中查找 key 可封裝成一個(gè)方法

2、查找 key 的條件 cur.next 不為空的前提下，已經(jīng)判斷了 cur.next 存儲(chǔ)的數(shù)據(jù)是否等于 key 了

2.8 刪除鏈表中所有數(shù)據(jù)為 key 的節(jié)點(diǎn)

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

2.9 清空

        像之前“清空” ArrayList 的方法在鏈表中是不可行的，因?yàn)槿绻靡恢贝嬖?，那么引用所指的對象無法被內(nèi)存回收，容易造成內(nèi)存泄漏，因此只有將 next 都置空了才算清空了鏈表數(shù)據(jù)。

    @Override
    public void clear() {
        ListNode cur = this.head;
        while (cur != null){
            ListNode prev = cur.next;
            cur.next = null;
            cur = prev;
        }
        head = null;
    }

三、面試題

3.1 刪除鏈表中等于給定值 key 的所有節(jié)點(diǎn)。（與上面的 2.8 一個(gè)意思）

3.2反轉(zhuǎn)一個(gè)單鏈表。

    public ListNode reverseList() {  // 反轉(zhuǎn)
        if(head == null){
            return null;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curNode = cur.next;
            cur.next = head;
            head = cur;
            cur = curNode;
        }
        return head;
    }

3.3返回鏈表中的中間節(jié)點(diǎn)，如果有兩個(gè)中間節(jié)點(diǎn)，則返回第2個(gè)節(jié)點(diǎn)。

提示，不能通過計(jì)算鏈表長度的方法進(jìn)行編程。

那么，采用雙指針的方法，快指針走兩步，慢指針走1步，最后慢指針指向的就是中間。

    public ListNode middleNode() {  // 找中間節(jié)點(diǎn)
        ListNode fast = head;  // 快指針，走兩步
        ListNode slow = head;  // 慢指針，走一步
        while(fast != null && fast.next != null){  // &&前面必須是 fast != null 的條件
            fast = fast.next.next;
            slow = slow.next;
        }
        /*while(fast.next != null && fast != null){  // 輸出 NullPointerException
            fast = fast.next.next;
            slow = slow.next;
        }*/
        return slow;
    }

3.4輸出該鏈表中倒數(shù)第 k 個(gè)節(jié)點(diǎn)。

        雖然 leetcode 上已經(jīng)保證了 k 的合法性，但自己實(shí)現(xiàn)的時(shí)候還是需要注意 k 的有效范圍。

    public int kthToLast(int k) {  // 返回倒數(shù)第k個(gè)字節(jié)的數(shù)據(jù)
        if(head == null){
            return -1;
        }
        // 注意k的范圍
        if (k <= 0){
            return -1;
        }
        /*if (k > 5){  // 這樣寫還得求鏈表的長度，不好
            return -1;
        }*/
        ListNode fast = head;
        ListNode slow = head;
        int count = 0;
        while(count != k-1){  // 為了與慢指針拉開一定的距離
            fast = fast.next;
            if(fast == null)  // 這里就是判斷k是否超出鏈表長度的條件
                return -1;
            count++;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

3.5合并兩個(gè)有序鏈表并按升序排序成有序鏈表返回。

提示

1、創(chuàng)建一個(gè)頭節(jié)點(diǎn)，作為標(biāo)志，可存儲(chǔ)數(shù)據(jù)，但該數(shù)據(jù)無實(shí)際意義；

2、返回的節(jié)點(diǎn)不是創(chuàng)建的頭節(jié)點(diǎn)。

3、在自己實(shí)現(xiàn)的鏈表中實(shí)現(xiàn)時(shí)，需要注意，因?yàn)樵摲椒ú僮鞯氖莾蓚€(gè)鏈表，因此不好將它定義到 SingleLinkedList 這個(gè)類中，因此直接定義到測試類。但直接定義到測試類時(shí)因?yàn)?ListNode 是 SingleLinkedList 的內(nèi)部類，需要用 SingleLinkedList. 來調(diào)用 ListNode

package test;
public class TestSingle {
    public static SingleLinkedList.ListNode mergeTwoLists
            (SingleLinkedList.ListNode headA, SingleLinkedList.ListNode headB) { // 合并兩個(gè)有序鏈表并排序
        SingleLinkedList.ListNode newHead = new SingleLinkedList.ListNode(-1); // 隨便傳一個(gè)數(shù)據(jù)，因?yàn)檫@個(gè)數(shù)據(jù)無效
        SingleLinkedList.ListNode tmp = newHead;
        while(headA != null && headB != null){
            if (headA.val < headB.val){
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }else{
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if (headA != null){
            tmp.next = headA;
        }
        if (headB != null){
            tmp.next = headB;
        }
        return newHead.next;
    }
    public static void main(String[] args) {
        // 測試合并兩個(gè)鏈表
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addFirst(4);
        linkedList.addLast(11);
        linkedList.addLast(19);
        linkedList.addLast(44);
        SingleLinkedList linkedList2 = new SingleLinkedList();
        linkedList2.addFirst(3);
        linkedList2.addLast(6);
        linkedList2.addLast(32);
        linkedList2.addLast(57);
        SingleLinkedList.ListNode newNode = mergeTwoLists(linkedList.head, linkedList2.head);
        linkedList.display(newNode);
    }
}

3.6以 x 值為基準(zhǔn)將鏈表分割成兩部分，所有小于 x 的節(jié)點(diǎn)排在大于或等于 x 的節(jié)點(diǎn)之后。

    public ListNode partition(int x) {  // 不改變原來數(shù)據(jù)的順序下，將所有小于x的結(jié)點(diǎn)排在其余結(jié)點(diǎn)之前
        ListNode beforeStart = null;  // 小于x的頭節(jié)點(diǎn)
        ListNode beforeEnd = null;    // 小于x的尾節(jié)點(diǎn)
        ListNode afterStart = null;   // 大于x的頭節(jié)點(diǎn)
        ListNode afterEnd = null;     // 大于x的尾節(jié)點(diǎn)
        ListNode cur = head;
        while(cur != null){
            if(cur.val < x){
                if(beforeStart == null){  // 第一次插入
                    beforeStart = beforeEnd = cur;
                }else{
                    beforeEnd.next = cur;
                    beforeEnd = beforeEnd.next;
                }
            }else{
                if(afterStart == null){
                    afterStart = afterEnd = cur;
                }else{
                    afterEnd.next = cur;
                    afterEnd = afterEnd.next;
                }
            }
            cur = cur.next;
        }
        // 如果沒有小于x的節(jié)點(diǎn)
        if (beforeStart == null){
            return afterStart;
        }
        // 前后兩部分銜接起來
        beforeEnd.next = afterStart;
        // 第2部分的最后一個(gè)節(jié)點(diǎn)的引用要置空，否則編譯超出范圍
        if(afterStart != null){
            afterEnd.next = null;
        }
        return beforeStart;
    }

3.7判斷是否為回文鏈表。

提示

1、找到鏈表的中間節(jié)點(diǎn)；

2、將中間節(jié)點(diǎn)后面的節(jié)點(diǎn)反轉(zhuǎn)；

3、頭節(jié)點(diǎn)的值與最后一個(gè)節(jié)點(diǎn)的值進(jìn)行比較，然后頭節(jié)點(diǎn)往后，最后一個(gè)節(jié)點(diǎn)往前。

        注意此題需要區(qū)分鏈表的節(jié)點(diǎn)數(shù)，如果是奇數(shù)比較好判斷，但如果是偶數(shù)，需要考慮另一個(gè)判斷條件。

奇數(shù)情況下：

偶數(shù)情況下：

判斷條件是 fast.next = slow;  不能是 slow.next = fast;
且該判斷條件前提是兩者的數(shù)據(jù)是相等的，因此判斷順序很重要。

    public boolean chkPalindrome(){ // 判斷是否是回文鏈表
        if(head == null){
            return true;
        }
        // 1、找到中間節(jié)點(diǎn)
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        // 2、反轉(zhuǎn)
        ListNode cur = slow.next;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }
        // 3、判斷是否是回文
        while(head != slow){
            if (head.val != slow.val){
                return false;
            }
            // 如果鏈表是偶數(shù)的話，應(yīng)該是下面的判斷條件
            // 前提是兩個(gè)val值是相等的
            if (head.next == slow){  // 注意是head的下一個(gè)節(jié)點(diǎn)是slow才對，因?yàn)閟low的下一個(gè)節(jié)點(diǎn)回到了slow后面了。
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

3.8輸入兩個(gè)鏈表，找出它們的公共節(jié)點(diǎn)。

    public SingleLinkedList.ListNode getIntersectionNode
            (SingleLinkedList.ListNode headA, SingleLinkedList.ListNode headB) {  // 兩鏈表是否相交
        SingleLinkedList.ListNode pLong = headA;  // 假設(shè)鏈表A的長度比鏈表B的長
        SingleLinkedList.ListNode pShort = headB;
        int lenA = 0;   // 鏈表A的長度
        int lenB = 0;   // 鏈表B的長度
        while (pLong != null){
            lenA++;
            pLong = pLong.next;
        }
        while (pShort != null){
            lenB++;
            pShort = pShort.next;
        }
        // 因?yàn)樵谟?jì)算長度時(shí)改變了兩個(gè)值，因此要從新定義
        pLong = headA;
        pShort = headB;
        // 計(jì)算兩個(gè)鏈表長度的差值
        int len = lenA - lenB;
        if (len < 0){  // 如果len為負(fù)數(shù)，說明lenB大于lenA，規(guī)定pLong一定指向長的鏈表
            pLong = headB;
            pShort = headA;
            len = lenB - lenA;  // 記住要把差值換成正數(shù)
        }
        // 長的鏈表先走len步
        while (len != 0){
            pLong = pLong.next;
            len--;
        }
        // 兩個(gè)引用同時(shí)走，知道它們相遇
        while (pLong != pShort){
            pLong = pLong.next;
            pShort = pShort.next;
        }
        if (pLong == null){
            return null;  // 說明沒有相交
        }
        return pLong;
    }

測試：

    public static void creatIntersect
            (SingleLinkedList.ListNode headA, SingleLinkedList.ListNode headB){  // 自己實(shí)現(xiàn)相交
        headA.next.next = headB.next.next.next;
    }
    public static void main(String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addFirst(5);
        linkedList.addLast(1);
        linkedList.addLast(8);
        linkedList.addLast(4);
        linkedList.addLast(5);
        SingleLinkedList linkedList2 = new SingleLinkedList();
        linkedList2.addFirst(4);
        linkedList2.addLast(1);
        linkedList2.addLast(6);
        linkedList2.addLast(8);
        linkedList2.addLast(4);
        linkedList2.addLast(5);
        creatIntersect(linkedList.head, linkedList2.head);
        SingleLinkedList.ListNode ret = getIntersectionNode(linkedList.head, linkedList2.head);
        System.out.println(ret.val);
    }

3.9判斷鏈表中是否有環(huán)。* 進(jìn)階：給定一個(gè)鏈表的頭節(jié)點(diǎn)  head ，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無環(huán)，則返回 null。

    public boolean hasCycle(){  // 判斷當(dāng)前鏈表是否有環(huán)
        if (head == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }
    public void creatLoop(){  // 創(chuàng)建環(huán)
        ListNode cur = head;
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = head.next.next.next;
    }
    public ListNode detectCycle() {   // 給定一個(gè)鏈表，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無環(huán)，則返回 NULL
        ListNode fast = head;
        ListNode slow = head;
        while( fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next == null){
            return null;  // 說明沒有環(huán)
        }
        slow = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

測試類：

public class TestSingle {
    public static void main(String[] args) {
        // 測試返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addFirst(5);
        linkedList.addLast(1);
        linkedList.addLast(8);
        linkedList.addLast(4);
        linkedList.addLast(5);
        linkedList.creatLoop();
        System.out.println(linkedList.hasCycle());
        SingleLinkedList.ListNode ret = linkedList.detectCycle();
        System.out.println(ret.val);
    }
}

到此這篇關(guān)于Java集合中的鏈表與結(jié)構(gòu)詳解的文章就介紹到這了,更多相關(guān)java集合鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評論