马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
List底层：
List 是 Java 中的一个接口，具体的底层实现取决于它的实现类。最常见的 List 实现类是 ArrayList 和 LinkedList，它们的底层原理完全差别。下面我们分别分析这两种实现类的底层原理。
ArryList原理：
ArrayList 是基于动态数组实现的，它的底层是一个可调整大小的数组。
核心特点
- 底层数据布局：ArrayList 利用一个 Object[] 数组来存储元素。
- 动态扩容：当数组容量不足时，ArrayList 会自动扩容（通常是当前容量的 1.5 倍）。
- 随机访问：由于是基于数组实现的，ArrayList 支持通过索引快速访问元素，时间复杂度为 O(1)。
- 插入和删除：在中心插入或删除元素时，需要移动后续元素，时间复杂度为 O(n)。
底层实现细节：
- 初始化：
- 默认情况下，ArrayList 的初始容量为 10。
- 可以通过构造函数指定初始容量。
- List<Integer> list = new ArrayList<>(); // 默认容量为 10
- List<Integer> list = new ArrayList<>(20); // 指定初始容量为 20
- 添加元素
- 当调用 add(E e) 方法时，元素会被添加到数组的末尾。
- 如果数组已满，ArrayList 会触发扩容机制：
- 创建一个新的数组，大小为原数组的 1.5 倍（int newCapacity = oldCapacity + (oldCapacity >> 1)）。
- 将原数组中的元素复制到新数组中。
- 更新引用，指向新数组。
- 插入元素
- 当调用 add(int index, E element) 方法时，ArrayList 会将指定位置及其后续元素向后移动一位，然后插入新元素。
- 如果需要扩容，会先扩容再插入。
- list.add(1, 20); // 在索引 1 处插入元素
- 删除元素
- 当调用 remove(int index) 方法时，ArrayList 会将指定位置之后的元素向前移动一位，覆盖被删除的元素。
- 末了将数组的末了一个位置设置为 null，以便垃圾接纳。
- list.remove(1); // 删除索引 1 处的元素
- 随机访问：
- 通过 get(int index) 方法可以直接访问数组中的元素，时间复杂度为 O(1)。
- int value = list.get(0); // 获取索引 0 处的元素
LinkedList 的底层原理
LinkedList 是基于双向链表实现的，它的底层是一个由节点（Node）构成的链表。
核心特点
- 底层数据布局：LinkedList 利用双向链表存储元素，每个节点包罗数据、前驱节点和后继节点的引用。
- 动态大小：链表的大小可以动态调整，不需要扩容。
- 插入和删除：在链表中插入或删除元素时，只需要修改节点的引用，时间复杂度为 O(1)。
- 随机访问：访问链表中的元素需要重新或尾遍历，时间复杂度为 O(n)。
底层实现细节
- 节点布局：
- 每个节点是一个 Node 对象，包罗三个部分：
- E item：存储元素。
- Node next：指向下一个节点。
- Node prev：指向上一个节点。
- private static class Node<E> {
- E item;
- Node<E> next;
- Node<E> prev;
- Node(Node<E> prev, E element, Node<E> next) {
- this.item = element;
- this.next = next;
- this.prev = prev;
- }
- }
- 添加元素：
- 当调用 add(E e) 方法时，LinkedList 会在链表末尾添加一个新节点。
- 如果链表为空，新节点既是头节点也是尾节点。
- 如果链表不为空，新节点的 prev 指向原尾节点，原尾节点的 next 指向新节点。
- list.add(10); // 在链表末尾添加元素
- 插入元素：
- 当调用 add(int index, E element) 方法时，LinkedList 会遍历链表找到指定位置，然后插入新节点。
- 插入操作只需要修改相邻节点的引用。
- list.add(1, 20); // 在索引 1 处插入元素
- 删除元素：
- 当调用 remove(int index) 方法时，LinkedList 会遍历链表找到指定位置，然后修改相邻节点的引用，跳过被删除的节点。
- 被删除的节点会被垃圾接纳。
- list.remove(1); // 删除索引 1 处的元素
- 随机访问：
- 通过 get(int index) 方法访问元素时，LinkedList 需要重新或尾遍历链表，时间复杂度为 O(n)。
- int value = list.get(0); // 获取索引 0 处的元素
其他 List 实现类
- Vector：与 ArrayList 雷同，但是线程安全的（同步的），性能较低。
- Stack：继承自 Vector，实现了栈数据布局（后进先出）。
- CopyOnWriteArrayList：线程安全的 List，适合读多写少的场景。
总结
- ArrayList 基于动态数组实现，适合随机访问和尾部操作。
- LinkedList 基于双向链表实现，适合频繁插入和删除操作。
- 根据具体需求选择合适的 List 实现类，可以明显进步步伐性能。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
