赞
踩
本文章分析LinkedList源码。
LinkedList采用的是双链表数据结构组成
transient Node<E> first;
transient Node<E> last;
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;
}
}
根据源码可以知道,它定义了一个它有一个Node内部类,作为链表里的节点,一个节点包含 E item、Node next、Node prev三个内容,其中item用来保存数据,next用于指向下一个节点Node,prev用来指向上一个节点。它还用transient 关键字定义了头节点和尾节点Node first和Node 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()方法时,由源码可知其本质是使用linkLast()方法,在此方法中有一个l节点指向了类定义的last节点,又创建了一个newNode节点,通过有参构造方法,将newNode的prev指向了l,元素e赋值给了item,next指向一个null,先将last节点指向newNode,再经过if语句判断如果prev指向的l节点为空,则说明是第一次添加元素,此newNode为头节点,将first指向newNode,否则通过l的next节点指向newNode,意为将新节点添加到尾部。
第一次添加元素:
第二次添加元素:
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
此方法意为将添加的元素作为链表的头部,其真正意义上使用的是linkFirst(e)方法加入,与add()方法的不同点在于final Node<E> f = first;
和 first = newNode
,它将f指向了最初的first,如果f为空说明此链表为空,则将last也指向newNode,否则将f的prev指向newNode,说明新加入元素为头节点。
public E get(int index) { checkElementIndex(index); return node(index).item; } private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isElementIndex(int index) { return index >= 0 && index < size; } Node<E> node(int index) { // assert isElementIndex(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查找指定元素item,此方法会先进入checkElementIndex方法,通过isElementIndex判断index是否大于0或者超过链表的容量size,大于或者超过将抛一个IndexOutOfBoundsException异常,没问题则进入node(index)构造方法中,此方法判断如果index小于链表容量size的一半,则通过next从头节点开始遍历找到对应节点,返回item对象,如果大于链表容量size的一半,则从通过prev从尾节点开始遍历找到对应节点,返回item对象。
public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } 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++; }
此方法可以在指定的index位置插入对象element,方法开始后先检查index是否在范围内并且大于0,否则抛出IndexOutOfBoundsException异常,index无误将会判断index是否为链表容量,如果是说明index指向尾部,则将元素放在尾部,不是则执行linkBefore(E e, Node succ)方法,此方法中的两个参数e是将加入的新元素,succ是通过node(index)找到的原来index位置的节点,将原位置的节点succ的prev指向pred,newNode的prev指向pred,item为e,next指向succ,如果pred为null,说明新节点插在头节点处,将first指向newNode,否则pred的next节点指向newNode,最终容量+1,修改次数+1。
插入元素图解:
public E remove() { return removeFirst(); } public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(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; }
此方法用于删除头节点,其本质使用的是removeFirst()方法,此方法中会判断f是否为空,为空抛异常,返回unlinkFirst(f)方法,在此方法中,会将头节点的元素item赋值给element对象,将next指向f的next节点,再将f的item和next都设置为null,最后将first指向next,如果next为null,说明此链表已空,则将last也指向null,否则再将next的prev节点指向null。最终减少一个容量,增加一次修改次数,返回被删除的元素element对象。
如图:
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } 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; }
此方法删除指定位置index处的节点,方法开始和之前方法一样会先检查index是否在范围内,不在则抛异常,之后进入unlink(Node x),此方法会通过node(index)拿到指定位置要删除的节点x,将x的item给element对象,next、prev分别指向新的Node next和Node prev节点,如果prev为空,说明删掉的节点为头节点,则将frist指向next,否则将prev的next指向next;如果next为空,则说明删除的节点为尾节点,则将last指向prev,否则将next的prev指向prev,最终将x的item指向null,容量-1,修改次数+1,返回被删除的元素对象element。
如图:
根据源码可以发现,方法中没有加锁,所以LinkedList是线程不安全的,通过get(int index)方法也可以发现它原理是从头或者尾部依次遍历寻找元素,所以它查找效率很低,但是它的增加和删除很方便,只需要改变next和prev的指向即可。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。