目錄

(一) 線性表

(二) ArrayList

1. ArrayList的介紹

2. ArrayList的常見(jiàn)方法和使用

3. ArrayList的遍歷

4. ArrayList的模擬實(shí)現(xiàn)

5. ArrayList的優(yōu)缺點(diǎn)

(三)?LinkedList

1. LinkedList的介紹

2. LinkedList的常見(jiàn)方法和使用

3. LinkedList的遍歷

4. LinkedList的模擬實(shí)現(xiàn)

5. LinkedList的優(yōu)缺點(diǎn)

(四) ArrayList和LinkedList的區(qū)別

總結(jié)

(一) 線性表

線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié) 構(gòu)，常見(jiàn)的線性表：順序表、鏈表、棧、隊(duì)列...

線性表在邏輯上是線性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物 理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。如下圖:

(二) ArrayList

1. ArrayList的介紹

ArrayList是Java中的一個(gè)動(dòng)態(tài)數(shù)組類, 即順序表，可以動(dòng)態(tài)地增加或減少數(shù)組的大小。它是一個(gè)可以動(dòng)態(tài)改變大小的數(shù)組，可以根據(jù)需要自動(dòng)地增加或減少數(shù)組的大小。ArrayList可以存儲(chǔ)任意類型的對(duì)象，包括基本數(shù)據(jù)類型和引用類型, 它實(shí)現(xiàn)了List接口, 具體框架圖如下：

[說(shuō)明]

1. ArrayList實(shí)現(xiàn)了RandomAccess接口，表明ArrayList支持隨機(jī)訪問(wèn)

2. ArrayList實(shí)現(xiàn)了Cloneable接口，表明ArrayList是可以clone的

3. ArrayList實(shí)現(xiàn)了Serializable接口，表明ArrayList是支持序列化的

4. 和Vector不同，ArrayList不是線程安全的，在單線程下可以使用，在多線程中可以選擇Vector或者 CopyOnWriteArrayList

5. ArrayList底層是一段連續(xù)的空間，并且可以動(dòng)態(tài)擴(kuò)容，是一個(gè)動(dòng)態(tài)類型的順序表

2. ArrayList的常見(jiàn)方法和使用

使用ArrayList可以方便地進(jìn)行元素的添加、刪除和查找操作，是Java中常用的集合類之一。

ArrayList類包含許多常用的方法，以下是一些常見(jiàn)的方法和它們的使用：

常見(jiàn)的方法

• boolean add(E e)：向ArrayList中尾插 一個(gè)元素e。
• void add(int index, E element): 將 e 插入到 index 位置
• E remove(int index)：移除指定索引位置的元素。
• E get(int index)：獲取指定索引位置的元素。
• size()：獲取ArrayList的大小
• E set(int index, E element): 將下標(biāo) index 位置元素設(shè)置為 element
• void clear(): 清空
• boolean contains(Object o)：判斷ArrayList是否包含指定的元素。
• int indexOf(Object o)：返回指定元素在ArrayList中第一次出現(xiàn)的索引。
• int lastIndexOf(Object o):?返回指定元素在ArrayList中最后一次出現(xiàn)的索引。

? 使用:

import java.util.ArrayList;

public class ArrayListExample {
   public static void main(String[] args) {
            // 創(chuàng)建一個(gè)ArrayList
            ArrayList<String> list = new ArrayList<>();

            // 向ArrayList中尾插元素
            list.add("apple");
            list.add("banana");
            list.add("orange");

            // 將元素插入到指定索引位置
            list.add(1, "grape");

            //遍歷ArrayList
            System.out.print("打印1: ");
            for (String ret: list) {
                System.out.print(ret+" ");
            }
            System.out.println();

            // 移除指定索引位置的元素
            list.remove(2);

            //遍歷ArrayList
            System.out.print("打印2: ");
            for (String ret: list) {
                System.out.print(ret+" ");
            }
            System.out.println();

            // 獲取指定索引位置的元素
            String fruit = list.get(0);
            System.out.println("索引0處的水果: " + fruit);

            // 獲取ArrayList的大小
            int size = list.size();
            System.out.println("ArrayList的大小: " + size);

            // 將指定索引位置的元素設(shè)置為新元素
            list.set(2, "cherry");

            // 判斷ArrayList是否包含指定的元素
            boolean contains = list.contains("apple");
            System.out.println("是否包含'apple': " + contains);

            // 返回指定元素在ArrayList中第一次出現(xiàn)的索引
            int index = list.indexOf("banana");
            System.out.println("'banana'第一次出現(xiàn)的索引: " + index);

            // 返回指定元素在ArrayList中最后一次出現(xiàn)的索引
            int lastIndex = list.lastIndexOf("apple");
            System.out.println("'apple'最后一次出現(xiàn)的索引: " + lastIndex);

            // 清空ArrayList
            list.clear();

            //遍歷ArrayList
            System.out.print("打印3: ");
            for (String ret: list) {
                System.out.print(ret+" ");
            }
            System.out.println();
        }
}

