你的位置:首页 > Java教程

[Java教程]基于JDK1.8的LinkedList源码学习笔记


        LinkedList作为一种常用的List,是除了ArrayList之外最有用的List。其同样实现了List接口,但是除此之外它同样实现了Deque接口,而Deque是一个双端队列接口,其继承自Queue,所以LinkedList同样可以用来模拟队列,栈以及双端队列。

图片1

一.基本用法

      因为LinkedList是基于链表实现的,所以注定其插入和删除操作速度要快于ArrayList,但是由于其是链表结构,所以其随机访问查找检索速度慢于基于数组的ArrayList。

         这里先主要说一下LinkedList的基本用法,以及模拟队列,模拟栈,模拟双端队列的常用方法。

1.LinkedList,List用法

List<String> myList=new LinkedList<String>();(1)//增加元素String s="myString"myList.add(s);//这里等同于在链表尾端增加元素addLast(e)myList.add(1,s);//在指定位置插入元素(2)//获取指定位置的元素String getString=myList.get(10)//获取链表第11处元素,从头计算(3)//删除元素myList.remove(2)//删除链表第3个元素(4)//clear清空链表myList.clear()(5)isEmpty(),//判断list是否为空

2.LinkedList模拟队列

Queue<String> myQueue=new LinkedList<String>();(1)//添加元素到到队尾  myQueue.offer(myString);  myQueue.add(myString);(2)检索但不删除队首元素  String head=myQueue.peek();//若为空,返回null  String head=myQueue.element();//若队列为空,抛出NoSuchElementException(3)取出并且删除队首元素  String head=myQueue.poll(); //若为空,返回null  String head=myQueue.remove();//若队列为空,抛出NoSuchElementException//综上,LinkedList通过在链表尾插入元素,链表首取出元素,模拟了先进先出FIFO的队列,但是//这里的队列是单向的

3.LinkedList模拟栈Stack操作

Deque<String> stack=new LinkedList<String>();//(1)进栈操作    stack.push(myString);//(2)出栈操作,删除并且取出  stack.pop();//(3)若是检索不删除则还用peek  stack.peek();//LinkedList通过在队首插入元素,队首取出元素,模拟stack的先进后出操作

4.LinkedList模拟双端队列Deque操作

Deque<String> deque=new LinkedList<String>();//(1)队首添加元素 deque.offerFirst(myString); deque.addFirst(myString);//(2)队尾添加元素 deque.offerLast(myString); deque.addLast(myString);//(3)检索但不删除队首元素  String first=deque.peekFirst();  first=deque.getFirst();//(4)检索但不删除队尾元素  String last=deque.peekLast();  last=deque.getLast();//(5)取出并删除队首元素  deque.pollFirst();  deque.removeFirst();//(6)取出并删除队尾元素  deque.pollLast();  deque.removeLast();//这样LinkedList通过操作链表队首队尾就实现了双端队列

5.LinkedList迭代遍历

//(1)for each 循环List<String> list=new ArrayList<String>();for(String s:list){////}//(2)iterator迭代器Iterator<String> it=list.iterator();while(it.hasNext()){  it.next();}//(3)同时List还提供了ListIterator接口,拥有反向正向迭代ListIterator<String> lit=list.listIterator();while(lit.hasNext()){  it.next();}//正向迭代while(it.hasPrevious()){  it.previous();}//反向迭代//值得注意的是,以前可能忽视了,listIterator迭代器同时提供了增删改的功能//add(),在指定位置插入一个元素,当前迭代的前面插入//set(E,e),修改当前迭代为指定元素//remove();删除上一次迭代

二.JDK源码分析

   这里的JDK是基于JDK1.8的源码。

1.定义,LinkedList类定义

public class LinkedList<E>  extends AbstractSequentialList<E>  implements List<E>, Deque<E>, Cloneable, java.io.Serializable // 继承了AbstractSequentialList抽象类,提供了实现List接口的基本实现 //Deque接口, A linear collection that supports element insertion and removal at both ends.  //The name <i>deque</i> is short for "double ended queue" and is usually pronounced "deck"public interface Deque<E> extends Queue<E>//所以这里就可以知道为什么LinkedList可以模拟队列,双端队列,以及Stack栈了

2.重要属性

transient int size = 0;//记录List大小//接下来分别是两个Node引用,分别指向链表头和链表尾transient Node<E> first;transient Node<E> last;//接下就是链表中节点的定义,可以看到JDK1.8把节点都统一为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;    }  }//及其简单的定义,双向链表,向前链接,向后向后链接,元素

3.构造器

