【JDK8源码】LinkedList集合

LinkedList特性

双向链表，增删快，随机访问慢（相对ArrayList）
泛型类，可存储任意类型
离散空间，不需要主动扩容

LinkedList数据结构

 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底层的数据结构是双向链表（jdk1.7之前是双向循环链表），即为双向数据链结构，每一个节点存放了一个Node，Node又有三个属性，item：实际存入的元素，next：下一个结节点的引用，prev：前一个节点的引用，各个Node之间手拉手构成了一个双向链表。

源码分析

层次结构

在这里插入图片描述

LinkedList被声明为LinkedList<E>，表示LinkedList可以存储任意类型
AbstractSequentialList：继承自AbstractList，Abstract List提供了随机访问，ArrayList就是继承于AbsctractList，而AbstractSequentialList实现了List的一些主要方法，比如set(),get(),remove(),降低了接口的复杂度，提供的是顺序访问，实现的所有方法都是调用的 ListIterator 相关方法。
List：一个元素存取有序的集合，实现List接口能进行队列操作。
Deque：双端队列，继承自Queue，表示LinkedList可以作为双端队列使用，可以从列表的两端进行插入和删除操作。
Cloneable：实现该接口后可使用OBject.Clone()方法，否则会抛出异常
Serializable：序列化接口，表示该类可以被序列化。

属性

 //链表元素节点的个数 transient int size = 0; //指向链表的第一个元素 transient Node<E> first; //指向链表的最后一个元素 transient Node<E> last; //内部类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; } }

构造函数

 //无参构造函数 public LinkedList() { } //有参构造方法，将参数集合添加到创建的集合中 public LinkedList(Collection<? extends E> c) { this(); addAll(c); }

多处调用的方法

   //校验传入的index是否在范围内 private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //根据index查找集合中的某个节点，因为需要遍历查找，不能随机访问，所以效率比Array List低 Node<E> node(int index) { // assert isElementIndex(index); //如果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; } }

常用方法

addFirst(E e)：将元素插入到集合的第一个节点

 public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { //先取出原本在链表first的节点 final Node<E> f = first; //创建一个新的节点，上一个节点引用为null，存储元素为e，下一个节点的引用为之前的Frist节点f final Node<E> newNode = new Node<>(null, e, f); //将新的节点设置为frist节点 first = newNode; //如果之前的frist节点为空 if (f == null) //则把当前的节点设置为last节点 last = newNode; else //否则把原Frist节点的prev设置为当前的节点 f.prev = newNode; //集合长度增加 size++; modCount++;
  }

addLast(E e)和add(E e),都是将元素插入到集合的末尾

  public void addLast(E e) { linkLast(e);
  } void linkLast(E e) { //创建一个节点保存当前集合的最后一个节点 final Node<E> l = last; //创建一个前节点为当前集合的最后一个节点，后节点为null，节点值为node的节点 final Node<E> newNode = new Node<>(l, e, null); //将当前集合的last设置为新的节点 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) { //首先判断index是否在集合长度内，如果没有则抛出异常 checkPositionIndex(index); //如果index刚好等于集合的长度值，则直接调用插入到最末尾的方法 if (index == size) 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++;
  }
  //传入的参数为当前需要添加的元素和原index处的节点 void linkBefore(E e, Node<E> succ) { // assert succ != null; //将原来index节点的前节点引用保存到新的节点 final Node<E> pred = succ.prev; //创建一个新的节点，前节点引用为pred，当前元素值为e，下节点引用为succ final Node<E> newNode = new Node<>(pred, e, succ); //将原index处的节点的前节点引用设置为当前添加的元素 succ.prev = newNode; if (pred == null) //如果原index处的节点的prev值为空，则将当前元素设置为首节点 first = newNode; else //否则将原index处的节点的next设置为当前添加的节点 pred.next = newNode; //数组长度增加 size++; modCount++;
  }

