LinkedList与链表

发布于：2025-07-27 ⋅ 阅读:(23) ⋅ 点赞:(0)

LinkedList与链表

文章目录

ArrayList的缺陷

因为ArrayList底层是一段连续的空间，ArrayList 适合读多写少、随机访问频繁、单线程环境的场景，但在频繁插入 / 删除中间元素、多线程并发、存储大量基本数据类型等场景下，需考虑其缺陷并选择更合适的集合（如 LinkedList、CopyOnWriteArrayList 等）

具体例子：
场景：向 ArrayList中间频繁插入元素，对比 LinkedList 的性能差异

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ArrayListDefectDemo {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        int size = 10000; // 数据量

        // 向ArrayList中间插入元素
        long start = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            arrayList.add(0, i); // 每次在头部（索引0）插入
        }
        long arrayTime = System.currentTimeMillis() - start;

        // 向LinkedList中间插入元素
        start = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            linkedList.add(0, i); // 同样在头部插入
        }
        long linkedTime = System.currentTimeMillis() - start;

        System.out.println("ArrayList头部插入耗时：" + arrayTime + "ms");
        System.out.println("LinkedList头部插入耗时：" + linkedTime + "ms");
    }
}

运行结果：

ArrayList头部插入耗时：235ms
LinkedList头部插入耗时：3ms

总结：
1.中间插入 / 删除频繁 → 用 LinkedList 更合适
2.多线程场景 → 用 CopyOnWriteArrayList 或同步集合

链表

链表概念及结构

链表是一种常见的线性数据结构，与数组不同，它的元素（称为 “节点”）在内存中非连续存储，而是通过指针（或引用）相互连接，形成链式结构。这种特性让链表在插入、删除操作上更灵活，但随机访问效率较低

常见链表类型：

链表类型 结构特点 遍历方向 插入/删除操作 典型应用场景
单链表 每个节点含1个指针域（指向下一个节点），尾节点指针为null 单向（头→尾） 只需修改1个相邻节点的指针，时间复杂度O(1) 实现栈、队列、简单链表结构
双向链表 每个节点含2个指针域（prev指向上一个节点，next指向下一个节点），头节点prev为null，尾节点next为null 双向（头→尾/尾→头） 需同时修改prev和next指针，时间复杂度O(1) 需双向遍历的场景（如LinkedList）
单循环链表 基于单链表，尾节点指针不指向null，而是指向头节点，形成环形结构 循环遍历 同单链表，需注意边界判断（避免无限循环） 约瑟夫问题、循环队列
双循环链表 基于双向链表，头节点prev指向尾节点，尾节点next指向头节点，形成环形结构 双向循环遍历 同双向链表，支持从任意节点开始循环访问 复杂循环场景（如操作系统进程调度）

注意⚠️：
1.链式结构在逻辑上是连续的，但是在物理上不一定是连续的
2.现实中的节点一般都是从堆上申请出来的
3.从堆上申请的空间是按照一定的策略来分配的，两次申请的空间，可能是连续的也可能不连续

链表的实现

import java.util.NoSuchElementException;

// 单链表节点定义
class ListNode {
    int val; // 数据域
    ListNode next; // 指针域（指向下一个节点）

    // 构造方法
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

// 单链表实现类
public class SinglyLinkedList {
    private ListNode head; // 头节点
    private int size; // 链表长度（元素个数）

    // 初始化空链表
    public SinglyLinkedList() {
        head = null;
        size = 0;
    }

    /**
     * 1. 在链表头部插入元素
     * 时间复杂度：O(1)
     */
    public void addFirst(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head; // 新节点指向原头节点
        head = newNode; // 头节点更新为新节点
        size++;
    }

    /**
     * 2. 在链表尾部插入元素
     * 时间复杂度：O(n)（需遍历到尾节点）
     */
    public void addLast(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) { // 空链表直接插入头部
            head = newNode;
        } else {
            ListNode cur = head;
            while (cur.next != null) { // 遍历到尾节点
                cur = cur.next;
            }
            cur.next = newNode; // 尾节点指向新节点
        }
        size++;
    }

