数据结构 -- ArrayList与LinkedList的区别

一、二者的相同点

1，它们都是继承自List接口。

二、二者的区别

1，数据结构：ArrayList是（Array动态数组）的数据结构；而LinkedList是（Link双向链表）的数据结构。ArrayList 自由性较低，需要手动的设置固定大小的变化。而LinkedList自由性较高。

2，随机访问 (get、set)：ArrayList 比 LinkedList 效率更高。原因是 ArrayList 在内存中的表现形式是一段连续的空间，当我 get(index) 的时候，我可以根据数组的首地址+偏移量，直接计算出我想访问的第 index个元素位置； 而 LinkedList 是链表的形式，在内存中的表现形式不是一段连续的空间，而是每个元素中都存储着上一个和下一个元素指针地址，当get(index)时，只能从首个元素开始，依次获取下一个元素的地址。LinkedList是线性的数据存储方式，所以需要移动指针从前往后依次查找。用时间复杂度来表示的话，ArrayList 的 get(index) 是 O(1)，而 LinkedList 是 O(n)    

3，增加和删除操 (add ，remove): LinkedList 比 ArrayList 的效率更高，因为ArrayList是数组，在进行增、删操作时，会改变操作节点之后所有数据的下标，需要进行数据的移动。