Java ArrayList与LinkedList源码分析与比较

时间:2022-08-16 19:32:05

众所周知,ArrayList与LinkedList都实现了List接口,那么其分别是如何实现其中的 add(E object),get(int location),remove(int location),clear()方法呢?

一、ArrayList源码分析

1、如何初始化?
2、如何add一个对象?
3、ArrayList如何得到一个数
4、如何remove一个对象?
5、如何进行的clear?

1、看看ArrayList()初始化方法:
 public ArrayList() {
array = EmptyArray.OBJECT;
}
其中EmptyArray的OBJECT对象为
public static final Object[] OBJECT = new Object[0];
这里也就是将array初始化为一个没有数据的数组。

2、ArratList如何增加一个对象
public boolean add(E object) {
Object[] a = array;
int s = size;
if (s == a.length) {
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;
modCount++;
return true;
}
其中MIN_CAPACITY_INCREMENT变量为12,我们将其带入,其源码解析为
     Object[] a = array;
int s = size;
//其中s为当前List中储存的对象的数量,a.length为当前存储数组的长度
//当相等时,说明储存数组已经满了,这时候就需要新建一个更长的数组
if (s == a.length) {
//此为新建一个更长数组的源码
Object[] newArray = new Object[s +
(s < (12/ 2) ? 12: s >> 1)];
//然后将原先的数组中的内容都拷贝新的数组中
System.arraycopy(a, 0, newArray, 0, s);
//将ArrayList中的数组指向新的数组
array = a = newArray;
}
//把储存数据的数组增加之后,就可以在数组添加指定数据:
a[s] = object;
size = s + 1;
modCount++;
 可以看出,ArrayList虽然是使用数据进行的对象存储,但不是每增加一个数就将数组加一,这样的开销太大,而是到了临界值后增加一定的值。
  
  3、ArrayList如何得到一个数
  public E get(int index) {
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
return (E) array[index];
}
 因为ArrayList是采用数组进行储存,所以可以直接通过位置得到其数据

  4、如何remove一个对象

 下面为删除指定位置数据的源码:
 public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) {
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
//可以看出,直接把数组中指定位置及其后面的数据向前移一位
System.arraycopy(a, index + 1, a, index, --s - index);
//然后将最后一个一位的引用置空
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return result;
}

5、如何进行的clear:
public void clear() {
if (size != 0) {
Arrays.fill(array, 0, size, null);
size = 0;
modCount++;
}
}
可以看出,clear时并不是将指向数组的引用置空,而是将数组中所有对象的引用都置空,这样下次增加对象时就不需要在新建数组了。

二、LinkedList
因为LinkedList是采用链表进行存储,所以先看其节点的代码:
private static final class Link<ET> {
ET data;


Link<ET> previous, next;


Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}
 可以看出,其节点中的指针不仅有指向下一个的next指针,也有指向前一个previous指针,所以,可以说LinkedList是采用双向链表的设计。
  1、LinkedList的初始化代码:
    public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
  2、LinkedList如何添加对象

为了方便理解,先看一下双向链表的存储方式,可以看出来,首先有一个voidLink头结点,其next指针指向第一个节点,previous指针指向了最后一个节点,这样,一个头结点就可以访问到第一个或者是最后一个节点了。

Java ArrayList与LinkedList源码分析与比较

这时候,如果我又在后面添加了一个节点newLastNode,那么结果应为:

Java ArrayList与LinkedList源码分析与比较

明白了原理之后,就可以看看LinkedList添加对象的源码了
    @Override
public boolean add(E object) {
return addLastImpl(object);
}


private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous;
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
voidLink.previous = newLink;
oldLast.next = newLink;
size++;
modCount++;
return true;
}
可以看出,源码中的oldLast就对应着图一中的lastNode,newLink 即为图二中创建的newLastNode。
3、LinkedList如何得到指定位置的数字:
  public E get(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
return link.data;
}
throw new IndexOutOfBoundsException();
}
首先,如果得到的位置小于0或者比最大的数字还大,就会抛出IndexOutOfBoundsException异常。
其次,其会判断位置location数是在前半段还是后半段,举个例子,如果当前List的size为16,那么如果得到参数的位置小于8,就属于前半段,就从刚开始向后遍历,相反,如果属于后半段,就从最后面的节点往前遍历,遍历成功后,将节点的值返回即可。
  4、LinkedList如何移除指定位置的数据:
   比如下面的双向链表:
   Java ArrayList与LinkedList源码分析与比较
  想要删除其中的B节点,只需要将A节点的next指针指向C节点,然后将C节点的previou指针指向A节点即可,
  下面为LinkedList删除指定位置数据的源码:
  public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}
可以看出,先得到指定位置上的节点,然后得到其前驱节点,与后驱节点,然后改变指针即可。
  5、linkedList如何清空数据
  清空数据的方法即将链表恢复成初始状态即可,即voidLink的头结点指向自己,next指针指向自己即可 
public void clear() {
if (size > 0) {
size = 0;
voidLink.next = voidLink;
voidLink.previous = voidLink;
modCount++;
}
}
clear中的源码就是这样写的。
可能看出来,linkedList的每次操作后,都有一个modCount参数会自增,这个参数即使linkedList中保存操作数的参数

三、什么之后用ArrayList,什么时候用LinkedList?
  ArrayList与LinkedList实现了List接口,那么我们应该什么时候使用ArrayList,什么时候使用LinkedList呢?
  ArrayList的优势在于直接根据获取的位置找到数组的位置,然后获取存储在数组中的对象。但缺点是使用数组进行储存,当数组空间不够时,还需要新建更大容量的数组,并将原先的数据全部拷贝过去。而且在插入、删除数据时,由于是使用数组储存,需要将插入、删除位置及之后的所有数据都移动。
  LinkedList的优势在与有多少对象就新建多少节点,不会造成空间浪费,而且在插入、删除时可以不用移动后面的数据。但缺点在于每次得到指定位置的节点时,都需要从头部或者从尾部进行遍历。
  所以,当程序需要大量的插入、删除数据,或在头部、尾部插入数据时,使用LinkedList。如果是需要大量的获取指定位置的数据,那么使用ArrayList。