java基础解析系列(十)---ArrayList和LinkedList源码及使用分析

java基础解析系列(十)---ArrayList和LinkedList源码及使用分析

目录

• java基础解析系列(一)---String、StringBuffer、StringBuilder
• java基础解析系列(二)---Integer缓存及装箱拆箱
• java基础解析系列(三)---HashMap原理
• java基础解析系列(四)---LinkedHashMap的原理及LRU算法的实现
• java基础解析系列(五)---HashMap并发下的问题以及HashTable和CurrentHashMap的区别
• java基础解析系列(六)---注解原理及使用
• java基础解析系列(七)---ThreadLocal原理分析
• java基础解析系列(八)--fail-fast机制及CopyOnWriteArrayList的原理
• 这是我的博客目录，欢迎阅读

ArrayList

成员变量

• 数组元素

111 private transient Object[] elementData;


• 数组中元素的个数

118 private int size;


构造方法

• 初始化容量为10

Constructs an empty list with an initial capacity of ten.
137
138 public ArrayList() {
139 this(10);
140 }


• 可以设置初始容量

127 public ArrayList(int initialCapacity) {
128 super();
129 if (initialCapacity < 0)
130 throw new IllegalArgumentException("Illegal Capacity: "+
131 initialCapacity);
132 this.elementData = new Object[initialCapacity];
133 }


ensureCapacity方法

178 public void ensureCapacity(int minCapacity) {
179 modCount++;
180 int oldCapacity = elementData.length;
181 if (minCapacity > oldCapacity) {
182 Object oldData[] = elementData;
183 int newCapacity = (oldCapacity * 3)/2 + 1;
184 if (newCapacity < minCapacity)
185 newCapacity = minCapacity;
186 // minCapacity is usually close to size, so this is a win:
187 elementData = Arrays.copyOf(elementData, newCapacity);
188 }
189 }


• 181行，判断minCapacoty是否大于elementData数组的长度
• 如果181结果为true，183行设置新的容量为旧的容量*3/2+1
• 187行进行扩容，创建一个新容量的数组，然后将旧的数组元素复制到新数组中

顺序add方法

377 public boolean add(E e) {
378 ensureCapacity(size + 1); // Increments modCount!!
379 elementData[size++] = e;
380 return true;
381 }


• 378行执行ensureCapacity方法，看插入一个元素后是否需要扩容
• 379行，将待添加元素放置到下标size的位置,size+1

指定index的add方法

392 public void add(int index, E element) {
393 rangeCheckForAdd(index);
394
395 ensureCapacity(size+1); // Increments modCount!!
396 System.arraycopy(elementData, index, elementData, index + 1,
397 size - index);
398 elementData[index] = element;
399 size++;
400 }


• 393执行rangeCheckForAdd方法

577 private void rangeCheckForAdd(int index) {
578 if (index > size || index < 0)
579 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
580 }


• rangeCheckForAdd方法判断index是否超出范围或者小于0
• 395执行ensureCapacity方法看是否需要扩容
• 396行将index开始的元素全部往后移动一位
• 然后设置index位置的元素为插入元素

remove方法

411 public E remove(int index) {
412 rangeCheck(index);
413
414 modCount++;
415 E oldValue = elementData(index);
416
417 int numMoved = size - index - 1;
418 if (numMoved > 0)
419 System.arraycopy(elementData, index+1, elementData, index,
420 numMoved);
421 elementData[--size] = null; // Let gc do its work
422
423 return oldValue;
424 }


• 412行rangeCheck看传入的index是否在范围之内

569 private void rangeCheck(int index) {
570 if (index >= size)
571 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
572 }


• 415通过下标获得该元素
• 419行进行数组的移动，elementData数组中位置在 index+1 到 index+numMoved-1 之间的组件被分别复制到elementData数组中的 index 到 index+numMoved-1 位置。
• 把index后面的元素向前移动一位后，将size-1的位置设置为null，方便gc

get方法

348 public E get(int index) {
349 rangeCheck(index);
350
351 return elementData(index);
352 }


• 349行查找index是否超出范围
• 351直接通过坐标从数组中返回

