Java数据结构之——List - 高飞网
210 人阅读

Java数据结构之——List

2017-07-28 02:09:46


 

ArrayList

LinkedList

描述

可变数组

链表

底层结构

数组:

private transient Object[] elementData;

双向循环链表:
class Node<E> {

        E item;

        Node<E> next;

        Node<E> prev;
}

特性

序列化

支持

支持

线程安全性

1非线程安全
2
快速失败机制(通过modCount
3 Collections.synchronizedList(new ArrayList(...));

1 非线程安全
2
快速失败机制(通过modCount

随机访问

支持,下标快速访问O(1)

需要遍历O(n)

Null

允许

允许

空间(capacity)

默认容量

10

由于链表的特性,LinkedList支持在任意位置插入数据,无需动态扩容

增长方式

数据copy

增长动因

旧空间无法满足新加元素后总长度

增量计算

int newCapacity = (oldCapacity * 3)/2 + 1;  即为原来的1.5

性能优化点

空间大小

如果预先知道数组大小,初始化时设置合适的大小,避免因数组扩容导致数据拷贝

 


还没有评论!
23.20.166.68