Java ArrayList 和 LinkList 原理对比

Java 中的 ArrayList 和 LinkedList 都是实现了 List 接口的集合类它们都允许添加、删除和修改元素。但是它们的底层实现原理不同导致它们在不同的场景下拥有不同的优劣势。

ArrayListArrayList 的底层是通过数组实现的因此它具有数组的特性。它允许快速随机访问元素但是在插入和删除元素时速度较慢。当向 ArrayList 中添加元素时如果数组的长度不够容纳新的元素就需要创建一个新的更大的数组并将原来数组中的元素拷贝到新数组中。
优点

快速随机访问元素访问时间复杂度为 O(1)；
可以预先设定集合的大小避免多次扩容。
缺点

插入和删除元素时需要移动元素时间复杂度为 O(n)；
当数组长度不够时需要重新创建一个更大的数组拷贝原有元素开销较大。
LinkedListLinkedList 的底层是通过链表实现的因此它具有链表的特性。它不支持快速随机访问元素但是在插入和删除元素时速度更快。当向 LinkedList 中添加元素时只需要修改指针的指向即可不需要像 ArrayList 那样创建新数组并拷贝元素。
优点

插入和删除元素时只需要修改指针时间复杂度为 O(1)；
不需要预先设定集合的大小节省空间。
缺点

不支持快速随机访问元素访问时间复杂度为 O(n)；
占用空间较大因为需要为每个元素保存指针。
3.适用场景ArrayList适合于随机访问元素的场景比如需要频繁地读取集合中的元素而不需要频繁地插入和删除元素的情况。

LinkedList适合于频繁的插入和删除元素的场景比如实现栈和队列等数据结构或者需要经常对集合进行排序的情况。

ArrayListArrayList 是基于数组实现的动态数组它的内部是一个 Object[] 数组通过不断扩容实现可变长度。当数组已满时ArrayList会创建一个新的更大的数组将原数组中的元素拷贝到新数组中并使用新数组替换原数组。
ArrayList 的优点是访问元素快速因为它可以通过索引直接访问元素而不需要像 LinkedList一样遍历整个链表。缺点是插入和删除元素相对较慢因为在数组中插入或删除一个元素时需要将该位置后面的元素都向后或向前移动一个位置。

ArrayList适用于频繁访问元素但很少进行插入和删除操作的场景。

LinkedListLinkedList 是基于链表实现的双向链表它的内部是由一个个节点组成的每个节点包含一个值和指向前一个和后一个节点的指针。
LinkedList 的优点是插入和删除元素相对较快因为只需要修改相邻节点的指针即可而不需要像 ArrayList一样移动大量元素。缺点是访问元素相对较慢因为需要遍历整个链表找到指定位置的元素。

LinkedList适用于经常进行插入和删除操作的场景但不适用于频繁访问元素的场景。

综上所述ArrayList 和 LinkedList 的使用场景不同需要根据具体情况选择合适的集合类型。