    /**
     * 3. 在指定索引位置插入元素（索引从0开始）
     * 时间复杂度：O(n)（需遍历到目标位置的前一个节点）
     */
    public void add(int index, int val) {
        // 校验索引合法性
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("索引越界：" + index);
        }
        if (index == 0) { // 头部插入（复用addFirst）
            addFirst(val);
            return;
        }
        if (index == size) { // 尾部插入（复用addLast）
            addLast(val);
            return;
        }
        // 找到索引的前一个节点
        ListNode prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = prev.next; // 新节点指向prev的下一个节点
        prev.next = newNode; // prev指向新节点
        size++;
    }

    /**
     * 4. 删除头部元素
     * 时间复杂度：O(1)
     */
    public int removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("链表为空，无法删除");
        }
        int val = head.val;
        head = head.next; // 头节点后移一位
        size--;
        return val;
    }

    /**
     * 5. 删除尾部元素
     * 时间复杂度：O(n)（需遍历到倒数第二个节点）
     */
    public int removeLast() {
        if (head == null) {
            throw new NoSuchElementException("链表为空，无法删除");
        }
        if (size == 1) { // 只有一个节点（直接删除头部）
            return removeFirst();
        }
        // 找到倒数第二个节点
        ListNode prev = head;
        while (prev.next.next != null) {
            prev = prev.next;
        }
        int val = prev.next.val;
        prev.next = null; // 断开与尾节点的连接
        size--;
        return val;
    }

    /**
     * 6. 删除指定索引位置的元素
     * 时间复杂度：O(n)
     */
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界：" + index);
        }
        if (index == 0) { // 删除头部（复用removeFirst）
            return removeFirst();
        }
        // 找到索引的前一个节点
        ListNode prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        int val = prev.next.val;
        prev.next = prev.next.next; // 跳过待删除节点
        size--;
        return val;
    }

    /**
     * 7. 修改指定索引位置的元素
     * 时间复杂度：O(n)
     */
    public void set(int index, int val) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界：" + index);
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.val = val; // 更新值
    }

    /**
     * 8. 查找指定索引位置的元素
     * 时间复杂度：O(n)
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界：" + index);
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    /**
     * 9. 查找元素首次出现的索引（不存在返回-1）
     * 时间复杂度：O(n)
     */
    public int indexOf(int val) {
        ListNode cur = head;
        for (int i = 0; i < size; i++) {
            if (cur.val == val) {
                return i;
            }
            cur = cur.next;
        }
        return -1;
    }

    /**
     * 10. 判断链表是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 11. 获取链表长度
     */
    public int size() {
        return size;
    }

    /**
     * 12. 打印链表元素（以"[a,b,c]"格式）
     */
    public void print() {
        if (isEmpty()) {
            System.out.println("[]");
            return;
        }
        StringBuilder sb = new StringBuilder("[");
        ListNode cur = head;
        while (cur != null) {
            sb.append(cur.val);
            if (cur.next != null) {
                sb.append(",");
            }
            cur = cur.next;
        }
        sb.append("]");
        System.out.println(sb.toString());
    }

    // 测试方法
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.addLast(1);
        list.addLast(2);
        list.addFirst(0);
        list.add(2, 100); // 在索引2插入100
        list.print(); // 输出：[0,1,100,2]

        System.out.println("索引1的值：" + list.get(1)); // 输出：1
        System.out.println("100的索引：" + list.indexOf(100)); // 输出：2

        list.set(3, 200);
        list.print(); // 输出：[0,1,100,200]

        list.remove(2); // 删除索引2的100
        list.removeFirst();
        list.print(); // 输出：[1,200]

        System.out.println("链表长度：" + list.size()); // 输出：2
    }
}

方法说明：