//(1)无参构造器 public LinkedList() {  } //(2)带有集合的构造器 public LinkedList(Collection<? extends E> c) {    this();    addAll(c);  }//调用addAll将现有集合内所有元素放到LinkedList中 public boolean addAll(Collection<? extends E> c) {    return addAll(size, c);  } //将整个集合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则为原来在index位置的节点      succ = node(index);      pred = succ.prev;    }    for (Object o : a) {      @SuppressWarnings("unchecked") E e = (E) o;      //创建新的Node节点,其中newNode的前向节点为pred,后向节点没有定义      Node<E> newNode = new Node<>(pred, e, null);      //pred==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;  }

4.常用方法源码分析

(1). add(E e)

//默认add方法,将节点放入链表尾部,同offer方法 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++;  }

//将元素链接放到指定位置public void add(int index, E element) {     //该方法主要是查看index是否合法,在范围内,否则抛出异常    checkPositionIndex(index);    //当index是末尾时,直接链接到结尾    if (index == size)      linkLast(element);    else      //否则找到index位置的原来节点,插入到其前面      linkBefore(element, node(index));  }  //取出index位置的node节点  Node<E> node(int index) {    // assert isElementIndex(index);    //这里有一处非常值得注意    //size>>1表示的是向右移位1,该方法其实相当于除以2,去得一半的值    //当index<size/2时,表明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;    }  }//linkBefore 方法  //这个方法是将节点插入到succ节点的前面,//由于是在指定位置插入节点,所以要将原来的节点链接到新节点后面  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节点定义为当前节点      pred.next = newNode;    size++;    modCount++;  }

  (2).addLast(),addFirst()方法

addLast()等同于add()方法,addFirst是在链表头插入节点

//将新节点放入到链表尾部 public void addLast(E e) {    linkLast(e);  }//在链表头插入节点  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++;  }

(3). getFirst(),getLast()获取头节点和尾节点

/**   * Returns the first element in this list.   *   * @return the first element in this list   * @throws NoSuchElementException if this list is empty为空会抛出异常   */  public E getFirst() {    final Node<E> f = first;    if (f == null)      throw new NoSuchElementException();    return f.item;  }  /**   * Returns the last element in this list.   *   * @return the last element in this list   * @throws NoSuchElementException if this list is empty   */  public E getLast() {    final Node<E> l = last;    if (l == null)      throw new NoSuchElementException();    return l.item;  }

     (4). removeFirst(),removeLast()方法

/**   * Removes and returns the first element from this list.   *   * @return the first element from this list   * @throws NoSuchElementException if this list is empty   */
public E removeFirst() {    final Node<E> f = first;    if (f == null)      throw new NoSuchElementException();    return unlinkFirst(f);  }//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;    if (next == null)      last = null;//此时链表为空    else      next.prev = null;    size--;    modCount++;    return element;  }

/**   * Removes and returns the last element from this list.   *   * @return the last element from this list   * @throws NoSuchElementException if this list is empty   */  public E removeLast() {    final Node<E> l = last;    if (l == null)      throw new NoSuchElementException();    return unlinkLast(l);  }  /**   * Unlinks non-null last node 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;  }

(5). contains(Object o)
    查看链表中是否存有某个元素

public boolean contains(Object o) {    return indexOf(o) != -1;  }  //indexOf()这个方法返回对象O在链表中的位置  public int indexOf(Object o) {    int index = 0;    if (o == null) {      for (Node<E> x = first; x != null; x = x.next) {        if (x.item == null)          return index;        index++;      }    } else {      //同样调用的也是equals方法判断两个值是否相等      for (Node<E> x = first; x != null; x = x.next) {        if (o.equals(x.item))          return index;        index++;      }    }    return -1;//没有找到时返回-1  }

(6). get(int index)

获取指定index位置的元素

/**   * Returns the element at the specified position in this list.   *   * @param index index of the element to return   * @return the element at the specified position in this list   * @throws IndexOutOfBoundsException {@inheritDoc}   */  public E get(int index) {    checkElementIndex(index);    return node(index).item;  }

  (7).set(int index,E element)

set修改指定位置的元素

//主要还是定位获取节点之后再修改  public E set(int index, E element) {    checkElementIndex(index);    Node<E> x = node(index);    E oldVal = x.item;    x.item = element;    return oldVal;  }

(8).搜索元素所在位置indexOf(Object o),lastIndexOf(Object o)

分为正向indexOf(),即第1次插入时匹配的元素位置和反向lastIndexOf(),即最后一次插入匹配的位置

