Java

List存储的数据为有序并且可重复，最具代表性的实现就是ArrayList和linkedList。

• ArrayList

1. ArrayList底层数据结构是数组，默认大小为10，其数组大小是可改变的。当有效元素的个数超过数组大小时，底层会进行扩容操作，扩容后数组的大小为原数组的1.5倍。
2. 由于数组索引的存在ArrayList在查询数据这一方面效率是非常快的，以及在集合的末尾新增或删除数据效率也是非常快的，但大数据量下涉及到在集合中间进行数据的新增或删除效率非常低，因为其底层在新增或删除操作的时候，会将大量数据整体向前或向后移动，这种频繁的操作，非常影响效率。ArrayList弊端在于即使索引上没有元素也会占内存。
3. ArrayList主要的性能开销在于扩容操作。

• linkedList

1. linkedList底层数据结构为双向链表，是没有容量大小以及扩容的概念。
2. 由于其链表是按照线性的方式去查找数据，在数据量庞大的情况下相比于ArrayList是比较慢的，但在插入和删除方面性能是非常快的，只需要将新节点挂到链表上即可。
3. linkedList主要的性能开销在于每个节点不止存储自己的数据，还要存储上一个节点与下一个节点的地址引用。