操作类型 方法名 功能描述 时间复杂度 关键说明
插入操作 addFirst(val) 在链表头部插入元素 O(1) 直接修改头节点指针，效率最高
插入操作 addLast(val) 在链表尾部插入元素 O(n) 需遍历到尾节点，再添加新节点
插入操作 add(index, val) 在指定索引位置插入元素 O(n) 需先找到目标位置的前一个节点，再修改指针
删除操作 removeFirst() 删除链表头部元素 O(1) 直接将头节点后移一位
删除操作 removeLast() 删除链表尾部元素 O(n) 需遍历到倒数第二个节点，断开与尾节点连接
删除操作 remove(index) 删除指定索引位置的元素 O(n) 需先定位到目标位置的前一个节点，再跳过该节点
查询与修改 get(index) 获取指定索引位置的元素值 O(n) 需从头遍历到目标节点
查询与修改 set(index, val) 修改指定索引位置的元素值 O(n) 需从头遍历到目标节点，再更新值
查询与修改 indexOf(val) 查找元素首次出现的索引（不存在返回-1） O(n) 需遍历整个链表对比元素值

LinkedList模拟实现

import java.util.NoSuchElementException;

// 链表节点类
class ListNode {
    int val;
    ListNode next;
    
    // 构造方法
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

// 单链表类
public class SinglyLinkedList {
    // 头节点
    private ListNode head;
    // 链表长度
    private int size;
    
    // 构造方法，初始化空链表
    public SinglyLinkedList() {
        head = null;
        size = 0;
    }
    
    // 1. 在链表头部添加元素
    public void addFirst(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    // 2. 在链表尾部添加元素
    public void addLast(int val) {
        ListNode newNode = new ListNode(val);
        
        // 如果链表为空，直接让头节点指向新节点
        if (head == null) {
            head = newNode;
        } else {
            // 找到最后一个节点
            ListNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }
    
    // 3. 在指定索引位置添加元素
    public void add(int index, int val) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("索引越界: " + index);
        }
        
        // 索引为0，相当于在头部添加
        if (index == 0) {
            addFirst(val);
            return;
        }
        
        // 索引为size，相当于在尾部添加
        if (index == size) {
            addLast(val);
            return;
        }
        
        // 找到要插入位置的前一个节点
        ListNode prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        
        // 创建新节点并插入
        ListNode newNode = new ListNode(val);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }
    
    // 4. 删除头节点
    public int removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException("链表为空，无法删除");
        }
        