addAll(int index, Collection<? extends E> c)：将一个集合添加到集合的指定位置

 public boolean addAll(int index, Collection<? extends E> c) {
 //判断index的值是否超出集合的长度 checkPositionIndex(index); //将集合元素转换为数组 Object[] a = c.toArray(); int numNew = a.length; //如果数组长度为0直接返回失败 if (numNew == 0) return false; //创建两个节点，一个是index位置节点的前节点，一个是index位置的节点 Node<E> pred, succ; //如果index==集合长度，说明是添加到最末尾，将集合前节点设置为最后一个节点 if (index == size) { succ = null; pred = last; } else { //否则取出当前index位置的节点和index位置节点的前节点 succ = node(index); pred = succ.prev; } //循环遍历要添加的元素数组，将元素依次添加到prve的后面
  for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null)//判断原index位置的节点是不是首节点 //如果是，就将首节点设置成新的节点 first = newNode; else //否则将原index节点的前节点的后节点设置为当前的节点 pred.next = newNode; pred = newNode; } //判断原集合是否为空，如果是空直接把pred设置成尾节点 if (succ == null) { last = pred; } else { //否则把pred添加到succ的前面 pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; }

addAll(Collection<? extends E> c)：将一个集合添加到该集合中

 //内部调用的还是addAll(int index,Collecction<? extends E> c)方法
  //将index值设置为当前集合的最后一个元素
 public boolean addAll(Collection<? extends E> c) { return addAll(size, c);
 }

remove

removeFirst()：删除集合的首节点

 //元素进入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; //保存要删除节点的item值 final E element = f.item; //新建一个next等于当前要删除节点的next final Node<E> next = f.next; //把首节点的item值和next值设置为null f.item = null; f.next = null; // help GC //把首节点设置为原首节点的next节点 first = next; //如果next==null,则把last节点也设置为空 if (next == null) last = null; else //否则把原来第二个节点的前节点设置为null，表示原来的第二个节点变为首节点 next.prev = null; //集合长度自减1 size--; modCount++; //返回原集合的首节点的值 return element; }

removeLast()：删除集合的尾节点

   //当元素进入removeLast方法 public E removeLast() { //声明常量保存要删除的节点 final Node<E> l = last; if (l == null) //如果节点为空，抛出异常 throw new NoSuchElementException(); //否则进入删除最后一个节点的方法 return unlinkLast(l); } private E unlinkLast(Node<E> l) { //保存节点中的元素值 final E element = l.item; //保存节点的前一个节点 final Node<E> prev = l.prev; //将节点的item和prev设置为null l.item = null; l.prev = null; // help GC //把尾节点设置为当前删除节点的前一个节点 last = prev; //如果前节点为空，则把首节点也设置为空 if (prev == null) first = null; else //把原节点的前一个节点的next设置为null，标志为最后一个节点 prev.next = null; //集合长度自减 size--; modCount++; //返回原节点的值 return element;
  }

remove(Object o)：删除指定元素


 public boolean remove(Object o) {
 //判断元素是否为空 if (o == null) { //如果为空，遍历找出第一个item为空的节点 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { //进入删除方法 unlink(x); return true; } } } else { //如果不为空，匹配第一个item等于o的节点 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) { // 取出删除节点的item、next、prev final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; //如果原节点的前节点为空，说明是首节点 if (prev == null) { //把原节点的下一个节点设置为首节点 first = next; } else { //否则把原节点的上一个节点的next设置为原节点的next prev.next = next; //把原节点的prev设置为空 x.prev = null; } //如果原节点的后节点为空，说明是尾节点 if (next == null) { //把原节点的上一个节点设置为尾节点 last = prev; } else { //否则把原节点的下一个节点的prev设置为原节点的prev，把原节点的next设置为空 next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element;
  }

remove(int index)

  //元素进入该方法，首先判断index是否超过了集合的长度，如果超过就抛出异常
  //实际与remove(Object o)方法一样，只是先调用了node方法，通过index取到节点
  //再调用unlink接触链式绑定，删除节点
  public E remove(int index) { checkElementIndex(index); return unlink(node(index));
  } E unlink(Node<E> x) { 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;
  }

