ArrayList

线性表 - 数组

线性表

线性表 是最基本、最简单、也是最常用的一种数据结构，一个线性表是 n个具有相同特性的数据元素的有序数列。

数组 是一种顺序存储的线性表，可以存储多个值 每个元素可以通过索引进行访问

数据按照顺序存储在连续位置的存储器中

随机访问

由于他们存储在连续的位置因此可以使用他们的索引来计算内存地址，以便随机访问数据

数组的另一个特点是与列表相比，在特定位置添加或删除数据的成本比较高

• 首先删除元素
• 然后逐个移动数据填充空白空间、
• 最后通过删除额外的空间来完成删除操作

数组优缺点

优点：

• 空间利用率高。
• 查询速度高效，通过下标来直接存取。

缺点：

• 插入和删除比较慢，比如：插入或者删除一个元素时，整个表需要遍历移动元素来重新排一次顺序。
• 不可以增长长度，有空间限制，当需要存取的元素个数可能多于顺序表的元素个数时，会出现 “溢出” 问题。当元素个数远少于预先分配的空间时，空间浪费巨大。

动态数组的设计实现

动态数组接口设计

• int size(); //元素的数量
• boolean isEmpty(); //是否为空
• boolean contains(E element); //是否包含某个元素
• void add(E element); //添加元素到最后面
• E get(int index); //返回index位置对应的元素
• E set(int index, E element); //设置index位置的元素
• void add(in index, E element); //往index位置添加元素
• E remove(int index); //删除index位置对应的元素
• int indexOf(E element); //查看元素的位置
• void clear(); //清除所有元素