源码阅读之LinkedList（JDK8）
2018-06-18 00:34:42来源：未知 阅读 ()
inkedList概述
LinkedList是List和Deque接口的双向链表的实现。实现了所有可选列表操作，并允许包括null值。
LinkedList既然是通过双向链表去实现的，那么它可以被当作堆栈、队列或双端队列进行操作。并且其顺序访问非常高效，而随机访问效率比较低。
注意，此实现不是同步的。 如果多个线程同时访问一个LinkedList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。这通常是通过同步那些用来封装列表的 对象来实现的。但如果没有这样的对象存在，则该列表需要运用{@link Collections#synchronizedList Collections.synchronizedList}来进行“包装”，该方法最好是在创建列表对象时完成，为了避免对列表进行突发的非同步操作。
List list = Collections.synchronizedList(new LinkedList(...));
类中的iterator()方法和listIterator()方法返回的iterators迭代器是fail-fast的：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。
LinkedList的源码阅读
- 底层结构
节点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; } }
LinkedList结构：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
//LinkedList包含的元素个数 transient int size = 0; /** * Pointer to first node. 首节点 * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ 首节点和尾节点要么同时为null, 不可能一个为null,一个不为null transient Node<E> first; /** * Pointer to last node. 尾节点 * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last;
- 构造函数
LinkedList提供了两种种方式的构造器，构造一个空列表、以及构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回的顺序排列的。
public LinkedList() { } // 构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回的顺序排列的
public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
- 添加元素
LinkedList提供了头插入addFirst(E e)、尾插入addLast(E e)、add(E e)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)、add(int index, E element)这些添加元素的方法。
// 添加
public boolean add(E e) {
// 在链表尾部插入 linkLast(e); return true; } // 插入 public void add(int index, E element) {
// 插入范围检查 checkPositionIndex(index); if (index == size)
// 在链表尾部添加 linkLast(element); else
// 在链表中间插入 linkBefore(element, node(index)); } // 头插入 public void addFirst(E e) { linkFirst(e); } // 尾插入 public void addLast(E e) { linkLast(e); }
/**
* 按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此链表的尾部
* 如果指定的集合添加到链表的尾部的过程中，集合被修改，则该插入过程的后果是不确定的。
* 一般这种情况发生在指定的集合为该链表的一部分，且其非空。
* @throws NullPointerException 指定集合为null
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c); } //从指定的位置开始，将指定collection中的所有元素插入到此链表中，新元素的顺序为指定collection的迭代器所返回的元素顺序 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; //succ指向当前需要插入节点的位置，pred指向其前一个节点 if (index == size) {//说明在列表尾部插入集合元素 succ = null; pred = last; } else { succ = node(index); //得到索引index所对应的节点 pred = succ.prev; } //指定collection中的所有元素依次插入到此链表中指定位置的过程 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o;
//将元素值e，前继节点pred“封装”为一个新节点newNode Node<E> newNode = new Node<>(pred, e, null); if (pred == null) //如果原链表为null，则新插入的节点作为链表首节点 first = newNode; else pred.next = newNode; pred = newNode; //pred指针向后移动，指向下一个需插入节点位置的前一个节点 } //集合元素插入完成后，与原链表index位置后面的子链表链接起来 if (succ == null) { //说明之前是在列表尾部插入的集合元素 last = pred; //pred指向的是最后插入的那个节点 } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; }
细读上面的代码linkLast，linkBefore，linkFirst，linkLast
1. linkLast
// 尾插入，即将节点值为e的节点设置为链表的尾节点
void linkLast(E e) {
// 获取当前尾结点引用 final Node<E> l = last;
//构建一个prev值为l,节点值为e,next值为null的新节点newNode final Node<E> newNode = new Node<>(l, e, null);
//将newNode作为尾节点 last = newNode;
//如果原尾节点为null，即原链表为null，则链表首节点也设置为newNode if (l == null) first = newNode; else //否则，原尾节点的next设置为newNode l.next = newNode; size++; modCount++; }
当last==null时, fisrt 和 last 都是同一个node,该弄得的p和n都为null,不指向任何节点
当last != null时，第一步，构建newNode的时候把newNode的p指向了原先的lastNode,第二步，把newNode复制给lastNode,第三步，把原先的lastNode的n指向newNode
2. linkBefore
//中间插入，在非空节点succ之前插入节点值e
void linkBefore(E e, Node<E> succ) { //获取给定结点的上一个结点引用 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++; }
当succ.pred != null时，开始的数据结构如下：
第一步，新构建一个newNode，把newNode的p指向succ的前一个节点，把newNode的n指向succ。
第二步，将succ节点的p指向 从succ.prev转移到newNode上。
第三步，将succ的前一个节点的n指向 从succ转移到newNode上。
当succ.pred == null时，和上面差不多，只是第三步的时候直接把newNode设置为首节点。
3. linkFirst
//头插入，即将节点值为e的节点设置为链表首节点
private void linkFirst(E e) { final Node<E> f = first;
//构建一个prev值为null,节点值为e,next值为f的新节点newNode final Node<E> newNode = new Node<>(null, e, f);
//将newNode作为首节点 first = newNode;
//如果原首节点为null，即原链表为null，则链表尾节点也设置为newNode if (f == null) last = newNode; else //否则，原首节点的prev设置为newNode f.prev = newNode; size++; modCount++; }
linkLast
// 尾插入，即将节点值为e的节点设置为链表的尾节点
void linkLast(E e) {
// 获取当前尾结点引用 final Node<E> l = last;
//构建一个prev值为l,节点值为e,next值为null的新节点newNode final Node<E> newNode = new Node<>(l, e, null);
//将newNode作为尾节点 last = newNode;
//如果原尾节点为null，即原链表为null，则链表首节点也设置为newNode if (l == null) first = newNode; else //否则，原尾节点的next设置为newNode l.next = newNode; size++; modCount++; }
- 删除元素
LinkedList提供了头删除removeFirst()、尾删除removeLast()、remove(int index)、remove(Object o)、clear()这些删除元素的方法。
// 删除首结点，返回存储的元素
public E removeFirst() {
// 获取首结点引用 final Node<E> f = first; if (f == null) throw new NoSuchElementException();
// 删除首结点，返回存储的元素 return unlinkFirst(f); } // 删除尾结点，返回存储的元素 public E removeLast() {
// 获取尾结点引用 final Node<E> l = last; if (l == null) throw new NoSuchElementException();
// 删除尾结点，返回存储的元素 return unlinkLast(l); } //删除指定元素，默认从first节点开始，删除第一次出现的那个元素 public boolean remove(Object o) {
//会根据是否为null分开处理。若值不是null，会用到对象的equals()方法 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; } // 删除指定位置的元素，返回之前元素 public E remove(int index) {
// 判断指定位置是否合法 checkElementIndex(index);
// 删除指定位置的结点，返回之前元素 return unlink(node(index)); } // 删除所有元素 public void clear() {
//遍历链表，删除所有结点,方便gc回收垃圾
for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; }
// 首尾结点置空 first = last = null;
// 元素数量置0 size = 0; modCount++; }
细读remove里面的代码unlink，unlinkFirst，unlinkLast
1. unlink
// 删除指定非空结点，返回存储的元素
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 {
// 将前一个节点的next指向指定节点的后一个节点，并把指定节点的prev清空 prev.next = next; x.prev = null; } // 如果后一个节点为空，说明指定节点为尾节点，只需将指定节点的前一个节点设置为尾节点即可 if (next == null) { last = prev; } else {
// 将后一个节点的prev指向指定节点的前一个节点，并把指定节点的next清空 next.prev = prev; x.next = null; } // 指定节点的存储元素清空 x.item = null;
// 元素数量-1 size--; modCount++; return element; }
初始状态：
第一步，将指定节点的前一个节点的next指向指定节点的后一个节点，然后将指定节点的prev清空。
第二步，将指定节点的后一个接的的prev指向指定节点的前一个节点，然后将指定节点的next清空。
最后的效果
2. unlinkFirst
// 删除首结点，返回存储的元素，内部使用
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;
// 如果首节点的后一个节点为空，说明容器里只有一个节点，所以删除了首节点，容器为空，首节点和尾节点都设置为null if (next == null) last = null; else // 把新的首节点的prev清空
next.prev = null; size--; modCount++; return element; }
3. unlinkLast
// 删除尾结点，返回存储的元素，内部使用
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 // 把新的尾节点的next清空
prev.next = null; size--; modCount++; return element; }
- 修改元素
// 修改指定位置的元素，返回之前元素
public E set(int index, E element) {
// 判断指定位置是否合法 checkElementIndex(index);
// 获取指定位置的结点 Node<E> x = node(index);
// 获取该结点存储的元素 E oldVal = x.item;
// 修改该结点存储的元素 x.item = element;
// 返回该结点存储的之前的元素 return oldVal; }
- 查询元素
LinkedList提供了getFirst()、getLast()、contains(Object o)、get(int index)、indexOf(Object o)、lastIndexOf(Object o)这些查找元素的方法。
//返回列表首节点元素值 public E getFirst() { final Node<E> f = first; if (f == null) //如果首节点为null throw new NoSuchElementException(); return f.item; } //返回列表尾节点元素值 public E getLast() { final Node<E> l = last; if (l == null) //如果尾节点为null throw new NoSuchElementException(); return l.item; } //判断列表中是否包含有元素值o，返回true当列表中至少存在一个元素值e，使得(o==null?e==null:o.equals(e)) public boolean contains(Object o) { return indexOf(o) != -1; } //返回指定索引处的元素值 public E get(int index) { checkElementIndex(index); //index >= 0 && index < size return node(index).item; //node(index)返回指定索引位置index处的节点 } //正向查找，返回LinkedList中元素值Object o第一次出现的位置，如果元素不存在，则返回-1 public int indexOf(Object o) { int index = 0; //由于LinkedList中允许存放null，因此下面通过两种情况来分别处理 if (o == null) { for (Node<E> x = first; x != null; x = x.next) { //顺序向后 if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } //逆向查找，返回LinkedList中元素值Object o最后一次出现的位置，如果元素不存在，则返回-1 public int lastIndexOf(Object o) { int index = size; //由于LinkedList中允许存放null，因此下面通过两种情况来分别处理 if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { //逆向向前 index--; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }
细看里面的一个node()方法，通过下标定位时先判断是在链表的上半部分还是下半部分，如果是在上半部分就从头开始找起，如果是下半部分就从尾开始找起，因此通过下标的查找和修改操作的时间复杂度是O(n/2)。
//返回指定索引位置的节点 Node<E> node(int index) { // assert isElementIndex(index); //折半思想，当index < size/2时，从列表首节点向后查找 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //当index >= size/2时，从列表尾节点向前查找 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
- Fail-Fast机制
LinkedList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
- 遍历方式
LinkedList不提倡运用随机访问的方式进行元素遍历。
1）通过迭代器Iterator遍历：
Iterator iter = list.iterator();
while (iter.hasNext())
{
System.out.println(iter.next());
}
2）通过迭代器ListIterator遍历：
ListIterator<String> lIter = list.listIterator();
//顺向遍历
while(lIter.hasNext()){
System.out.println(lIter.next());
}
//逆向遍历
while(lIter.hasPrevious()){
System.out.println(lIter.previous());
}
3）foreach循环遍历
for(String str:list)
{
System.out.println(str);
}
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
上一篇：常用类（上）
- 你说研究过Spring里面的源码，循环依赖你会么？ 2020-06-09
- 通俗理解spring源码（六）—— 默认标签（import、alias、be 2020-06-07
- 数据结构:用实例分析ArrayList与LinkedList的读写性能 2020-06-04
- 学习源码的第八个月，我成了Spring的开源贡献者 2020-06-02
- java 在线网络考试系统源码 springboot mybaits vue.js 前后 2020-05-31
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
