Java学习——ArrayList和LinkedList

03-01 1415阅读

Java集合框架提供了强大的数据结构，以满足日常编程的需求。其中，ArrayList和LinkedList是实现List接口的两种重要数据结构，它们在使用和性能上各有特点。本文将深入探讨这两种列表的内部工作原理、性能对比和适用场景，帮助你做出更合适的选择。

（图片来源网络，侵删）

ArrayList: 动态数组的力量

ArrayList是基于动态数组实现的，这意味着它能够根据需要自动调整容量。这种灵活性使得ArrayList成为最受欢迎的List实现之一。

内部工作原理

当ArrayList中的元素超过当前容量时，它会创建一个新的数组，通常是原来容量的1.5倍，然后将旧数组中的元素复制到新数组中。这个过程称为“动态扩容”。

性能分析

随机访问：由于直接基于数组，ArrayList提供了快速的随机访问能力，时间复杂度为O(1)。
添加/删除元素：在末尾添加元素通常很快（摊销O(1)）。然而，在列表中间或开始处添加或删除元素需要移动后续的元素，时间复杂度为O(n)。
使用场景

ArrayList适用于频繁随机访问元素的场景，以及在列表末尾添加元素的操作较多时。

LinkedList: 链表的灵活性

与ArrayList相比，LinkedList基于双向链表实现，每个元素（即节点）包含数据和两个引用，分别指向前一个和后一个元素。

内部工作原理

LinkedList的每个元素都是一个独立的对象，所有元素通过引用链接在一起。这种结构使得在任何位置添加或删除元素都非常快捷，因为这仅涉及到改变节点之间的引用。

性能分析
- 随机访问：访问特定索引的元素需要从头或尾开始遍历，时间复杂度为O(n)。
- 添加/删除元素：在任何位置插入或删除元素的时间复杂度为O(1)，因为这只需要修改少量的引用。
  使用场景
  
  LinkedList适用于频繁在列表中插入或删除元素的场景，特别是在列表的开始或中间。
  
  性能对比
  
  特性 ArrayList LinkedList
  随机访问 O(1) O(n)
  在末尾添加元素摊销O(1) O(1)
  在开头添加元素 O(n) O(1)
  在中间添加元素 O(n) O(n)（需要遍历）
  总结
  
  ArrayList和LinkedList各有优缺点，选择哪一个取决于你的具体需求：
  - 如果你需要频繁随机访问列表中的元素，或在列表末尾添加元素的操作较多，ArrayList是更好的选择。
  - 如果你的应用需要频繁在列表的开始或中间插入或删除元素，LinkedList可能更适合。
    使用方法
    
    ArrayList和LinkedList都实现了List接口，因此它们提供了很多相同的方法来操作集合中的元素。以下是一些常用的方法和使用示例，展示了如何在Java中使用ArrayList和LinkedList。
```
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Iterator;
public class ListExample {
    public static void main(String[] args) {
        // 创建ArrayList和LinkedList
        List arrayList = new ArrayList();
        List linkedList = new LinkedList();
        // 添加元素
        arrayList.add("Apple");
        linkedList.add("Banana");
        arrayList.add(0, "Strawberry");
        linkedList.add(1, "Blueberry");
        // 访问元素
        System.out.println("First element of arrayList: " + arrayList.get(0)); // 输出 Strawberry
        System.out.println("Second element of linkedList: " + linkedList.get(1)); // 输出 Blueberry
        // 修改元素
        arrayList.set(0, "Orange");
        System.out.println("Modified first element of arrayList: " + arrayList.get(0)); // 输出 Orange
        // 删除元素
        arrayList.remove("Orange");
        linkedList.remove(1);
        // 列表大小
        System.out.println("Size of arrayList: " + arrayList.size()); // 输出列表的大小
        System.out.println("Size of linkedList: " + linkedList.size()); // 输出列表的大小
        // 遍历列表 - 使用for-each循环
        System.out.println("ArrayList elements:");
        for (String fruit : arrayList) {
            System.out.println(fruit);
        }
        System.out.println("LinkedList elements:");
        // 使用迭代器
        Iterator iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            String fruit = iterator.next();
            System.out.println(fruit);
        }
        // 判断列表是否包含某元素
        if (linkedList.contains("Banana")) {
            System.out.println("LinkedList contains Banana");
        }
        // 清空列表
        arrayList.clear();
        linkedList.clear();
        // 检查清空后的大小
        System.out.println("Size of arrayList after clear: " + arrayList.size());
        System.out.println("Size of linkedList after clear: " + linkedList.size());
    }
}
```
    这个示例代码首先创建了一个ArrayList和一个LinkedList，然后展示了如何向列表中添加元素、访问和修改元素、删除元素、获取列表大小、遍历列表（使用for-each循环和迭代器）、判断列表是否包含某个元素以及如何清空列表。最后，它还输出了清空列表后的大小，以确认列表已被清空。
    
    通过这个示例，你可以看到ArrayList和LinkedList提供的操作大部分是相同的，但它们在内部实现和性能方面有所不同。选择哪一种类型的列表取决于你的具体需求，如频繁的随机访问操作更适合使用ArrayList，而频繁的插入和删除操作（特别是在列表的开头或中间）则LinkedList更有优势。
    
    在LinkedList中访问特定位置的元素可以通过get(int index)方法实现。这个方法返回链表中指定位置的元素。需要注意的是，由于LinkedList是基于链表实现的，因此每次调用get(int index)方法时，它都会从链表的头部或尾部开始遍历，直到到达指定的位置。这意味着访问链表中间的元素可能会比访问头部或尾部的元素花费更多的时间。
    
    性能考虑
    
    虽然get(int index)方法提供了一种直接通过索引访问LinkedList中元素的方式，但在使用时应该谨慎，特别是在循环中反复调用此方法可能会导致性能问题。这是因为每次调用get(int index)都需要从头部或尾部开始遍历链表，其时间复杂度为O(n)，在列表较大时可能会显著影响性能。
    
    更高效的遍历方法
    
    如果你需要遍历LinkedList并对每个元素进行操作，使用迭代器（Iterator）或增强for循环通常是更高效的选择，因为它们可以顺序访问链表中的每个元素而无需每次都重新遍历链表。