        int val = head.val;
        head = head.next;
        size--;
        return val;
    }
    
    // 5. 删除尾节点
    public int removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException("链表为空，无法删除");
        }
        
        // 如果只有一个节点
        if (head.next == null) {
            int val = head.val;
            head = null;
            size--;
            return val;
        }
        
        // 找到倒数第二个节点
        ListNode prev = head;
        while (prev.next.next != null) {
            prev = prev.next;
        }
        
        int val = prev.next.val;
        prev.next = null;
        size--;
        return val;
    }
    
    // 6. 删除指定索引位置的节点
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界: " + index);
        }
        
        // 索引为0，相当于删除头节点
        if (index == 0) {
            return removeFirst();
        }
        
        // 找到要删除节点的前一个节点
        ListNode prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        
        int val = prev.next.val;
        prev.next = prev.next.next;
        size--;
        return val;
    }
    
    // 7. 查找指定索引位置的元素
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界: " + index);
        }
        
        ListNode current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.val;
    }
    
    // 8. 修改指定索引位置的元素
    public void set(int index, int val) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界: " + index);
        }
        
        ListNode current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        current.val = val;
    }
    
    // 9. 查找元素的索引
    public int indexOf(int val) {
        ListNode current = head;
        int index = 0;
        
        while (current != null) {
            if (current.val == val) {
                return index;
            }
            current = current.next;
            index++;
        }
        
        // 未找到返回-1
        return -1;
    }
    
    // 10. 判断链表是否包含某个元素
    public boolean contains(int val) {
        return indexOf(val) != -1;
    }
    
    // 11. 反转链表
    public void reverse() {
        // 空链表或只有一个节点，无需反转
        if (head == null || head.next == null) {
            return;
        }
        
        ListNode prev = null;
        ListNode current = head;
        ListNode next = null;
        
        while (current != null) {
            next = current.next;  // 保存下一个节点
            current.next = prev;  // 反转指针
            prev = current;       // 移动prev
            current = next;       // 移动current
        }
        
        head = prev;  // 更新头节点
    }
    
    // 12. 判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    
    // 13. 获取链表长度
    public int size() {
        return size;
    }
    
    // 14. 清空链表
    public void clear() {
        head = null;
        size = 0;
    }
    
    // 15. 打印链表元素
    public void print() {
        if (isEmpty()) {
            System.out.println("链表为空");
            return;
        }
        
        StringBuilder sb = new StringBuilder();
        ListNode current = head;
        
        while (current != null) {
            sb.append(current.val);
            if (current.next != null) {
                sb.append(" -> ");
            }
            current = current.next;
        }
        
        System.out.println(sb.toString());
    }
    
    // 测试方法
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        
        // 测试添加元素
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addFirst(0);
        list.add(2, 5);
        System.out.print("添加元素后: ");
        list.print();  // 输出: 0 -> 1 -> 5 -> 2 -> 3
        
        // 测试获取和修改元素
        System.out.println("索引2处的元素: " + list.get(2));  // 输出: 5
        list.set(2, 10);
        System.out.print("修改元素后: ");
        list.print();  // 输出: 0 -> 1 -> 10 -> 2 -> 3
        
        // 测试查找元素
        System.out.println("元素10的索引: " + list.indexOf(10));  // 输出: 2
        System.out.println("是否包含元素2: " + list.contains(2));  // 输出: true
        
        // 测试反转链表
        list.reverse();
        System.out.print("反转后: ");
        list.print();  // 输出: 3 -> 2 -> 10 -> 1 -> 0
        
        // 测试删除元素
        list.remove(2);
        System.out.print("删除索引2处的元素后: ");
        list.print();  // 输出: 3 -> 2 -> 1 -> 0
        
        list.removeFirst();
        list.removeLast();
        System.out.print("删除头节点和尾节点后: ");
        list.print();  // 输出: 2 -> 1
        
        // 测试链表长度
        System.out.println("链表长度: " + list.size());  // 输出: 2
    }
}

代码解析

这个单链表实现包含了以下核心部分：
1.节点类（ListNode）：
每个节点包含一个值（val）和一个指向下一个节点的引用（next）

2.链表类（SinglyLinkedList）：
包含头节点（head）和链表长度（size）两个成员变量，实现了一系列常用操作方法

3.主要方法说明：
增：addFirst()、addLast()、add()
删：removeFirst()、removeLast()、remove()
改：set()
查：get()、indexOf()、contains()
其他：reverse()（反转链表）、isEmpty()、size()等

4.反转链表的实现：
使用迭代方式，通过三个指针（prev、current、next）完成反转
时间复杂度 O (n)，空间复杂度 O (1)

LinkedList的使用

什么是LinkedList

LinkedList 是 Java 集合框架中一个重要的实现类，基于双向链表数据结构实现，继承自 AbstractSequentialList 并实现了 List、Deque 等接口。它不仅可以作为普通链表使用，还能当作队列（Queue）、双端队列（Deque）或栈（Stack）使用，功能十分灵活

注意⚠️：
1.LinkedList实现了List接口
2.LinkedList底层使用了双向链表
3.LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4.LinkedList在任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5.LinkedList比较适合任意位置插入的场景

LinkedList的使用

构造方法和常见使用方法：

