LinkedList作为一个常用的集合在我们项目开发当中经常会用到，它经常会拿来和ArrayList做比较，那我们今天就通过源码来解析下它内部的实现原理
构造方法
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
new了一个Link类，这个Link类包括：添加的数据data，链表上个对象和下个对象的引用；因为是初始化所以它的数据是null，对上一个和下一个的引用也是自己本身。
添加方法
@Override
public void add(int location, E object) {
//如果location大于等于0，并且location小于等于size执行下面操作
// 否则越界异常
if (location >= 0 && location <= size) {
Link<E> link = voidLink;
//如果location小于总大小的1/2,就从链表的尾部找
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
//如果location大于等于总大小的1/2,就从链表的头部找
for (int i = size; i > location; i--) {
link = link.previous;
}
}
//插入到location位置
Link<E> previous = link.previous;
Link<E> newLink = new Link<E>(object, previous, link);
previous.next = newLink;
link.previous = newLink;
size++;
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
}
当我们调用add(E e)方法的同时，方法内部又调用了add(int location, E object)方法，location是要添加数据的位置，下面我们通过一张图来看一下它的add机制。
QQ图片20170123105921.jpg
如果location是1，那么就从0开始循环找，然后把要添加的数据添加到0和1之间；
如果location是3，那么就从voidLinked header开始找，然后把数据添加到2和3之间。
再来看看其他add方法
public boolean addAll(Collection<? extends E> collection) {
int adding = collection.size();
if (adding == 0) {
return false;
}
Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;
Link<E> previous = voidLink.previous;
//下面代码的逻辑就是：从链表的头开始插入数据，
// 最后一条数据是在链表头上面的数据
for (E e : elements) {
Link<E> newLink = new Link<E>(e, previous, null);
previous.next = newLink;
previous = newLink;
}
previous.next = voidLink;
voidLink.previous = previous;
size += adding;
modCount++;
return true;
}
addFirst方法
public void addFirst(E object) {
addFirstImpl(object);
}
//把object添加到链表的最尾部，因为我们取数据的时候是从尾部开始取的
private boolean addFirstImpl(E object) {
Link<E> oldFirst = voidLink.next;
Link<E> newLink = new Link<E>(object, voidLink, oldFirst);
voidLink.next = newLink;
oldFirst.previous = newLink;
size++;
modCount++;
return true;
}
addLast方法
public void addLast(E object) {
addLastImpl(object);
}
//把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;
}
get方法
@Override
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();
}
跟添加数据获取location位置数据的逻辑是一致的，这边就不细说了。
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;
}
}
//把locaiton位置的对象的上面和下面的对象关联起来
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}
查找数据的逻辑和取值的逻辑是一致的，然后就是把location位置对象的上面和下面对象关联起来。
@Override
public boolean remove(Object object) {
return removeFirstOccurrenceImpl(object);
}
//最后调用了此方法
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;
}
循环遍历，通过equals方法对比找到相同的数据，然后删除。
总结
LinkedList内部存储数据是以链表的形式存储的，查询数据需要从链表头或尾循环取值，所以会比ArrayList查询慢，添加和删除数据差不多，在特定的情况下添加数据ArrayList会稍慢，其他方法差别不会特别大。