3. ArrayList的遍歷

ArrayList可以使用三種方式遍歷：for循環(huán)+下標(biāo)、foreach、使用迭代器, 代碼如下:

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        // 創(chuàng)建一個(gè)ArrayList對(duì)象，它是List接口的實(shí)現(xiàn)類
        List<String> list = new ArrayList<>();

        // 將指定的元素添加到列表的末尾
        list.add("apple");
        list.add("banana");
        list.add("cherry");

        //for循環(huán)+下標(biāo)
        System.out.print("for循環(huán)+下標(biāo): ");
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();

        //foreach遍歷
        System.out.print("foreach遍歷: ");
        for (String ret : list) {
            System.out.print(ret+" ");
        }
        System.out.println();

        //使用迭代器
        System.out.print("迭代器遍歷: ");
        Iterator<String> iter = list.iterator();
        while (iter.hasNext()){
            String ret = iter.next();
            System.out.print(ret+" ");
        }
        System.out.println();
    }
}

4. ArrayList的模擬實(shí)現(xiàn)

package List;

import java.util.Arrays;

// 自定義的ArrayList類
public class MyArrayList {
    public int[] arr; // 用于存儲(chǔ)元素的數(shù)組
    public int size; // 記錄當(dāng)前數(shù)組中的元素個(gè)數(shù)
    public static final int Max = 10; // 默認(rèn)最大容量

    // 構(gòu)造方法，初始化數(shù)組
    public MyArrayList() {
        this.arr = new int[10];
    }

    // 打印元素
    public void display() {
        for (int i = 0; i < this.size; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // 增加元素
    public void add(int data) {
        if (isFull()) {
            arr = Arrays.copyOf(arr, arr.length * 2); // 如果數(shù)組已滿，擴(kuò)容為原來(lái)的兩倍
        }
        arr[size++] = data;
    }

    // 判斷數(shù)組是否已滿
    public boolean isFull() {
        if (size == Max) {
            return true;
        }
        return false;
    }

    // 檢查插入位置是否合法
    private void checkAddPos(int pos) {
        if (pos < 0 || pos > size) {
            throw new PosIndexNotLegalException("pos位置不合法");
        }
    }

    // 在指定位置插入元素
    public void add(int pos, int data) {
        try {
            checkAddPos(pos);
            if (isFull()) {
                arr = Arrays.copyOf(arr, 2 * arr.length); // 如果數(shù)組已滿，擴(kuò)容為原來(lái)的兩倍
            }
            for (int i = size - 1; i >= pos; i--) {
                arr[i + 1] = arr[i]; // 元素后移
            }
            arr[pos] = data; // 在指定位置插入新元素
            size++;
        } catch (PosIndexNotLegalException e) {
            e.printStackTrace();
        }
    }

    // 判斷是否包含某個(gè)元素
    public boolean contains(int toFind) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == toFind) {
                return true;
            }
        }
        return false;
    }

    // 查找某個(gè)元素對(duì)應(yīng)的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == toFind) {
                return i;
            }
        }
        return -1; // 如果找不到返回-1
    }

    // 獲取指定位置的元素
    public int get(int pos) {
        checkAddPos(pos);
        return arr[pos];
    }

    // 給指定位置的元素賦值
    public void set(int pos, int value) {
        checkAddPos(pos);
        arr[pos] = value;
    }

    // 刪除第一次出現(xiàn)的指定元素
    public void remove(int toRemove) {
        int index = indexOf(toRemove);
        if (index == -1) {
            System.out.println("沒(méi)有你要?jiǎng)h除的數(shù)字！");
            return;
        }
        for (int j = index; j < size; j++) {
            arr[j] = arr[j + 1]; // 元素前移
        }
        size--;
    }

    // 獲取順序表長(zhǎng)度
    public int size() {
        int ret = size;
        return ret;
    }

    // 清空順序表
    public void clear() {
        size = 0; // 將元素個(gè)數(shù)置為0，實(shí)現(xiàn)清空操作
    }
}

5. ArrayList的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

