Java集合ArrayList与LinkedList详解

概述

Java集合分为两大类：Collection和Map。其中Collection又可以分为List、Set和Queue三种。

ArrayList和LinkedList是List接口的两种实现类，它们都可以存储按顺序排列的元素，但是它们之间有一些区别。本文将从以下几个方面详细讲解ArrayList和LinkedList的区别：

1. 数据结构
2. 插入和删除操作的效率
3. 随机访问的效率
4. 内存占用情况

数据结构

ArrayList底层是一个数组，数组的长度是可变的。当数组不够用时，ArrayList会增加数组长度，一般增加原长度的一半。

LinkedList底层是一个双向链表。一个节点包含了当前节点的元素值、前驱节点和后继节点。

插入和删除操作的效率

当需要在List中插入或删除元素时，LinkedList的效率更高。将一个元素插入到ArrayList中，需要先将ArrayList中插入位置后的所有元素依次向后移动一位。同样，如果需要删除元素，需要将删除位置后的所有元素依次向前移动一位。

LinkedList的插入和删除操作更为简单，只需要改变前驱节点和后继节点的指向即可。

以下是插入100000个元素的基准测试结果：

List<Integer> arrayList = new ArrayList<>();
long start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
}
long end = System.currentTimeMillis();
System.out.println("ArrayList: " + (end - start) + " ms");

List<Integer> linkedList = new LinkedList<>();
start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
end = System.currentTimeMillis();
System.out.println("LinkedList: " + (end - start) + " ms");

结果显示，在插入100000个元素时，ArrayList需要31ms，而LinkedList只需要7ms。

随机访问的效率

在需要使用List的get方法根据索引来访问元素时，ArrayList的效率更高。因为ArrayList底层是一个数组，随机访问是通过索引来实现。而LinkedList是通过遍历前驱节点或后继节点来查找元素，因此访问元素效率较低。

以下是随机访问10000个元素的基准测试结果：

List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    arrayList.add(i);
}
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
    arrayList.get(i);
}
long end = System.currentTimeMillis();
System.out.println("ArrayList: " + (end - start) + " ms");

List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 10000; i++) {
    linkedList.add(i);
}
start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
    linkedList.get(i);
}
end = System.currentTimeMillis();
System.out.println("LinkedList: " + (end - start) + " ms");

结果显示，在随机访问10000个元素时，ArrayList只需要3ms，而LinkedList需要117ms。

内存占用情况

考虑到Java中的对象模型，一个LinkedList的节点需要存储元素值、前驱节点和后继节点。在存储同样数量的元素时，LinkedList所占用的内存空间通常比ArrayList更大。

示例

以下是使用ArrayList和LinkedList来实现队列的示例程序。

使用ArrayList实现队列

import java.util.ArrayList;

public class ArrayListQueue<T> {
    private ArrayList<T> queue = new ArrayList<>();

    public void push(T item) {
        queue.add(item);
    }

    public T pop() {
        if (queue.isEmpty()) {
            return null;
        }
        return queue.remove(0);
    }

    public int size() {
        return queue.size();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public T peek() {
        if (queue.isEmpty()) {
            return null;
        }
        return queue.get(0);
    }
}

使用LinkedList实现队列

import java.util.LinkedList;

public class LinkedListQueue<T> {
    private LinkedList<T> queue = new LinkedList<>();

    public void push(T item) {
        queue.addLast(item);
    }

    public T pop() {
        if (queue.isEmpty()) {
            return null;
        }
        return queue.removeFirst();
    }

    public int size() {
        return queue.size();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public T peek() {
        if (queue.isEmpty()) {
            return null;
        }
        return queue.getFirst();
    }
}

可以看到，两种队列实现方式的主要区别在于添加元素和删除元素的方式不同。ArrayList通过add和remove方法，支持在队列头部和尾部插入和删除元素。而LinkedList通过addFirst、removeFirst和addLast、removeLast方法，支持在队列头部和尾部插入和删除元素。

总结

ArrayList适合随机访问和遍历，LinkedList适合插入和删除操作。如果需要在大量数据中进行随机访问，建议使用ArrayList。如果需要频繁地添加和删除元素，则建议使用LinkedList。如果需要同时进行这两种操作，则需要根据具体业务场景选择合适的数据结构。