//indexOf()这个方法返回对象O在链表中的位置  public int indexOf(Object o) {    int index = 0;    if (o == null) {      for (Node<E> x = first; x != null; x = x.next) {        if (x.item == null)          return index;        index++;      }    } else {      //同样调用的也是equals方法判断两个值是否相等      for (Node<E> x = first; x != null; x = x.next) {        if (o.equals(x.item))          return index;        index++;      }    }    return -1;  }  //反向查找  //有index的时候,必然会有lastIndexOf  public int lastIndexOf(Object o) {    int index = size;    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先--,因为你是从size位置开始的,所以要先--        index--;        if (o.equals(x.item))          return index;      }    }    return -1;  }

5.模拟Queue操作源码分析

再次强调一次这里queue先进先出,在队尾入队,队首出队

(1).首先是检索队首,但不出队的操作,peek(),element()

/**   * Retrieves, but does not remove, the head (first element) of this list.   *   * @return the head of this list, or {@code null} if this list is empty   * @since 1.5   */最常用操作,peek(),若为空会,返回null  public E peek() {    final Node<E> f = first;    return (f == null) ? null : f.item;  }  /**   * Retrieves, but does not remove, the head (first element) of this list.   *   * @return the head of this list   * @throws NoSuchElementException if this list is empty   * @since 1.5   *///若为空会抛出异常  public E element() {    return getFirst();  }//再回头看一眼getFirst(),  public E getFirst() {    final Node<E> f = first;    if (f == null)      throw new NoSuchElementException();//抛出异常    return f.item;  }

(2).出队操作,取出队首元素,poll(),remove()

/**   * Retrieves and removes the head (first element) of this list.   *   * @return the head of this list, or {@code null} if this list is empty   * @since 1.5   */  public E poll() {    final Node<E> f = first;    return (f == null) ? null : unlinkFirst(f);  }  /**   * Retrieves and removes the head (first element) of this list.   *   * @return the head of this list   * @throws NoSuchElementException if this list is empty   * @since 1.5   */  public E remove() {    return removeFirst();  }  public E removeFirst() {    final Node<E> f = first;    if (f == null)      throw new NoSuchElementException();    return unlinkFirst(f);  }

(3).队尾插入元素offer()

/**   * Adds the specified element as the tail (last element) of this list.   *   * @param e the element to add   * @return {@code true} (as specified by {@link Queue#offer})   * @since 1.5   */  public boolean offer(E e) {    return add(e);  }

6. 模拟双端队列Deque操作源码分析

双端队列,其实就是整条链表头尾都操作,有了前面的基础,这里应该非常简单了

(1).在队首,队尾插入元素,offerFirst(),offerLast()

其实就是分别调用addFirst(E e)和addLast(E e)方法

/**   * Inserts the specified element at the front of this list.   *   * @param e the element to insert   * @return {@code true} (as specified by {@link Deque#offerFirst})   * @since 1.6   */  public boolean offerFirst(E e) {    addFirst(e);    return true;  }  /**   * Inserts the specified element at the end of this list.   *   * @param e the element to insert   * @return {@code true} (as specified by {@link Deque#offerLast})   * @since 1.6   */  public boolean offerLast(E e) {    addLast(e);    return true;  }

(2).检索队首,队尾元素,但不出队peekFirst(),peekLast()

/**   * Retrieves, but does not remove, the first element of this list,   * or returns {@code null} if this list is empty.   *   * @return the first element of this list, or {@code null}   *     if this list is empty   * @since 1.6   */  public E peekFirst() {    final Node<E> f = first;    return (f == null) ? null : f.item;   }  /**   * Retrieves, but does not remove, the last element of this list,   * or returns {@code null} if this list is empty.   *   * @return the last element of this list, or {@code null}   *     if this list is empty   * @since 1.6   */  public E peekLast() {    final Node<E> l = last;    return (l == null) ? null : l.item;  }

(3). 出队操作,取出队首,队尾元素,pollFirst(),pollLast()

/**   * Retrieves and removes the first element of this list,   * or returns {@code null} if this list is empty.   *   * @return the first element of this list, or {@code null} if   *   this list is empty   * @since 1.6   */  public E pollFirst() {    final Node<E> f = first;    return (f == null) ? null : unlinkFirst(f);  }  /**   * Retrieves and removes the last element of this list,   * or returns {@code null} if this list is empty.   *   * @return the last element of this list, or {@code null} if   *   this list is empty   * @since 1.6   */  public E pollLast() {    final Node<E> l = last;    return (l == null) ? null : unlinkLast(l);  }

7. 模拟栈Stack操作源码分析