1. 隨機(jī)訪問(wèn)：由于 ArrayList 使用數(shù)組來(lái)存儲(chǔ)元素，可以通過(guò)索引快速訪問(wèn)元素，性能較好，時(shí)間復(fù)雜度為 O(1)。
2. 靈活的大小：ArrayList 的大小可以動(dòng)態(tài)調(diào)整，不需要預(yù)先指定數(shù)組大小，可以根據(jù)需求動(dòng)態(tài)增加或減少元素。

缺點(diǎn)：

1. 插入和刪除效率低：在 ArrayList 中間或開(kāi)頭插入或刪除元素時(shí)，需要移動(dòng)后續(xù)元素，時(shí)間復(fù)雜度為 O(n)，性能較差。
2. 內(nèi)存開(kāi)銷：ArrayList 在動(dòng)態(tài)擴(kuò)容時(shí)需要重新分配內(nèi)存并拷貝元素，可能會(huì)產(chǎn)生額外的內(nèi)存開(kāi)銷。

總結(jié)

ArrayList 適合需要頻繁隨機(jī)訪問(wèn)元素、對(duì)大小變化較為頻繁的場(chǎng)景，但在大量插入和刪除操作時(shí)性能較差。

(三)?LinkedList

1. LinkedList的介紹

在前面ArrayList我們知道，當(dāng)在ArrayList任意位置插入或者刪除元素時(shí)，就需要將后序元素整體往前或者往后搬移，時(shí)間復(fù)雜度為O(n)，效率比較低，因此ArrayList不適合做任意位置插入和刪除比較多的場(chǎng)景。因此：java 集合中又引入了LinkedList，即鏈表結(jié)構(gòu)。

LinkedList 是 Java 中的一個(gè)無(wú)頭雙向鏈表。實(shí)現(xiàn)，實(shí)現(xiàn)了 List 和 Deque 接口，LinkedList 內(nèi)部是使用無(wú)頭雙向循環(huán)鏈表。表來(lái)存儲(chǔ)元素，每個(gè)節(jié)點(diǎn)包含對(duì)前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)的引用。LinkedList 支持在任意位置進(jìn)行高效的插入和刪除操作，時(shí)間復(fù)雜度為 O(1)。無(wú)頭雙向鏈表結(jié)構(gòu)圖:

雙向鏈表的每個(gè)節(jié)點(diǎn)都有 3 個(gè)屬性：

1. data : 實(shí)際存放的內(nèi)容；

2. prev : 指向前一節(jié)點(diǎn)的指針；

3. next : 指向后一節(jié)點(diǎn)的指針。

實(shí)際中鏈表的結(jié)構(gòu)非常多樣，單向或者雙向, 帶頭或者不帶頭, 循環(huán)或者非循環(huán)

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們重點(diǎn)掌握兩種:

無(wú)頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如 哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

無(wú)頭雙向鏈表：在Java的集合框架庫(kù)中LinkedList底層實(shí)現(xiàn)就是無(wú)頭雙向循環(huán)鏈表。

2. LinkedList的常見(jiàn)方法和使用

LinkedList 類實(shí)現(xiàn)了 List 接口，因此它包含了 List 接口定義的所有方法，例如 add、remove、get、set 等。此外，LinkedList 還包含了一些特有的方法，如 addFirst、addLast等，用于在鏈表的開(kāi)頭或結(jié)尾進(jìn)行操作

常見(jiàn)方法

• boolean add(E e): 在鏈表的末尾添加元素。
• void addFirst(E e): 在鏈表的開(kāi)頭添加元素。
• void addLast(E e): 在鏈表的末尾添加元素。
• E get(int index): 獲取指定位置的元素。
• E set(int index, E element) 將下標(biāo) index 位置元素設(shè)置為 element
• boolean remove(): 刪除并返回鏈表的第一個(gè)元素。
• String removeFirst(): 刪除并返回鏈表的第一個(gè)元素。
• String removeLast(): 刪除并返回鏈表的最后一個(gè)元素。
• int size(): 獲取鏈表的大小。
• boolean contains(Object o): 判斷鏈表是否包含指定的元素。
• int indexOf(Object o): 返回指定元素在鏈表中第一次出現(xiàn)的位置。
• int lastIndexOf(Object o) 返回最后一個(gè) o 的下標(biāo)
• void clear() 清空

import java.util.LinkedList;
class Main {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

        // 添加元素
        linkedList.add("A");
        System.out.println("添加 'A' 后的鏈表: " + linkedList);
        linkedList.addFirst("B");
        System.out.println("在鏈表開(kāi)頭添加 'B' 后的鏈表: " + linkedList);
        linkedList.addLast("C");
        System.out.println("在鏈表末尾添加 'C' 后的鏈表: " + linkedList);

        // 獲取元素
        String elementAtIndex1 = linkedList.get(1);
        System.out.println("索引為 1 的元素: " + elementAtIndex1);

