本版本基于android-19 sdk源码分析
本文章只分析android 中的linkedlist源码.如果想看java中linkedlist源码，请移步，其实原理都差不多。
其中1.6jdk和1.7jdk版本中linkedlist结构有所不同，1.6中链表是循环 链表。1.7中链表是非循环链表。本次分析的是循环链表
Linkedlist 底层实现是链表，链表的优点是插入删除快，查询慢。
Linkedlist 构造方法：
/**
* Constructs a new empty instance of .
*/
public LinkedList() {
//给voidLink 创建对象，他的previous和next都指向自己
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
transient Link<E> voidLink;
这个变量是记录链表的最后一个位置。它的previous指向的是当前链表中真实数据最后一个元素。next指向的是当前链表中的真实数据第一个元素。
如图所示：
Add 方法：
- 直接插入一个对象。
/**
* 原理是在voidLink和上一个元素中间插入新的元素
* voidLink.previous指向的是最后一个元素
* voidLink.next指向的是链表中的第一个元素
*/
private boolean addLastImpl(E object) {
//获取当前节点previous保存的对象，如果是第一次插入应该是null
Link<E> oldLast = voidLink.previous;
//创建一个新的元素，把obj保存到元素中，新元素的previous节点指向oldLast，
//next节点指向最后一个元素，
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
//给最后一个节点的previous赋值为新元素
voidLink.previous = newLink;
//上一个元素的next节点指向新元素
oldLast.next = newLink;
//元素值自增
size++;
modCount++;
return true;
}
原理如图所示：
-
当没有增加数据
image.png -
当增加一个数据 oldLast = voidLinked；
image.png -
当增加两个数据 oldLast = o linkde；
image.png
其实就是在链表最后重新插入了一条数据。
- 在指定位置插入一个对象。
public void add(int location, E object) {
//插入位置大于等于零，并且插入位置小于等于当前元素总数，防止数组越界
if (location >= 0 && location <= size) {
//获取到最后一个元素，这个元素的previous指向的是本链表中存储的最后一个元素，
//next指向的是null。
Link<E> link = voidLink;
//判断插入位置是否是小于当前元素大小的一半
//如果小于一半则通过元素的next去查找
//如果大于一半则通过元素的previous去查找
//这种方式可以更快的找到插入位置
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;
//创建一个新的元素对象，并把obj放入，
//他的previous指向上一个元素，next指向下一个元素
Link<E> newLink = new Link<E>(object, previous, link);
//上一个元素的next指向新的元素
previous.next = newLink;
//下一个元素的previous指向新的元素
link.previous = newLink;
size++;
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
}
实现原理为，在指定位置改变了上一个元素next和下一个元素的previous指向。在指定位置对象和上一个元素中间插入了本对象。
分析到这里，是不是发现链表的插入比数组快呢，因为数组每次插入都需要给插入位置之后的元素移动，而链表不需要，只需要改变插入位置的指针指向就可以了。
Remove 方法：
- 移除指定位置元素
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;
//把删除元素的上一元素的next节点指向删除元素的下一个元素位置
previous.next = next;
//把删除元素的下一个元素的previous节点指向删除元素的上一个元素位置
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}
- 移除指定对象。
public boolean remove(Object object) {
return removeFirstOccurrenceImpl(object);
}
private boolean removeFirstOccurrenceImpl(Object o) {
//创建一个迭代器便于遍历链表中数据
Iterator<E> iter = new LinkIterator<E>(this, 0);
return removeOneOccurrence(o, iter);
}
private boolean removeOneOccurrence(Object o, Iterator<E> iter) {
//遍历元素
while (iter.hasNext()) {
E element = iter.next();
//当移除对象不为空，并且链表中存在时，移除
if (o == null ? element == null : o.equals(element)) {
iter.remove();
return true;
}
}
return false;
}
LinkIterator remove 方法
public void remove() {
if (expectedModCount == list.modCount) {
if (lastLink != null) {
//当前需要删除元素的下一个元素
Link<ET> next = lastLink.next;
//当前需要删除元素的上一个元素
Link<ET> previous = lastLink.previous;
//下一个元素的previous节点指向上一个元素
next.previous = previous;
//上一个元素的next节点指向下一个元素
previous.next = next;
if (lastLink == link) {
pos--;
}
link = previous;
//给当前删除元素滞空
lastLink = null;
expectedModCount++;
list.size--;
list.modCount++;
} else {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}
可以看出，删除指定对象和删除某个位置元素原理差不多。
因为删除原理和加入原理都是链表指针变换，因此这里不再画图。
总结
底层是双向链表存储数据,并且记录了头节点和尾节点
添加元素非常快,如果是添加到头部和尾部的话更快,因为已经记录了头节点和尾节点,只需要链接一下就行了. 如果是添加到链表的中间部分的话,那么多一步操作,需要先找到添加索引处的元素(因为需要链接到这里),才能进行添加.
遍历的时候,建议采用forEach()进行遍历,这样可以在每次获取下一个元素时都非常轻松(next = next.next;). 然后如果是通过fori和get(i)的方式进行遍历的话,效率是极低的,每次get(i)都需要从最前面(或者最后面)开始往后查找i索引处的元素,效率很低.
删除也是非常快,只需要改动一下指针就行了,代价很小.
linkedList的源码就分析到这里，思考一个问题。
有一个数据为0-2k，如果需要翻转数据，需要用那个类比较好，应该怎么翻转呢！
结合linkedList是双向回环链表结构，因此如果要数据翻转，只需要每个数据的pre指针和next指针指向对换即可！
