ArrayList和LinkedList简单讲讲

前言

昨天请假了,去银行签贷款去了,然后和女朋友去办护照了,发生了一件事。在银行打印资金证明时,被要求买他们的一款理财产品,理由是资金少了,需要对他们的产品进行一个覆盖。我的天,现在都这样了吗。没钱没人权吗?在和银行的工作人员狡辩了几句,大致内容如下,我有自己买理财产品,也是货币基金,如果我买你们的理财,我也不会动用用于首付款的钱。心里想,毕竟找你们借钱,你是爷,抱着能少说两句就少说两句的心态,没有继续往下争辩,私下和贷款岗的工作人员联系,他们给我的解决办法是,去其他支行打印资金证明,再来交给跟我签贷款的人,在这里我就不说是哪个银行了。很气愤。好了,不多说,生活中的小事,一笑而过。

开始

其实这篇文章在我的有道云笔记里面是分开两篇的,很久之前写的,现在翻出来看看,有很多废话,我就索性将他们合二为一,去其糟粕取其精华。这里说一下,我有时会在宿舍或者手机简单的用有道云做一下笔记,然后就会在公司的电脑上面,去排版,添加内容,整理格式,整理语句,因为之后公司的电脑才会有Hexo+Next的环境,今天星期六,调休过来加班。带薪划水。

正式开始

比较

ArrayList是一个基于动态数组实现的一个数据结构,LinkdeList是基于链表的一个数据结构

ArrayList就没什么看图的,一个数组,能自动扩容,LinkedList我从网上弄来一张图,帮助理解这个数据结构

这个就是LinkedList的数据结构,可以看到,他不仅维护了数组,还维护了前后两个节点,来关联数组的先后顺序

这里我理解的是:ArrayList就是一群小朋友排队站在一起,LindedList就是一群小朋友手拉手站在一起,这样在排队的时候(插入,删除)就会很快,不需要重新排位置,只需要两边的小朋友交换一下拉手的对象就好了

看了这个图,在来比较一下ArrayList和LinkedList的区别:

先来看看LinkedList,他相比ArrayList多维护了一个前后的两个节点,相当于利用了空间来换取时间,我们在快读删除或者插入元素的时候,就用LinkedList,在查询的时候就不应该用LinkedList了,因为LinkedList在查询的时候是需要不断的遍历,而ArrayList只需要找出下标就好了。

删除或者插入的时候LinkedList只需要动一下前后两个节点让他们重新关联上,而ArrayList需要将后面的节点往后面位移一位。

不废话了,看代码吧
ArrayList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* Appends the specified element to the end of this list.
* 将指定元素追加到列表的的尾部
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//进行扩容效验
ensureCapacityInternal(size + 1); // Increments modCount!!
//将值放到数组的末尾,然后将size自加1
elementData[size++] = e;
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
public void add(int index, E element) {
//验证index的有效性,如果索引超出数组的范围则抛出异常IndexOutof
rangeCheckForAdd(index);
//将值放到数组的末尾,然后将size自加1
ensureCapacityInternal(size + 1); // Increments modCount!!
//copy数据,将要插入的位置空出来,将后面的元素往后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//将空出来的位置,插入element
elementData[index] = element;
size++;
}

上面调用最终调用的扩容代码就是下面的grow方法。每次会扩容1.5倍

int newCapacity = oldCapacity + (oldCapacity >> 1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}

数据扩容校验,如果不带构造参数时(不指定大小时)会自动生成一个长度为10的Objecr类型的数组

1
2
3
4
5
6
7
8
9
10
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
LinkedList

这里有两个指针,一个指向头,一个指向尾,在代码里面会用来判断是否为空啊,来区分该节点是否是最后一个节点,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
transient int size = 0;