类型 方法声明 功能描述
构造方法 LinkedList() 创建一个空的 LinkedList
LinkedList(Collection<? extends E> c) 通过已有的集合创建 LinkedList，包含集合中的所有元素
添加元素 boolean add(E e) 在链表尾部添加元素，成功返回 true
void add(int index, E element) 在指定索引位置插入元素
boolean addAll(Collection<? extends E> c) 将集合中的所有元素添加到链表尾部
void addFirst(E e) 在链表头部添加元素
void addLast(E e) 在链表尾部添加元素（与 add(E e) 功能相同）
boolean offer(E e) 等价于 add(E e)，在尾部添加元素，成功返回 true
boolean offerFirst(E e) 等价于 addFirst(E e)，在头部添加元素，成功返回 true
boolean offerLast(E e) 等价于 addLast(E e)，在尾部添加元素，成功返回 true
获取元素 E get(int index) 返回指定索引位置的元素
E getFirst() 返回链表头部元素（若为空，抛出 NoSuchElementException）
E getLast() 返回链表尾部元素（若为空，抛出 NoSuchElementException）
E peek() 等价于 peekFirst()，返回头部元素（若为空，返回 null）
E peekFirst() 返回头部元素（若为空，返回 null）
E peekLast() 返回尾部元素（若为空，返回 null）
修改元素 E set(int index, E element) 修改指定索引位置的元素，返回被替换的旧元素
删除元素 E remove() 等价于 removeFirst()，删除并返回头部元素（若为空，抛出异常）
E remove(int index) 删除指定索引位置的元素，返回被删除的元素
boolean remove(Object o) 删除第一个与 o 相等的元素，成功返回 true
E removeFirst() 删除并返回头部元素（若为空，抛出 NoSuchElementException）
E removeLast() 删除并返回尾部元素（若为空，抛出 NoSuchElementException）
E poll() 等价于 pollFirst()，删除并返回头部元素（若为空，返回 null）
E pollFirst() 删除并返回头部元素（若为空，返回 null）
E pollLast() 删除并返回尾部元素（若为空，返回 null）
查找判断 int indexOf(Object o) 返回第一个与 o 相等的元素的索引，未找到返回 -1
int lastIndexOf(Object o) 返回最后一个与 o 相等的元素的索引，未找到返回 -1
boolean contains(Object o) 判断链表是否包含元素 o，包含返回 true

具体例子：

import java.util.LinkedList;
import java.util.ArrayList;
import java.util.NoSuchElementException;

public class LinkedListMethodsDemo {
    public static void main(String[] args) {
        // 1. 构造方法示例
        LinkedList<String> list = new LinkedList<>(); // 空构造
        ArrayList<String> arrList = new ArrayList<>();
        arrList.add("Java");
        arrList.add("Python");
        LinkedList<String> listFromCol = new LinkedList<>(arrList); // 从集合构造
        System.out.println("从集合构造的LinkedList: " + listFromCol);


        // 2. 添加元素方法
        list.add("Apple"); // 尾部添加
        list.add(0, "Banana"); // 指定索引添加
        list.addAll(listFromCol); // 添加另一个集合
        list.addFirst("Grape"); // 头部添加
        list.addLast("Orange"); // 尾部添加
        list.offer("Mango"); // 等价于add()
        list.offerFirst("Pineapple"); // 等价于addFirst()
        System.out.println("添加元素后: " + list);


        // 3. 获取元素方法
        System.out.println("get(2)获取索引2的元素: " + list.get(2));
        System.out.println("getFirst()获取头部元素: " + list.getFirst());
        System.out.println("getLast()获取尾部元素: " + list.getLast());
        System.out.println("peek()获取头部元素: " + list.peek());
        System.out.println("peekLast()获取尾部元素: " + list.peekLast());


        // 4. 修改元素方法
        String oldVal = list.set(3, "Strawberry"); // 修改索引3的元素
        System.out.println("修改前的值: " + oldVal + "，修改后列表: " + list);


        // 5. 删除元素方法
        list.remove(1); // 删除索引1的元素
        list.remove("Apple"); // 删除指定元素
        String first = list.removeFirst(); // 删除头部元素
        String last = list.removeLast(); // 删除尾部元素
        System.out.println("删除的头部元素: " + first + "，删除的尾部元素: " + last);
        System.out.println("删除后列表: " + list);
        String polled = list.poll(); // 等价于removeFirst()
        System.out.println("poll()删除的元素: " + polled + "，操作后列表: " + list);


        // 6. 查找判断方法
        System.out.println("Java的索引位置: " + list.indexOf("Java"));
        System.out.println("是否包含Python: " + list.contains("Python"));
        System.out.println("最后一个Python的索引: " + list.lastIndexOf("Python"));
    }
}