set(int index, E element)：用指定的元素替换列表中指定位置的元素

   public E set(int index, E element) { //元素进入set方法，首先判断index的值是否超出了集合的长度，如果超出了就抛出异常 checkElementIndex(index); //调用node方法，获取要替换的元素 Node<E> x = node(index); //取出要替换的元素 E oldVal = x.item; //替换为新的元素 x.item = element; //返回指定位置要替换的旧的元素 return oldVal; }

get
getFirst()：获取集合的第一个元素

  public E getFirst() { //获取集合的第一个节点 final Node<E> f = first; //如果为空，抛出异常 if (f == null) throw new NoSuchElementException(); //否则返回节点中的item值 return f.item;
  }

getLast()：获取集合中的最后一个元素

  public E getLast() { //获取集合的最后一个节点 final Node<E> l = last; //如果节点为空，抛出异常 if (l == null) throw new NoSuchElementException(); //否则返回节点的item值 return l.item;
  }

get(int index):根据索引值获取元素

  public E get(int index) {
  //判断index是否超出了集合的长度，如果超出则抛出异常 checkElementIndex(index); //否则调用node方法返回指定位置节点的item值 return node(index).item;
  }

indexOf(Object o)：判断元素是否存在，存在则返回索引值，不存在返回-1

 public int indexOf(Object o) { int index = 0; //判断o是否为空 if (o == null) { //如果为空，遍历匹配第一个为空的值 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; //匹配到了，返回节点位置 index++; } } else { //如果不为空，遍历匹配第一个值与o相同的值 for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) //匹配到了，返回节点位置 return index; index++; } } //如果没有匹配到，返回-1 return -1; }

遍历集合

使用普通循环

  List<String> list=new LinkedList<String>(); list.add("123"); list.add("12345"); list.add("123"); list.add("12345"); //手写for循环 for (int i=0;i<list.size();i++){ //调用LinkedList的get(int index)方法 list.get(i); }

 //get方法的内部还是使用node方法循环遍历取到元素的 public E get(int index) { checkElementIndex(index); return node(index).item; } //使用node方法遍历，是通过next或者prev获取到前后的节点引用 //假设需要循环取到index=3和index=4的值 //那么第一轮循环要遍历0-3的值，第二轮循环还要遍历0-4的值 //虽然有把集合一分为二，但是假设数据量多的时侯，循环遍历的时间还是不短的 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; } }

使用迭代器

 List<String> list=new LinkedList<String>(); list.add("123"); list.add("12345"); list.add("123"); list.add("12345"); //使用迭代器进行循环 //调用listIterator()方法初始化一个迭代器 Iterator<String> l=list.listIterator(); //遍历循环 while (l.hasNext()){ System.out.println(l.next()); }

 private class ListItr implements ListIterator<E> { //表示最后一次访问过的对象 private Node<E> lastReturned; //表示下一次调用next方法时返回的元素 private Node<E> next; //表示下一次调用niex()方法时返回的元素的下标 private int nextIndex; //expectedModCount是ListItr持有的修改次数，modCount是LinkedList持有的修改次数 //为了防止多线程下同时修改集合的元素 private int expectedModCount = modCount; //初始化迭代器，如果参数为空表示从0开始循环 //通过node(index)方法将下一次调用next()方法时要返回的节点以及节点下标存储在next变量内 ListItr(int index) { //如果index已经等于集合的长度，则返回null next = (index == size) ? null : node(index); nextIndex = index; } //用于循环时判断是否还有下一个节点 public boolean hasNext() { return nextIndex < size; } public E next() { //判断内外两个修改次数是否一致，不一致则抛出异常 checkForComodification(); //判断是否还有下一个节点，如果没有也抛出异常 if (!hasNext()) throw new NoSuchElementException(); //迭代器循环遍历时不需要每次从头开始的关键代码在此 //每次在调用next()方法的时候，已经将下一次调用时需要返回的值记录下来了 //所以在循环取下一个值的时候不需要再从第一个节点next到需要的节点，而是直接返回记录下来的next节点 //将最后一次访问的元素存储到lastReturned变量中 lastReturned = next; //设置下一次访问时要返回的元素 next = next.next; //下标自增 nextIndex++; //返回当前的节点值 return lastReturned.item; } }

文章来源: blog.csdn.net，作者：Judy-zqj，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_43988801/article/details/114694721

（完）