LinkedList是基于双向链表实现的，相比与内部使用数组的ArrayList而言LinkedList查询比较慢（因为链表不用在连续的存储空间），添加、删除效率比较高（因为只需要修改前驱结点和后继结点的指针可以实现)。因此，对于添加，删除比较多的情况下，推荐使用LinkedList。本文基于android-23源码分析。
源码分析
LinkedList继承和实现的接口
public class LinkedList<E> extends AbstractSequentialList<E> implements
List<E>, Deque<E>, Queue<E>, Cloneable, Serializable {}
Cloneable：通过实现clone()方法，能够实现克隆对象；
Serializable：LinkedList支持序列化，和反序列化，实现Serializble接口之后能够进行序列化传输；
LinkedList的构造函数
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
public LinkedList(Collection<? extends E> collection) {
this();
addAll(collection);
}
在LinkedList的构造函数当中，会先创建一个Link的对象voidLink结点，这个Link是LinkedList的一个内部类，它维护一个结点数据，前驱结点以及后继结点，创建出来的voidLink的pervious和next分别指向当前创建的Link对象。
我们先来看看Link类的定义：
private static final class Link<ET> {
//当前节点数据
ET data;
//previous前驱结点，next后继结点
Link<ET> previous, next;
Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}
如果在LinkedList的构造函数中传递了collection集合变量，那么最后还会调用addAll方法。
添加元素的方法
@Override
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) {
//创建newLink结点
Link<E> newLink = new Link<E>(e, previous, null);
//previous结点的后继结点指向当前创建的结点
previous.next = newLink;
//previous 结点指向当前创建的结点
previous = newLink;
}
//previous结点的后继结点指向LinkedList的当前结点
previous.next = voidLink;
//当前结点的前驱结点指向previous结点
voidLink.previous = previous;
//当前的数量增加
size += adding;
//当前修改的标记增加
modCount++;
return true;
}
在addAll的方法中，先拿到需要添加的元素的集合，然后循环遍历，在遍历的过程中不断创建新的结点，然后将前一个结点的后继结点指向当前创建的结点，然后将前一个结点指向当前创建的结点，循环完了之后，将前一个结点的后继结点指向LinkedList中的当前结点，然后将当前结点的前驱结点指向前一个结点，修改size和modCount的值，完成添加工作。
现在我们看看其他的add方法：
@Override
public boolean add(E object) {
return addLastImpl(object);
}
public void addLast(E object) {
addLastImpl(object);
}
private boolean addLastImpl(E object) {
//LinkedList的voidLink的前驱结点
Link<E> oldLast = voidLink.previous;
//创建一个newLink结点，newLink的前驱结点指向oldLast，后继结点指向voidLink
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
//voidLink的前驱结点指向newLink
voidLink.previous = newLink;
//oldLast的后继结点指向newLink
oldLast.next = newLink;
size++;
modCount++;
return true;
}
oldLast结点指向voidLink结点的前驱结点，创建一个newLink结点，newLink的前驱结点指向oldLast，后继结点指向voidLink，然后将voidLink的前驱结点指向newLink，oldLast的后继结点指向newLink，这样操作过后，就将新创建的newLink结点插入到oldLast和voidLink中间。
public void addFirst(E object) {
addFirstImpl(object);
}
private boolean addFirstImpl(E object) {
//oldFirst指向voidLink的后继结点
Link<E> oldFirst = voidLink.next;
//创建newLink结点
Link<E> newLink = new Link<E>(object, voidLink, oldFirst);
//voidLink的后继结点指向newLink结点
voidLink.next = newLink;
//oldFirst的前驱结点指向newLink结点
oldFirst.previous = newLink;
size++;
modCount++;
return true;
}
首先oldFirst指向voidLink的后继结点，然后创建newLink结点，voidLink的后继结点指向newLink结点，最后oldFirst的前驱结点指向newLink结点，并且修改size，modCount的值。
public void addLast(E object) {
addLastImpl(object);
}
private boolean addLastImpl(E object) {
//oldLast结点指向voidLink的前驱结点
Link<E> oldLast = voidLink.previous;
//创建newLink结点，前驱结点为oldLast，后继结点为voidLink
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
//
voidLink.previous = newLink;
oldLast.next = newLink;
size++;
modCount++;
return true;
}
@Override
public boolean addAll(int location, Collection<? extends E> collection) {
if (location < 0 || location > size) {
throw new IndexOutOfBoundsException();
}
int adding = collection.size();
if (adding == 0) {
return false;
}
Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;
//previous 指向voidLink
Link<E> previous = voidLink;
if (location < (size / 2)) {
for (int i = 0; i < location; i++) {
//将previous结点指向previous的后继结点
previous = previous.next;
}
} else {
for (int i = size; i >= location; i--) {
//将previous结点指向previous的前驱结点
previous = previous.previous;
}
}
//next结点指向previous的next
Link<E> next = previous.next;
//通过foreach语法糖循环遍历元素的集合
for (E e : elements) {
//创建newLink结点，前驱结点为previous，后继结点为null
Link<E> newLink = new Link<E>(e, previous, null);
//previous结点的后继结点指向newLink
previous.next = newLink;
//previous指向newLink
previous = newLink;
}
//previous结点的后继结点指向next
previous.next = next;
//next结点的前驱结点指向previous
next.previous = previous;
size += adding;
modCount++;
return true;
}
添加的方法，我们主要就看这些，当然还有另外的一些添加元素的方法，
public void push(E e) {
addFirstImpl(e);
}
另外的，我们就不多介绍了，下面我们来看看移除元素的方法
删除方法
移除第一个元素
public E removeFirst() {
return removeFirstImpl();
}
private E removeFirstImpl() {
//first结点指向voidLink的后继结点
Link<E> first = voidLink.next;
//判断是否有可移除的结点
if (first != voidLink) {
//next结点指向first的后继结点
Link<E> next = first.next;
//voidLink的后继结点指向next
voidLink.next = next;
//next结点的前驱结点指向voidLink
next.previous = voidLink;
size--;
modCount++;
return first.data;
}
throw new NoSuchElementException();
}
通过location移除元素
@Override
public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
//通过location找到link结点
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();
}
remove（int location）的时候，先判断location是否越界，如果没有越界则继续往下执行，通过循环找到link结点，然后分别拿到link结点的前驱结点和后继结点，让他们分别修改应用的指向，从而达到从链表中删除结点的目的。
@Override
public void clear() {
if (size > 0) {
size = 0;
//重置voidLink结点的前驱结点，后继结点指向
voidLink.next = voidLink;
voidLink.previous = voidLink;
//修改modCount变量
modCount++;
}
}
clear方法会重置voidLink结点的前驱结点，后继结点指向。
获取元素
@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();
}
相比较ArrayList这类可以使用index下标获取元素的数组来说，LinkedList通过location来获取元素，它需要循环遍历，这种随机的获取元素的方法效率比较低。
LinkedList的Iterator
先来看看ReverseLinkIterator：
private class ReverseLinkIterator<ET> implements Iterator<ET> {
private int expectedModCount;
private final LinkedList<ET> list;
private Link<ET> link;
private boolean canRemove;
ReverseLinkIterator(LinkedList<ET> linkedList) {
list = linkedList;
expectedModCount = list.modCount;
link = list.voidLink;
canRemove = false;
}
public boolean hasNext() {
return link.previous != list.voidLink;
}
public ET next() {
if (expectedModCount == list.modCount) {
if (hasNext()) {
link = link.previous;
canRemove = true;
return link.data;
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}
public void remove() {
if (expectedModCount == list.modCount) {
if (canRemove) {
Link<ET> next = link.previous;
Link<ET> previous = link.next;
next.next = previous;
previous.previous = next;
link = previous;
list.size--;
list.modCount++;
expectedModCount++;
canRemove = false;
return;
}
throw new IllegalStateException();
}
throw new ConcurrentModificationException();
}
}
private static final class LinkIterator<ET> implements ListIterator<ET> {
int pos, expectedModCount;
final LinkedList<ET> list;
Link<ET> link, lastLink;
LinkIterator(LinkedList<ET> object, int location) {
list = object;
expectedModCount = list.modCount;
if (location >= 0 && location <= list.size) {
// pos ends up as -1 if list is empty, it ranges from -1 to
// list.size - 1
// if link == voidLink then pos must == -1
link = list.voidLink;
if (location < list.size / 2) {
for (pos = -1; pos + 1 < location; pos++) {
link = link.next;
}
} else {
for (pos = list.size; pos >= location; pos--) {
link = link.previous;
}
}
} else {
throw new IndexOutOfBoundsException();
}
}
public void add(ET object) {
if (expectedModCount == list.modCount) {
Link<ET> next = link.next;
Link<ET> newLink = new Link<ET>(object, link, next);
link.next = newLink;
next.previous = newLink;
link = newLink;
lastLink = null;
pos++;
expectedModCount++;
list.size++;
list.modCount++;
} else {
throw new ConcurrentModificationException();
}
}
public boolean hasNext() {
return link.next != list.voidLink;
}
public boolean hasPrevious() {
return link != list.voidLink;
}
public ET next() {
if (expectedModCount == list.modCount) {
LinkedList.Link<ET> next = link.next;
if (next != list.voidLink) {
lastLink = link = next;
pos++;
return link.data;
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}
public int nextIndex() {
return pos + 1;
}
public ET previous() {
if (expectedModCount == list.modCount) {
if (link != list.voidLink) {
lastLink = link;
link = link.previous;
pos--;
return lastLink.data;
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}
public int previousIndex() {
return pos;
}
public void remove() {
if (expectedModCount == list.modCount) {
if (lastLink != null) {
Link<ET> next = lastLink.next;
Link<ET> previous = lastLink.previous;
next.previous = previous;
previous.next = next;
if (lastLink == link) {
pos--;
}
link = previous;
lastLink = null;
expectedModCount++;
list.size--;
list.modCount++;
} else {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}
public void set(ET object) {
if (expectedModCount == list.modCount) {
if (lastLink != null) {
lastLink.data = object;
} else {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}
}
网友评论