ArrayList如何提供随机访问行为？

Question

ArrayList简单地实现为Object [].我知道它实现了RandomAccess接口,但它只是一个标记接口......

所以,我的问题是:为什么/如何使用ArrayList提供随机访问功能？

编辑1:也许我应该更清楚......我想要理解的是为什么在它是Object []时访问元素的时间是恒定的？

Answer 1

通过比较LinkedList,ArrayList和Array可以使事情变得简单:

链表:

+----+      +----+      +----+      +----+
|Head| ---> | e1 | ---> | e2 | ---> | e3 | ---> null
+----+      +----+      +----+      +----+

现在,假设我想获得元素e2,但是链表本身保存了headNode的引用.要到达e2,我必须从HeadNode一直遍历到e2.显然,这不提供恒定的时间操作,因为如果不遍历列表就无法直接访问任何元素.

阵:

+----++----++----++----+
| e1 || e2 || e3 || e4 |  (value)
+----++----++----++----+
| 01 || 02 || 03 || 04 |  (address)
+----++----++----++----+

想象一下,当你有一个包含数组的变量时,只有第一个元素(e1)的地址保存在变量中.以下数组元素将存储在下一个可用内存块中.数组元素在存储器中以连续顺序彼此相邻.当您需要访问特定元素时,这使其成为一个恒定的时间操作.例如,当您要访问e3时,每个内存块为4个字节.从第一个元素开始,从数组引用移动2个内存块(8个字节).恒定时间操作的关键是:不需要遍历.它只需根据每个块的大小和要移动的块数(由数组索引表示)计算从当前位置移位的字节数.在Java中,当你试图超越数组的已分配内存的边界时,它会给你一个ArrayIndexOutOfBoundsException.

数组列表:

Arraylist使用相同的数组概念.它最初将分配10的大小.当需要增长(例如添加更多元素)时,它会创建一个新的数组,并增加存储长度.由于数据的存储是通过数组存储的,因此操作时间将与数组相同(即恒定时间).