值得注意的是Stack操作一直是对链表头进行操作,不管是进栈push还是出栈pop方法

/**   * Pushes an element onto the stack represented by this list. In other   * words, inserts the element at the front of this list.   *   * <p>This method is equivalent to {@link #addFirst}.   *   * @param e the element to push   * @since 1.6   */  public void push(E e) {    addFirst(e);  }  /**出栈操作,若栈为空会抛出异常   * Pops an element from the stack represented by this list. In other   * words, removes and returns the first element of this list.   *   * <p>This method is equivalent to {@link #removeFirst()}.   *   * @return the element at the front of this list (which is the top   *     of the stack represented by this list)   * @throws NoSuchElementException if this list is empty   * @since 1.6   */  public E pop() {    return removeFirst();  }

8. 最后再看一下LinkedList的迭代器ListIterator

listIterator()方法,返回ListIterator迭代器 ,这个不带参数listIterator方法是 AbstractlList中的方法

public ListIterator<E> listIterator() {    return listIterator(0);  } //从第几个链表节点开始迭代 public ListIterator<E> listIterator(int index) {    checkPositionIndex(index);    return new ListItr(index);  } //ListItr是其中的一个内部类,该类是一个List迭代器 private class ListItr implements ListIterator<E> {    private Node<E> lastReturned;//永远记录上一次迭代的节点    private Node<E> next;    private int nextIndex;    //这个变量非常重要,能够查看迭代过程中是否修改了List,使得迭代过程中的数据与原List中的数据一致    //Fail_fast原理,不一致时立马失败抛出异常    private int expectedModCount = modCount;    //这里给出index,则可以看成是从哪个节点开始迭代    ListItr(int index) {      // assert isPositionIndex(index);      next = (index == size) ? null : node(index);      nextIndex = index;    }    //正向迭代,向后迭代    public boolean hasNext() {      return nextIndex < size;    }    public E next() {      //每次迭代前都检查一下,是否修改了原List,若原List自行修改,而没有经过ListItr迭代器修改则将抛出异常      //Fail-Fast      checkForComodification();      if (!hasNext())        throw new NoSuchElementException();      lastReturned = next;      next = next.next;      nextIndex++;      return lastReturned.item;    }    //反向迭代,即向前迭代    public boolean hasPrevious() {      return nextIndex > 0;    }    public E previous() {      checkForComodification();      if (!hasPrevious())        throw new NoSuchElementException();      lastReturned = next = (next == null) ? last : next.prev;      nextIndex--;      return lastReturned.item;    }    //返回下标    public int nextIndex() {      return nextIndex;    }    public int previousIndex() {      return nextIndex - 1;    }    //迭代操作时,唯一的增删改方式,值得注意的是这里的修改操作都是针对上一次的迭代    //也就是调用next()得到元素,若要对这个变量进行修改,则可以进行修改    //这种设计也十分合理,我只有得到元素我才知道我要对元素做什么        public void remove() {      //当迭代过程中要想删除元素,一定要用迭代器的remove方法      checkForComodification();      if (lastReturned == null)        throw new IllegalStateException();      Node<E> lastNext = lastReturned.next;      unlink(lastReturned);      if (next == lastReturned)        next = lastNext;      else        nextIndex--;      lastReturned = null;      //由于上面调用unlink时,modCount++;      //所以为了下一次迭代不抛出异常,这里也要进行 expectedModCount++      expectedModCount++;    }    public void set(E e) {      if (lastReturned == null)        throw new IllegalStateException();      checkForComodification();      lastReturned.item = e;    }    //增也是增在next()后的元素之后    public void add(E e) {      checkForComodification();      lastReturned = null;      if (next == null)        linkLast(e);      else        linkBefore(e, next);      nextIndex++;      expectedModCount++;    }    public void forEachRemaining(Consumer<? super E> action) {      Objects.requireNonNull(action);      while (modCount == expectedModCount && nextIndex < size) {        action.accept(next.item);        lastReturned = next;        next = next.next;        nextIndex++;      }      checkForComodification();    }    //// 判断expectedModCount和modCount是否一致,以确保通过ListItr的修改操作正确的反映在LinkedList中    final void checkForComodification() {      if (modCount != expectedModCount)        throw new ConcurrentModificationException();    }  }

三.简单总结

       LinkedList是十分常用的类,而且其方法实在太多了,而且其功能还狠多,之前老是记不住,这次掰开揉碎过一遍JDK源码,发现实现其实非常简单,但是里面有很多小技巧是值得学习的。所以阅读源码应该成为我今后学习的一个好习惯,任何框架任何技术,知其所以然才能融汇贯通。