Java集合框架：ArrayList和LinkedList性能对比示例

原创雨点打透心脏的1/2处 2024-11-08 14:12 27阅读 0赞

Java集合框架中的`ArrayList`和`LinkedList`是两种常用的列表实现，它们在不同的操作下性能表现不同。以下是一些基本的性能对比示例：

###1.随机访问- **ArrayList**：在随机访问时，`ArrayList`的性能通常优于`LinkedList`。因为`ArrayList`是基于动态数组实现的，所以访问元素时可以直接通过索引访问，时间复杂度为O(1)。
- **LinkedList**：`LinkedList`是基于双向链表实现的，随机访问时需要从头节点开始遍历到指定位置，时间复杂度为O(n)。

###2.插入和删除- **ArrayList**：在列表中间插入或删除元素时，`ArrayList`需要移动插入点之后的所有元素，时间复杂度为O(n)。
- **LinkedList**：`LinkedList`在列表中间插入或删除元素时，只需要改变节点的指针，时间复杂度为O(1)。

###3.内存占用- **ArrayList**：`ArrayList`的内存占用通常比`LinkedList`小，因为它不需要存储额外的指针。
- **LinkedList**：每个节点都需要存储两个指针（指向前一个节点和后一个节点），所以内存占用更大。

### 示例代码以下是一些简单的Java代码示例，展示`ArrayList`和`LinkedList`在不同操作下的性能对比：

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

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

//测试添加元素 long startTime = System.currentTimeMillis();
 for (int i =0; i < size; i++) {
 arrayList.add(i);
 }
 long endTime = System.currentTimeMillis();
 System.out.println("ArrayList add: " + (endTime - startTime) + "ms");

startTime = System.currentTimeMillis();
 for (int i =0; i < size; i++) {
 linkedList.add(i);
 }
 endTime = System.currentTimeMillis();
 System.out.println("LinkedList add: " + (endTime - startTime) + "ms");

//测试随机访问 startTime = System.currentTimeMillis();
 for (int i =0; i < size; i++) {
 arrayList.get(i);
 }
 endTime = System.currentTimeMillis();
 System.out.println("ArrayList get: " + (endTime - startTime) + "ms");

startTime = System.currentTimeMillis();
 for (int i =0; i < size; i++) {
 linkedList.get(i);
 }
 endTime = System.currentTimeMillis();
 System.out.println("LinkedList get: " + (endTime - startTime) + "ms");

//测试中间插入 startTime = System.currentTimeMillis();
 for (int i =0; i < size; i++) {
 arrayList.add(size /2, i);
 }
 endTime = System.currentTimeMillis();
 System.out.println("ArrayList add in middle: " + (endTime - startTime) + "ms");

startTime = System.currentTimeMillis();
 for (int i =0; i < size; i++) {
 linkedList.add(size /2, i);
 }
 endTime = System.currentTimeMillis();
 System.out.println("LinkedList add in middle: " + (endTime - startTime) + "ms");
 }
}
```这个示例代码展示了`ArrayList`和`LinkedList`在添加元素、随机访问和中间插入操作下的性能对比。实际性能可能会因JVM实现、系统资源等因素而有所不同。