LinkedList

成员变量

95 private transient Entry<E> header = new Entry<E>(null, null, null);
96 private transient int size = 0;


• 95行head为一个头结点
• size为链表大小

构造方法

101 public LinkedList() {
102 header.next = header.previous = header;
103 }

• 102行将header的前节点和后节点设置为header本身,从这里也可以看出这是一个双向链表

add方法

214 public boolean add(E e) {
215 addBefore(e, header);
216 return true;
217 }


• 215行执行addBefore方法

794 private Entry<E> addBefore(E e, Entry<E> entry) {
795 Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
796 newEntry.previous.next = newEntry;
797 newEntry.next.previous = newEntry;
798 size++;
799 modCount++;
800 return newEntry;
801 }


• 795行创建一个新的节点
• 796行和797行修改节点的指针，将新节点放入链表

get方法

331 public E get(int index) {
332 return entry(index).element;
333 }

• 执行entry方法

380 private Entry<E> entry(int index) {
381 if (index < 0 || index >= size)
382 throw new IndexOutOfBoundsException("Index: "+index+
383 ", Size: "+size);
384 Entry<E> e = header;
385 if (index < (size >> 1)) {
386 for (int i = 0; i <= index; i++)
387 e = e.next;
388 } else {
389 for (int i = size; i > index; i--)
390 e = e.previous;
391 }
392 return e;
393 }


• 从这个方法可以看出并不是就是从前往后一个一个寻找，而是先将size>>1也就是将size除以2，看此时要查看的下标是小于还是大于这个数，如果小于这个数，说明位于链表中点的前面，用next指针寻找，正向寻找，反之用previous指针来寻找，这样可以减少遍历的次数
• 不过不能像ArrayList通过index直接定位，还是要一个一个寻找

remove方法

232 public boolean remove(Object o) {
233 if (o==null) {
234 for (Entry<E> e = header.next; e != header; e = e.next) {
235 if (e.element==null) {
236 remove(e);
237 return true;
238 }
239 }
240 } else {
241 for (Entry<E> e = header.next; e != header; e = e.next) {
242 if (o.equals(e.element)) {
243 remove(e);
244 return true;
245 }
246 }
247 }
248 return false;
249 }


• 可以看到，从前往后遍历，找到Object o后执行remove方法

803 private E remove(Entry<E> e) {
804 if (e == header)
805 throw new NoSuchElementException();
806
807 E result = e.element;
808 e.previous.next = e.next;
809 e.next.previous = e.previous;
810 e.next = e.previous = null;
811 e.element = null;
812 size--;
813 modCount++;
814 return result;
815 }


• 删除这个节点后，重新调整链表

总结与对比

• 效率方面，这两个集合对应数据结构中的两个线性表，一个数组一个链表，数组可以通过下标可以快速定位元素，所以自然查找和修改效率高。链表不能快速定位元素，只能一个一个找，所以自然查找效率没有数组快，而链表的优势在于他能快速插入快速删除因为只需修改一下节点的指针就可以，不需要像ArrayList移动元素。
• 容量方面，因为数组是有容量的，所以当容量不足的时候，需要扩容，扩容后就以为者需要进行一次复制，所以如果使用ArrayList的时候，要初始化一个合适的容量，避免扩容的开销。而链表就没有大小限制，插入一个元素，只要插入一个节点就行了
• 编程世界里面，同一个问题会有很多的方案，有优点也会一定会有缺点，只是在哪种场景下，优点大于缺点罢了

我觉得分享是一种精神，分享是我的乐趣所在，不是说我觉得我讲得一定是对的，我讲得可能很多是不对的，但是我希望我讲的东西是我人生的体验和思考，是给很多人反思，也许给你一秒钟、半秒钟，哪怕说一句话有点道理，引发自己内心的感触，这就是我最大的价值。（这是我喜欢的一句话，也是我写博客的初衷）

作者：jiajun 出处： http://www.cnblogs.com/-new/

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。如果觉得还有帮助的话，可以点一下右下角的【推荐】，希望能够持续的为大家带来好的技术文章！想跟我一起进步么？那就【关注】我吧。