        // 設(shè)置元素
        linkedList.set(0, "D");
        System.out.println("將索引為 0 的元素設(shè)置為 'D' 后的鏈表: " + linkedList);

        // 刪除元素
        String removedElement = linkedList.remove();
        System.out.println("刪除的元素: " + removedElement);
        String removedFirst = linkedList.removeFirst();
        System.out.println("刪除的第一個(gè)元素: " + removedFirst);
        String removedLast = linkedList.removeLast();
        System.out.println("刪除的最后一個(gè)元素: " + removedLast);

        // 獲取鏈表大小
        int size = linkedList.size();
        System.out.println("鏈表的大小: " + size);

        // 判斷是否包含元素
        boolean contains = linkedList.contains("A");
        System.out.println("鏈表是否包含 'A': " + contains);

        // 獲取元素的索引
        int index = linkedList.indexOf("B");
        System.out.println("'B' 在鏈表中的索引: " + index);

        // 清空鏈表
        linkedList.clear();
        System.out.println("清空鏈表后的結(jié)果: " + linkedList);
    }
}

3. LinkedList的遍歷

可以使用foreach、迭代器來(lái)訪問(wèn)鏈表中的每個(gè)元素。?代碼如下:

import java.util.LinkedList;
import java.util.Iterator;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");

        // 使用迭代器遍歷
        Iterator<String> iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            String element = iterator.next();
            System.out.println("Element: " + element);
        }
        
        // 使用foreach遍歷
        for (String element : linkedList) {
            System.out.println("Element: " + element);
        }
    }
}

4. LinkedList的模擬實(shí)現(xiàn)

無(wú)頭單向非循環(huán)鏈表代碼如下:

public class SingleLinkedList {

    // 定義節(jié)點(diǎn)類
    static class Node {
        public int val;
        public Node next;

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

    public Node head; // 鏈表頭節(jié)點(diǎn)

    // 頭插法
    public void addFirst(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
        } else {
            node.next = head;
            head = node;
        }
    }

