ArrayList与LinkLIst
ArrayList
在Java中，ArrayList是java.util包中的一个类，它实现了List接口，是一个动态数组，可以根据需要自动增长或缩小。下面是ArrayList的一些基本特性以及其底层原理的简要讲解：
ArrayList基本特性：
-
动态数组：
ArrayList是一个动态数组，它可以根据需要自动调整大小。 -
允许重复元素：
ArrayList允许存储相同的元素，可以包含重复的值。 -
随机访问： 通过索引，可以以常数时间复杂度进行元素的访问，这是由于底层是数组实现。
-
不同步：
ArrayList不是线程安全的，如果多个线程同时访问一个ArrayList实例，而至少有一个线程修改了列表结构，那么它必须保持外部同步。
API
boolean add(E element): | 将指定的元素添加到列表的末尾。 |
void add(int index, E element): | 在指定的位置插入指定的元素。 |
E get(int index) | 回列表中指定位置的元素。 |
int size(): | 返回列表中的元素数。 |
boolean remove(Object o) | 从列表中删除指定的元素（如果存在） |
E remove(int index) | 删除列表中指定位置的元素。 |
boolean contains(Object o) | 如果列表包含指定的元素，则返回 true。 |
void clear(): | 从列表中删除所有元素。 |
boolean isEmpty(): | 如果列表不包含元素，则返回 true。 |
ArrayList底层原理：
-
基于数组：
ArrayList的底层是一个数组。当你创建一个ArrayList时，它会初始化一个数组来保存元素。初始时，默认大小是0的数组。当添加第一个元素的时候，底层会创建一个长度为10的数组 -
自动扩容： 当元素数量超过当前数组容量时，
ArrayList会创建一个新的数组，将元素复制到新数组中，并更新引用。通常，新数组的大小是原数组的1.5倍。如果一次添加多个元素1.5倍放不下，则新建数组长度以实际长度为准 -
容量增长：
ArrayList的容量增长不是按需一次性增长的，而是按照一定的策略进行递增。这样可以减少频繁扩容的开销。 -
元素的添加和删除： 在数组中，添加和删除元素可能涉及到移动其他元素，这可能导致性能开销。在某些情况下，特别是在大量操作的情况下，可能会考虑使用
LinkedList，因为在链表中添加和删除元素的开销较小。
// 示例代码
import java.util.ArrayList;public class ArrayListExample {public static void main(String[] args) {// 创建ArrayListArrayList<String> arrayList = new ArrayList<>();// 添加元素arrayList.add("Java");arrayList.add("Python");arrayList.add("C++");// 访问元素System.out.println("First element: " + arrayList.get(0));// 删除元素arrayList.remove("Python");// 打印所有元素System.out.println("All elements: " + arrayList);}
}
总体而言，ArrayList是一个灵活且性能良好的集合类，适用于大多数元素的存储和检索场景。
LinkList
LinkedList是Java集合框架中的另一种实现List接口的类，它基于链表数据结构。相比于ArrayList，LinkedList在一些操作上有不同的性能特点。
LinkedList的基本特性：
-
基于链表：
LinkedList使用双向链表实现，每个元素都包含一个指向前一个元素和一个指向后一个元素的引用。这使得在链表中插入和删除元素更为高效，因为不需要移动其他元素。 -
不适合随机访问： 由于是链表结构，
LinkedList在随机访问元素时效率较低。访问某个特定位置的元素需要从头或尾开始遍历链表。 -
元素添加和删除高效： 在链表中插入和删除元素的操作相对较快，因为只需要更新相邻元素的引用，而不需要像数组一样移动大量元素。
-
不同步：
LinkedList也是非线程安全的，如果需要在多线程环境中使用，需要进行外部同步。
API
boolean add(E element) | 将指定的元素添加到列表的末尾。 |
void add(int index, E element) | 在指定的位置插入指定的元素 |
E get(int index): | 返回列表中指定位置的元素 |
E getFirst() | 返回列表中的第一个元素 |
E getLast(): | 返回列表中的最后一个元素。 |
boolean remove(Object o) | 从列表中删除指定的元素（如果存在） |
E remove(int index): | 删除列表中指定位置的元素。 |
E removeFirst(): | 删除并返回列表的第一个元素 |
E removeLast() | 删除并返回列表的最后一个元素 |
boolean contains(Object o) | 如果列表包含指定的元素，则返回 true。 |
void clear() | 从列表中删除所有元素 |
E set(int index, E element): | 用指定的元素替换列表中指定位置的元素。 |
boolean isEmpty(): | 如果列表不包含元素，则返回 true。 |
int indexOf(Object o) | 返回列表中第一次出现的指定元素的索引；如果列表不包含此元素，则返回 |
boolean offer(E e) | 将指定的元素添加到列表的末尾（队尾）。 |
E poll(): | 检索并删除列表的头部（队首）元素。 |
void push(E e): | 将元素推入列表所表示的堆栈（在列表的头部）。 |
E pop(): | 从列表所表示的堆栈中弹出第一个元素。 |
Object[] toArray(): | 返回包含列表中所有元素的数组。 |
示例代码：
import java.util.LinkedList;public class LinkedListExample {public static void main(String[] args) {// 创建LinkedListLinkedList<String> linkedList = new LinkedList<>();// 添加元素linkedList.add("Java");linkedList.add("Python");linkedList.add("C++");// 访问元素System.out.println("First element: " + linkedList.getFirst());// 删除元素linkedList.remove("Python");// 打印所有元素System.out.println("All elements: " + linkedList);}
}
适用场景：
- 当需要频繁执行插入和删除操作时，特别是在列表的中间位置。
- 当对列表进行迭代操作而不是随机访问时。
总体而言，LinkedList和ArrayList各有优势，选择取决于具体的使用场景。ArrayList适用于随机访问和大量元素的存储，而LinkedList适用于频繁插入和删除的场景。