在Java的集合框架中，`LinkedList`和`ArrayList`都是用来存储一组对象的容器，但它们在内部实现、性能特点等方面存在着一些差异。
## 一、内部实现
1. **ArrayList**
- `ArrayList`是基于数组实现的动态数组。它在内存中是一块连续的存储空间。当创建`ArrayList`时，会初始化一个默认大小的数组（初始容量为10）。随着元素的添加，如果数组容量不足，会进行扩容操作，通常是将原数组复制到一个更大容量的新数组中。
- 例如，以下代码创建了一个`ArrayList`并添加元素：
```java
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("Apple");
arrayList.add("Banana");
arrayList.add("Cherry");
System.out.println(arrayList);
}
}
```
2. **LinkedList**
- `LinkedList`是基于双向链表实现的。每个节点包含了数据元素、指向前一个节点的引用和指向后一个节点的引用。这种结构不需要连续的内存空间，在内存中的存储是分散的。
- 例如，创建和使用`LinkedList`的代码如下：
```java
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("Dog");
linkedList.add("Cat");
linkedList.add("Mouse");
System.out.println(linkedList);
}
}
```
## 二、性能特点
1. **随机访问**
- **ArrayList**：由于`ArrayList`基于数组实现，它支持快速的随机访问。通过索引访问元素的时间复杂度为 $O(1)$。例如：
```java
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
// 快速访问索引为1的元素
System.out.println(arrayList.get(1));
```
- **LinkedList**：对于`LinkedList`，随机访问元素效率较低，因为需要从链表的头部（或尾部）开始遍历，时间复杂度为 $O(n)$。例如：
```java
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
// 访问索引为1的元素，效率较低
System.out.println(linkedList.get(1));
```
2. **插入和删除操作**
- **ArrayList**：在`ArrayList`的中间插入或删除元素时，需要移动后面的元素，时间复杂度为 $O(n)$（$n$为元素个数）。但是在末尾添加元素的时间复杂度为 $O(1)$（不考虑扩容情况）。例如：
```java
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
// 在索引为1的位置插入元素4
arrayList.add(1, 4);
System.out.println(arrayList);
```
- **LinkedList**：在`LinkedList`中插入和删除元素（特别是在链表中间）只需要修改节点之间的引用，时间复杂度为 $O(1)$。例如：
```java
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
// 在第二个位置插入元素4
linkedList.add(1, 4);
System.out.println(linkedList);
```
## 三、适用场景
1. **ArrayList**
- 当需要频繁进行随机访问元素的操作，并且数据量相对稳定或者增长可预测时，`ArrayList`是一个较好的选择。例如，在存储数据库查询结果集并需要频繁根据索引获取元素时。
2. **LinkedList**
- 当需要频繁进行插入和删除操作（特别是在集合中间）时，`LinkedList`更合适。例如，在实现一个队列或者栈数据结构时，可以使用`LinkedList`，因为队列的入队和出队操作，栈的入栈和出栈操作都可以高效地在链表头部或者尾部进行。
综上所述，在Java编程中，根据具体的需求选择`LinkedList`或者`ArrayList`可以提高程序的性能和效率。
接下来我们来了解一下Map集合。
# Java中的HashMap与TreeMap
在Java的集合框架中，`HashMap`和`TreeMap`都是用于存储键 - 值对（`key - value`）的数据结构，但它们在内部实现、功能特性以及适用场景等方面存在着明显的差异。
## 一、内部实现
1. **HashMap**
- `HashMap`基于哈希表实现。它通过计算键（`key`）的哈希值来确定元素在数组中的存储位置。在`JDK 1.8`之前，`HashMap`采用数组 + 链表的结构。当发生哈希冲突（即不同的键计算出相同的哈希值）时，新元素会以链表的形式存储在对应数组索引的位置。在`JDK 1.8`之后，如果链表长度超过一定阈值（默认为8），链表会转换为红黑树，以提高查找效率。
- 例如，以下是创建和使用`HashMap`的示例代码：
```java
import java.util.HashMap;
public class HashMapExample {
public static void main(String[] args) {
HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("Apple", 1);
hashMap.put("Banana", 2);
hashMap.put("Cherry", 3);
System.out.println(hashMap.get("Apple"));
}
}
```
2. **TreeMap**
- `TreeMap`基于红黑树（一种自平衡二叉查找树）实现。它会根据键（`key`）的自然顺序或者自定义的比较器来对键值对进行排序。每次插入元素时，都会按照红黑树的规则调整树的结构，以保持树的平衡。
- 例如：
```java
import java.util.TreeMap;
public class TreeMapExample {
public static void main(String[] args) {
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Dog", 1);
treeMap.put("Cat", 2);
treeMap.put("Mouse", 3);
System.out.println(treeMap.get("Cat"));
}
}
```
## 二、功能特性
1. **排序特性**
- **TreeMap**：由于基于红黑树实现，`TreeMap`中的键值对是有序的。默认按照键的自然顺序（如果键实现了`Comparable`接口）进行排序。例如，如果键是字符串类型，那么会按照字典序排序。也可以通过自定义比较器来指定排序规则。
- 以下是自定义比较器的示例：
```java
import java.util.Comparator;
import java.util.TreeMap;
public class CustomComparatorTreeMap {
public static void main(String[] args) {
// 按照字符串长度进行排序的比较器
Comparator<String> comparator = new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length() - o2.length();
}
};
TreeMap<String, Integer> treeMap = new TreeMap<>(comparator);
treeMap.put("long", 1);
treeMap.put("short", 2);
treeMap.put("medium", 3);
System.out.println(treeMap);
}
}
```
- **HashMap**：`HashMap`不保证元素的顺序，元素的存储顺序取决于哈希函数的计算结果以及哈希冲突的处理方式。
2. **性能特性**
- **HashMap**：在插入、删除和查找操作方面，`HashMap`通常具有较好的性能。对于插入和查找操作，平均时间复杂度接近 $O(1)$。但是在最坏情况下（哈希冲突严重时），查找操作可能退化为 $O(n)$，不过这种情况在实际应用中很少出现。
- **TreeMap**：插入、删除和查找操作的时间复杂度为 $O(\log n)$，其中 $n$ 是树中的节点数量。虽然在平均情况下，`TreeMap`的性能比`HashMap`略差，但它提供了有序性的保证。
## 三、适用场景
1. **HashMap**
- 当不需要对键值对进行排序，并且需要快速的插入、删除和查找操作时，`HashMap`是首选。例如，在存储用户的配置信息，其中键是配置项名称，值是配置项的值，不需要按照特定顺序存储这些信息时。
2. **TreeMap**
- 当需要对键值对按照键进行排序时，例如在实现一个排行榜系统，键是用户的排名分数，值是用户信息，需要按照分数对用户进行排序时，`TreeMap`就非常合适。
总之，在Java编程中，根据实际需求合理选择`HashMap`或者`TreeMap`可以提高程序的性能和功能的准确性。
