ArrayList的扩容机制
插入和删除
ArrayList:在末尾进行插入和删除操作是高效的,但在中间或开头插入和删除需要移动元素,性能较差
LinkedList:插入和删除元素的性能相对较好,特别是在链表中间或头尾插入和删除元素时
内存空间占用:
ArrayList的空间浪费主要体现在底层数组需要为新元素预留一定的容量空间
LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为链表要存放后继和前驱节点)
使用场景
ArrayList:适用于需要频繁随机访问元素,而对插入和删除操作要求不那么严格的场景
LinkedList:适用于需要频繁插入和删除操作,而对随机访问的需求较少的场景
(注: java的LinkedList有严重缺陷, 插入删除的性能其实很多场景比ArrayList要差)
ArrayList的扩容机制
- 当调用ArrayList的无参构造new对象时, ArrayList对象的初始容量为0.
- 当插入一个元素时, ArrayList会进行首次扩容(无参构造才会用首次扩容). 首次扩
容, ArrayList会创建一个长度为10的新数组, 替换掉原来的旧数组. 此时ArrayList 的长度就为10.
- 当插入10个数据后, 要插入第11个数据时, 容量不足, 会触发第2次扩容. 第二次扩
容会扩容原容量的1.5倍, 之后扩容都是原容量的1.5倍.
ArrayList每次扩容都会创建新数组, 然后把数据转移到新数组中.