《工作笔记》Java中的集合类arraylist和linkedlist

冷不防 2022-03-07 08:44 108阅读 0赞

## ArrayList ##

ArrayList的数据结构是Object数据  
当使用 List list = new ArrayList(); ,只是新建了一个空数组  
当使用 List list = new ArrayList(10); 会新建长度为10的Object数组

1.  在list是空数组的情况下，会取 `DEFAULT_CAPACITY`作为数组的长度，并创建数组 ,并向新数组中添加数据
2.  在list不是空数组的情况下，会计算是否需要扩容，扩容是按照现有数组长度的1.5倍扩充

private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }

1.  list数组支持随机查找，主要体现在根据下标就能找到元素

所以，在使用数据的时候，最好能预估数组长度，减少数组扩容带来的性能损耗，还有就是数组在插入的时候的，如果默认插在数组末尾，时间复杂度是 O(1),如果是插在中间位置，那么需要插入后面的所有位置都进行移动，性能也很差，删除和添加一样，建议谨慎操作

ArrayList是非线程安全的,SynchronizedList是线程安全的数组

## LinkedList ##

LinkedList数组结构是双向链表，也是非线程安全的。双向链表结构对插入和删除时间复杂度一样。

## 比较 ##

比较的前提是数据量相同的情况下  
1.ArrayList更适合随机查找，LinkedList更适合插入和删除  
2.都是线程不安全的  
3.ArrayList插入和删除的性能跟数组下标有关  
4.LinkedList的查询性能跟元素位置有关