LinkedList源码浅析
2019-03-03 本文已影响0人
Duzzi
LinkedList
- 实现了List接口和Deque接口的双向链表，实现了list的所有操作，并且允许包括null的任何元素。
- 所有的操作都是基于双向链表，通过索引查找会从头部或者尾部开始查找，以确定哪个更接近目标索引。
- 非同步，线程不安全。
- 由于底层实现是链表，对于增删只需链表节点指针即可，所以效率相对ArrayList来说效率更高。
1.构造方法
构造方法基本上没干啥
节点个数
transient int size = 0;
//头部节点
transient Node<E> first;
//尾部节点
transient Node<E> last;
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
节点Node
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;
}
}
2.get相关方法
getFirst和getLast很简单，直接通过属性里的first和last节点判断，如果没有元素就会抛出异常。
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
根据index查找元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//返回索引对应的非null元素
Node<E> node(int index) {
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;
}
}
- 判断index是否越界，如果越界就会抛出IndexOutOfBoundsException异常
- 如果index小于size的一半，就从头部节点开始遍历顺序查找，否则从尾部节点开始遍历逆序查找。
可以看出这里的查找简单粗暴，所以LinkedList的索引查找效率并不高
3.remove相关方法
remove和removeLast是一样的，重点关注unlinkFirst
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
- 将first节点的元素和next都设置为null，方便gc
- 将第二个节点赋值给first节点，
- 如果第二个节点是null，即该链表为空；否则将第二个节点的头部指针设为null
- size-1
- modCount+1
modCount：迭代遍历的时候会有一个初始modCount，如果迭代遍历的过程中modCount发生了变化，那么就会抛出并发修改异常
removeLast和removeFirst类似
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
remove(Object object)与remove(int index)
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
remove的最后操作还是在unlink删除节点上：（假设现在要移除的是节点A）
- 如果A的prev==null，即A元素就是first节点，那么将A的next指向的节点直接赋值给
first节点；否则将前一个节点的next指针指向A元素的下一个节点，并将A元素的prev置为null - 如果A的next==null，即A元素就是last节点，那么将A的pre指向的节点赋值给last节点；否则将A的下一个节点的prev指针指向A的pre指向的节点，并将A的next置为null
- 将A节点的item置为null
4.size--
5.modCount++
4.add操作
add(obj)，实际上就是修改了原有节点的next，并将添加的obj设置为last节点
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
add(int index, E element)
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)//index就是最后的位置，直接在尾部追加
linkLast(element);
else//否则查找index所在的节点，并对改节点做修改
linkBefore(element, node(index));
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
addAll()其实原理和上面的类似
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
总结
- LinkedList的增删实际上就是修改链表中节点指针的指向，而ArrayList增删都涉及到了数组的拷贝，从效率上来说LinkedList更高
- LinkedList的索引查找只是简单的折半后进行逆序或者正序查找，而ArrayList底层基于数组实现，直接访问下标进行查找，所以ArrayList的查找效率更高
- 基于链表的LinkedList还可以当做栈和队列来使用
- 每次修改LinkedList的结构时，都会修改modCount。迭代遍历的时候是通过modCount判断是否要抛出并发修改异常