/**
* Pointer to first node.
//指向头节点的指针
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;

/**
* Pointer to last node.
//指向尾节点的指针
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;

看一下LinkedList的数据结构,这里维护了前后两个节点,上文说过了

1
2
3
4
5
6
7
8
9
10
11
12
//节点结构
private static class Node<E> {
E item;//数据
Node<E> next;//下一个节点(尾部)
Node<E> prev;//上一个节点(头部)

Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

这里我看了一下add的方法,add之后他会将数据放在最后,就会调用linkLast(E e)这个方法

代码里面都写了注释,这里就是将元素放进去,然后设置一下前后节点的位置,其实当时理解起来挺绕的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* Links e as first element.
*/
//设置为第一个节点
private void linkFirst(E e) {
//获取头节点
final Node<E> f = first;
//新建一个节点, 因为为双向链表,所以设置e节点为首节点时,头部为null,尾部,应该是first
final Node<E> newNode = new Node<>(null, e, f);
//将新建的节点设置成first节点。
first = newNode;
//如果首节点f没有,证明此链表为null,这个时候要设置最后一个节点也为当前节点
//否则将f节点的头部设置成新建的节点newNode
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* Links e as last element.
*/
//设置为最后一个节点
void linkLast(E e) {
//获取最后一个节点
final Node<E> l = last;
//新建一个节点,设置头部为最后一个节点L,尾部为null
final Node<E> newNode = new Node<>(l, e, null);
//复制给最后一个节点
last = newNode;
//如果最后一个节点为null,则将第一个节点设置为新建的节点
//否则,将最后一个节点的尾部设置为刚才新建的节点
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

这两个方法也是在操作数据结构的时候用的比较多的,主题内容也是在做手拉手操作,不能让这个链表断了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* Inserts element e before non-null Node succ.
*/
//将元素插入到指定的succ之前
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//假装succ不为null
//获取succ节点的头部
final Node<E> pred = succ.prev;
//新建一个节点将头部设置succ的头部,尾部设置为succ,就相当于替换了succ的前面关联的数据为新建的节点,然后尾部就设置为
//succ这个节点
final Node<E> newNode = new Node<>(pred, e, succ);
//将succ的头部设置成新建的节点,则newNode就在succ之前去了
succ.prev = newNode;
//如果succ没有头部,则证明succ为首节点,此时有数据插到前面来了,所以要改first
if (pred == null)
first = newNode;
else
//要设置succ和前面关联的节点的下一个节点,原来pred.next是succ,现在succ前面来了一个则要改
pred.next = newNode;
size++;
modCount++;
}
/**
* Unlinks non-null first node f.
*/
//删除第一个首节点
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//假设f是第一个节点,f不等于null
//获取f的值
final E element = f.item;
//获取f的下一个节点,可以理解为第二个节点,因为f为第一个节点
final Node<E> next = f.next;
//设置f的值为null和f的尾部为null,等待gc回收
f.item = null;
f.next = null; // help GC
//将f的下一节点设置成首节点
first = next;
//如果f的下一节点为null,证明这个链表里面只有一个元素就是f,删除之后就没了,所以设置last为null
if (next == null)
last = null;
else
//如果f的下一个节点不为null,就要将下一个节点的头部,设置为null,因为删除首节点之后,第二个节点到前面,他的头部就是null
next.prev = null;
size--;
modCount++;
return element;
}

indexOf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int indexOf(Object o) {
int index = 0;
//如果o为null
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
//如果item=null,返回索引
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
//判断对象o是否等于item,返回索引
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}

查找节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Node<E> node(int index) {
// assert isElementIndex(index);
// 首先会判断index处于前面还是后面 size >> 1 把当前链表/2
if (index < (size >> 1)) {
//从前面开始遍历
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//从后面开始遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
ArrayList扩容机制

ArrayList自动增加大小的机制是:向ArrayList里面添加对象,如果当前对象的长度+1大于原数组的长度,则调用grow扩容

扩容的容量为当前数组长度的1.5倍并且复制出来一个新数组,原数组自动抛弃(java垃圾回收机制会自动回收)。

size则在向数组添加对象,自增1。

-------------本文结束感谢您的阅读-------------
0%