黑马程序员技术交流社区

标题: ArrayList的底层数据结构 [打印本页]
作者: huangxuanheng    时间: 2014-8-3 20:49
标题: ArrayList的底层数据结构
ArrayList的底层数据结构是数组，但是工作原理是什么？为什么它能添加对象？底层的源代码是什么？
作者: fantacyleo    时间: 2014-8-3 21:02
跟StringBuilder一样，先来一个固定长度的数组，元素个数不超出这个长度就直接添加，如果超出，就新建一个更长的数组，把原数组复制到新数组中
作者: GoodBoy123    时间: 2014-8-3 22:22
你想知道ArrayList的原代码可以在Eclipse里按住ctrl然后点击ArrayList就可以看到源代码
作者: —Jimmy—    时间: 2014-8-4 10:30
底层数据结构是数组,原理就和数组一模一样啊,添加元素就是往数组中存放元素啊,别人只是把这个存放元素的动作,封装成了函数而已!!
作者: huangxuanheng    时间: 2014-8-4 20:28
—Jimmy— 发表于 2014-8-4 10:30
底层数据结构是数组,原理就和数组一模一样啊,添加元素就是往数组中存放元素啊,别人只是把这个存放元素的动 ...

是这样啊，那但是数组是固定长度的啊？而集合是不定的，即使封装了数组，感觉也不能改变定长吧？
作者: huangxuanheng    时间: 2014-8-4 21:16
GoodBoy123 发表于 2014-8-3 22:22
你想知道ArrayList的原代码可以在Eclipse里按住ctrl然后点击ArrayList就可以看到源代码 ...

谢谢.....太管用了
作者: 寐海流风    时间: 2014-8-4 21:16
可扩容数组。
作者: huangxuanheng    时间: 2014-8-4 21:17
fantacyleo 发表于 2014-8-3 21:02
跟StringBuilder一样，先来一个固定长度的数组，元素个数不超出这个长度就直接添加，如果超出，就新建一个 ...

有点糊涂，听不明白:'(
作者: fantacyleo    时间: 2014-8-5 00:54
huangxuanheng 发表于 2014-8-4 21:17
有点糊涂，听不明白

写个大意
  1. class ArrayList {
  2.         private Object[] elements;
  3.         private int size;
  4.        
  5.         ArrayList() {
  6.                 elements = new Object[16]; // 先设定一个固定长度的数组
  7.                 size = 0;
  8.         }
  9.        
  10.         public void add(Object obj) {
  11.                 // 如果元素个数不超过数组长度,直接添加新元素
  12.                 if (size < elements.length)
  13.                         elements[size++] = obj;
  14.                 else { // 如果数组满了，新建一个更长的数组,把原数组的元素copy到新数组，再添加元素
  15.                         Object[] newElements = new Object[size * 2];
  16.                         System.arraycopy(elements, 0, newElements, 0, size);
  17.                         elements = newElements;
  18.                         elements[size++] = obj;
  19.                 }
  20.         }
  21. }
复制代码
作者: ssy1939    时间: 2014-8-5 01:50
底层会先建一个长度为10的数组，添加对象超过10后，会新建一个数组，长度比原数组多1/2，即15，将再将原数组对象拷贝至新数组，原数组变成垃圾。继续添加超过15时，再新建一个多1/2的数组，依次类推。自己也可以看下API中arrayList的介绍



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2