ArrayList和LinkedList的区别

1. 底层���据结构

• ArrayList 是动态数组的数据结构实现。

• LinkedList 是双向链表的数据结构实现。

  （）

  2. 操作数据效率

  • ArrayList按照下标查询的时间复杂度O(1)【内存是连续的，根据寻址公式】， LinkedList不支持下标查询。

  • 查找（未知索引）： ArrayList需要遍历，链表也需要链表，时间复杂度都是O(n)。

  • 新增和删除

    • ArrayList尾部插入和删除，时间复杂度是O(1)；其他部分增删需要挪动数组，时间复杂度是O(n)。

    • LinkedList头尾节点增删时间复杂度是O(1)，其他都需要遍历链表，时间复杂度是O(n)。

    3. 内存空间占用

    • ArrayList底层是数组，内存连续，节省内存。

    • LinkedList 是双向链表需要存储数据，和两个指针，更占用内存。

      4. 线程安全

      • ArrayList和LinkedList都不是线程安全的。

      • 如果需要保证线程安全，有两种方案：

        • 在方法内使用，局部变量则是线程安全的。

        • 使用线程安全的ArrayList和LinkedList。