LinkedList的遍历

各遍历方式对比及注意事项：

遍历方式 特点与适用场景 注意事项
普通 for 循环（索引） 通过 get(index) 访问，适合需要索引的场景 效率低（每次 get(index) 需从头遍历），不推荐
增强 for 循环（foreach） 代码简洁，适合只读遍历 不能修改集合（添加 / 删除会抛异常）
Iterator 支持在遍历中安全删除元素 只能正向遍历
ListIterator 支持双向遍历（向前 / 向后），可在遍历中修改元素 功能最强大，适合复杂遍历需求
forEach()（Lambda） Java 8+ 特性，代码简洁，适合函数式编程风格 不能修改集合结构（添加 / 删除） 
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

public class LinkedListTraversal {
    public static void main(String[] args) {
        // 创建并初始化LinkedList
        LinkedList<String> fruits = new LinkedList<>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");
        fruits.add("Date");
        System.out.println("原始链表: " + fruits);


        // 1. 普通for循环（通过索引遍历）
        System.out.println("\n1. 普通for循环遍历:");
        for (int i = 0; i < fruits.size(); i++) {
            System.out.print(fruits.get(i) + " ");
        }


        // 2. 增强for循环（foreach）
        System.out.println("\n\n2. 增强for循环遍历:");
        for (String fruit : fruits) {
            System.out.print(fruit + " ");
        }


        // 3. 迭代器（Iterator）
        System.out.println("\n\n3. Iterator遍历:");
        Iterator<String> iterator = fruits.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }


        // 4. 列表迭代器（ListIterator）- 支持双向遍历
        System.out.println("\n\n4. ListIterator双向遍历:");
        System.out.print("正向遍历: ");
        ListIterator<String> listIterator = fruits.listIterator();
        while (listIterator.hasNext()) {
            System.out.print(listIterator.next() + " ");
        }

        System.out.print("\n反向遍历: ");
        while (listIterator.hasPrevious()) {
            System.out.print(listIterator.previous() + " ");
        }


        // 5. forEach()方法（Java 8+，使用Lambda表达式）
        System.out.println("\n\n5. forEach()方法遍历:");
        fruits.forEach(fruit -> System.out.print(fruit + " "));


        // 6. 迭代器遍历并删除元素（安全删除方式）
        System.out.println("\n\n6. 迭代器遍历并删除元素:");
        Iterator<String> iter = fruits.iterator();
        while (iter.hasNext()) {
            String fruit = iter.next();
            if (fruit.equals("Banana")) {
                iter.remove(); // 安全删除当前元素
            }
        }
        System.out.println("删除Banana后: " + fruits);
    }
}

ArrayList和LinkedList区别

以下是ArrayList和LinkedList的主要区别，通过表格形式呈现：

比较维度 ArrayList LinkedList
底层数据结构 基于动态数组（Object[]）实现 基于双向链表（JDK 1.6 及之前为循环双向链表）
随机访问性能 优秀，通过索引直接访问，时间复杂度O(1) 较差，需从头 / 尾遍历到目标位置，时间复杂度O(n)
插入 / 删除性能 中间插入 / 删除需移动元素，时间复杂度O(n) 中间插入 / 删除只需修改指针，时间复杂度O(1)（已知前驱节点时）
内存占用 内存连续，浪费较少（主要是扩容预留空间） 每个节点需存储前驱 / 后继指针，内存开销更大
扩容机制 容量不足时自动扩容（默认扩容为原容量的1.5倍） 无固定容量，无需扩容
迭代效率 普通 for 循环（索引遍历）效率高 迭代器（Iterator）遍历效率高
适用场景 频繁随机访问、少量插入 / 删除（多在尾部） 频繁插入 / 删除（多在中间）、较少随机访问
线程安全性 非线程安全 非线程安全
实现的接口 实现List接口 实现List和Deque接口（可作为双端队列使用）
特有方法 无特殊方法 提供addFirst()、addLast()、removeFirst()等双端队列操作方法

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布