    // 尾插法
    public void addLast(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
            return;
        } else {
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    // 任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)
    public void addIndex(int index, int data) {
        checkIndex(index);
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        Node node = new Node(data);
        // 找到要插入的前一個(gè)位置
        Node cur = prevIndex(index - 1);
        node.next = cur.next;
        cur.next = node;
    }

    private void checkIndex(int index) {
        if (index < 0 || index > size()) {
            throw new IndexNotLegalException("index位置不合法！");
        }
    }

    private Node prevIndex(int index) {
        Node cur = head;
        while (index > 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

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

    // 刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
    public void remove(int key) {
        if (head == null) return;
        if (head.val == key) {
            head = head.next;
            return;
        }
        Node cur = head.next;
        Node prev = head;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                return;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
    }

    // 刪除所有值為key的節(jié)點(diǎn)
    public void removeAllKey(int key) {
        if (head == null) return;
        Node cur = head.next;
        Node prev = head;
        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;
        }
    }

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

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

    // 清空鏈表
    public void clear() {
        if (head == null) return;
        Node cur = head;
        while (cur != null) {
            Node curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        head = null;
    }
    

    // 一道練習(xí)題  -- 單鏈表的逆置
    // 遞歸.單鏈表的逆置
    public Node reverseList(Node head) {
        if (head == null) {
            return head;
        }
        if (head.next == null) {
            return head;
        }
        Node newHead = reverseList(head.next);
        head.next.next = head;
        // 要注意的是的下一個(gè)節(jié)點(diǎn)必須指向?。如果忽略了這一點(diǎn)，鏈表中會(huì)產(chǎn)生環(huán),所以每反轉(zhuǎn)一個(gè),要把原來(lái)下個(gè)結(jié)點(diǎn)置null;
        head.next = null;

        return newHead;

    }

    // 非遞歸.單鏈表的逆置
    public Node reverseList1() {
        Node cur = head;
        Node prev = null;
        while (cur != null) {
            Node nextCur = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nextCur;
        }
        return prev;
    }

}

無(wú)頭雙向循環(huán)鏈表的實(shí)現(xiàn)如下:

package MyLinkedList;

// 無(wú)頭雙向鏈表實(shí)現(xiàn)
public class MyTwoLinkedList {

    // 定義節(jié)點(diǎn)類
    static class ListNode {
        public int val;
        public ListNode next; //指向下一個(gè)節(jié)點(diǎn)
        public ListNode prev; //指向上一個(gè)節(jié)點(diǎn)

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

    public ListNode head; // 表示存儲(chǔ)當(dāng)前鏈表的頭節(jié)點(diǎn)的引用
    public ListNode last; // 尾節(jié)點(diǎn)

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

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

    // 尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            last = node;
            return;
        }
        last.next = node;
        node.prev = last;
        last = last.next;
    }

    // 根據(jù)索引查找節(jié)點(diǎn)
    private ListNode findIndex(int index) {
        ListNode cur = head;
        while (index > 0) {
            index--;
            cur = cur.next;
        }
        return cur;
    }

    // 任意位置插入，第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)
    public void addIndex(int index, int data) {
        ListNode node = new ListNode(data);
        if (index < 0 || index > this.size()) {
            throw new IndexNotLegalException("雙向鏈表index不合法！");
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        // 獲取到當(dāng)前的index位置的節(jié)點(diǎn)的地址
        ListNode cur = findIndex(index);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

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

    // 刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
    public void remove(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {
                    head = head.next;
                    if (head != null) { // 防止只有一個(gè)節(jié)點(diǎn)
                        head.prev = null;
                    }
                } else {
                    cur.prev.next = cur.next;
                    // 刪除的不是尾巴節(jié)點(diǎn)
                    if (last.val != key) {
                        cur.next.prev = cur.prev;
                    } else {
                        last = cur.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }

    // 刪除所有值為key的節(jié)點(diǎn)
    public void removeAllKey(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {
                    head = head.next;
                    if (head != null) { // 防止只有一個(gè)節(jié)點(diǎn)
                        head.prev = null;
                    }
                } else {
                    cur.prev.next = cur.next;
                    // 刪除的不是尾巴節(jié)點(diǎn)
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        // 刪除的是尾結(jié)點(diǎn)
                        last = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

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

    // 清空鏈表
    public void clear() {
        ListNode cur = head;
        while (cur != null) {
            ListNode nextCur = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = nextCur;
        }
        head = null;
        last = null;
    }
}

5. LinkedList的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

1. 插入和刪除操作效率高：在鏈表中插入和刪除元素的效率很高，只需要修改節(jié)點(diǎn)的指針，不需要移動(dòng)其他元素。
2. 靈活性：鏈表可以動(dòng)態(tài)地分配內(nèi)存空間，可以根據(jù)需要?jiǎng)討B(tài)地添加或刪除節(jié)點(diǎn)。

缺點(diǎn)：

1. 隨機(jī)訪問(wèn)效率低：鏈表中要想訪問(wèn)第k個(gè)元素，需要從頭節(jié)點(diǎn)開(kāi)始順序遍歷，時(shí)間復(fù)雜度為O(n)。
2. 占用空間多：鏈表中每個(gè)節(jié)點(diǎn)都需要額外的空間來(lái)存儲(chǔ)指針，占用的空間比數(shù)組大。
3. 不支持隨機(jī)訪問(wèn)：鏈表不支持通過(guò)下標(biāo)直接訪問(wèn)元素，只能通過(guò)指針進(jìn)行遍歷訪問(wèn)。

總結(jié)

LinkedList 適合需要頻繁插入和刪除操作、對(duì)隨機(jī)訪問(wèn)要求不高的場(chǎng)景，但在需要頻繁隨機(jī)訪問(wèn)元素時(shí)性能較差。

(四) ArrayList和LinkedList的區(qū)別

ArrayList 和 LinkedList 都是 Java 中的集合類，用于存儲(chǔ)一組元素。它們之間的主要區(qū)別在于底層的數(shù)據(jù)結(jié)構(gòu)和對(duì)元素的訪問(wèn)方式。

ArrayList 是基于數(shù)組實(shí)現(xiàn)的動(dòng)態(tài)數(shù)組，它提供了快速的隨機(jī)訪問(wèn)和遍歷。在 ArrayList 中，每個(gè)元素都有一個(gè)索引，可以通過(guò)索引快速訪問(wèn)元素，但在插入和刪除元素時(shí)需要移動(dòng)其他元素，因此插入和刪除操作的效率較低。

LinkedList 是基于鏈表實(shí)現(xiàn)的雙向鏈表，它提供了快速的插入和刪除操作。在 LinkedList 中，每個(gè)元素都包含對(duì)前一個(gè)元素和后一個(gè)元素的引用，因此插入和刪除操作的效率比較高。但是在訪問(wèn)元素時(shí)需要從頭或尾開(kāi)始遍歷，因此隨機(jī)訪問(wèn)的效率較低。

總結(jié)

如果需要頻繁進(jìn)行插入和刪除操作，可以選擇 LinkedList；如果需要頻繁進(jìn)行隨機(jī)訪問(wèn)和遍歷操作，可以選擇 ArrayList。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-809850.html

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