基于JDK1.8的LinkedList源码学习笔记

2019-11-14 15:19:52

字体：大中小

来源：转载

供稿：网友

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

一.基本用法

因为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();        }    }