澳门新葡萄京官网注册 15

澳门新葡萄京官网注册LinkedList源码分析(基于Java8)

简介

LinkedList 是一个常用的集合类,用于顺序存储元素。 LinkedList 经常和
ArrayList 一起被提及。大部分人应该都知道 ArrayList
内部采用数组保存元素,适合用于随机访问比较多的场景,而随机插入、删除等操作因为要移动元素而比较慢。
LinkedList
内部采用链表的形式存储元素,随机访问比较慢,但是插入、删除元素比较快,一般认为时间复杂都是
O(1) (需要查找元素时就不是了,下面会说明)。本文分析 LinkedList
的具体实现。

澳门新葡萄京官网注册 1

LinkedList特点总结

  • LinkedList实现List接口,使用双向链表实现,元素可以是null
  • 可以被当作堆栈,队列,双端队列使用
  • 因其使用链表实现,查询需要遍历O(n)时间复杂度,插入时不再需要复制移动元素O(1)时间复杂度
  • 类中的iterator()方法和listIterator()方法返回的iterators迭代器是fail-fast的:当某一个线程A通过iterator去遍历某集合的过程中,若该集合的内容被其他线程所改变了;那么线程A访问集合时,就会抛出ConcurrentModificationException异常,产生fail-fast事件
  • 和ArrayList一样,不是线程安全的,可以使用Collections.synchronizedList()变成支持并发的容器


LinkedList是由一个双向链表来维护的,对于增删改查元素理解最清晰地理解就是画一张图

继承关系

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 继承了一个抽象类 AbstractSequentialList ,这个类就是用调用
ListIterator 实现了元素的增删查改,比如 add 方法:

public void add(int index, E element) {
    try {
        listIterator(index).add(element);
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

不过这些方法在 LinkedList 中被复写了。

LinkedList 实现了 List 、 Deque 、 Cloneable 以及 Serializable
接口。其中 Deque 是双端队列接口,所以 LinkedList
可以当作是栈、队列或者双端队队列。

  • LinkedList是一个实现了List接口和Deque接口的双端链表
  • 有关索引的操作可能从链表头开始遍历到链表尾部,也可能从尾部遍历到链表头部,这取决于看索引更靠近哪一端。
  • LinkedList不是线程安全的,如果想使LinkedList变成线程安全的,可以使用如下方式:

源码分析

考虑到之前是直接拷贝jdk源码在源码上通过注释的方式进行解读,这样看起来会比较杂乱,所以这次采用分块解读的方式

  1. 节点类

因为采用链表的方式实现,所以需要先定义一个结点类,源码中使用静态内部类的方式定义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;
        }
    }

可以看到定义的是一个双向链表的Node类,next指向其下一个Node,prev指向其上一个Node

  1. LinkedList的成员变量

    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

size是当前List中的元素个数,first和last都是Node类型的变量,分别指向链表的第一个节点和最后一个节点,这三个变量都是transient,说明不希望进行序列化

  1. 构造方法

    public LinkedList() {
    }

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

第一个构造方法创建了一个空的LinkedList,第二个构造方法是通过一个Collection接口的实现类对象进行初始化,首先调用第一个构造方法创建一个空的LinkedList然后将参数指向的Collection中的元素添加到LinkedList中,元素的顺序是Collection的iterator返回的顺序

  1. 增加元素

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;
    }

首先看add方法,add方法中调用了linkLast方法,可以看出来是在list的末尾添上一个Node,这个方法与源码中的addLast方法效果是相同的,只是add方法是有返回的,凡是返回比较鸡肋

   public void addLast(E e) {
        linkLast(e);
    }

顺藤摸瓜,我们来看一个linkLast方法

   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++;
    }
  • 首先通过last指针找到list的最后一个node,然后创建一个新的node,这个newNode的next指向null,prev指向链表的最后一个节点
  • 将链表的last指向创建的newNode
  • 判断之前找到的last node
    如果该node是null说明原来list中没有元素,将创建的newNode赋值给first表示新node是最后一个元素也是第一个元素,如果l不是null,表示原来的list中有元素,此时将l的next指向newNode
  • 最后需要将size++ 表示list元素多了一个

除了在list的尾巴上添加元素,jdk源码中还提供了在链表头上添加元素的方法

   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++;
   }

addFirst会直接调用linkFirst完成插入操作,和上面linkLast方法其实是相仿的

  • 首先找到first指向的元素,有可能是一个null
  • 创建一个新的node,其prev指向null,因为newNode是链表的第一个元素
  • first指向newNode
  • 如果f指向null,表示链表原先是没有元素的,那么newNode就是当前唯一的元素,last也要指向newNode,如果f不是null,表示原先链表中就有元素,需要将f指向的(此时是链表的第二个元素)的prev指向newNode

LinkedList同时也提供了指定index插入元素

    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;
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
  • 首先进行index的检查,保证index在[0,size]之间,如果是非法的index就抛出一个异常
  • 如果index==size 就是在链表的最后进行添加
  • 否则调用linkBefore方法,完成元素添加

   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;
       }
   }

node(int
index)这个方法返回在链表index位置上的node,返回的node是一个不为null的node,//
assert isElementIndex(index);
被注释掉是因为前面已经进行index == size
判断就不再这边进行判断了,此外需要注意的是这边使用了一个小技巧

  • 如果index属于链表的前面一半 index < (size >> 1)
    就从first指向的元素进行遍历
  • 如果index属于链表的后面一半元素 就从last指向的元素进行遍历
  • 返回node

    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++;
    }

linkBefore方法是最终完成插入操作的方法,同样succ!=null也被注释掉了,因为上面node方法返回的是一个不为null的node,linkBefore其实是一个双向链表的插入操作

  • 首先找到succ这个node prev指针指向的node,即succ左手边的一个node
  • 创建一个新的node,这个newNode prev指向pred,next指向succ
  • 因为jdk中在add(index,e)中仅对index==size的情况做了特殊处理,并没有对index==0的时候做出特殊处理,即在第一个位置进行插入,此时pred会是null,当pred
    == null时表示index ==
    0在第一个位置进行插入了,pred右手边指针需要指向newNode,其他情况下pred.next指向newNode即可
  1. 访问元素

LinkedList提供了getFirst()、getLast()、contains(Object o)、get(int
index)、indexOf(Object o)、lastIndexOf(Object o)这些查找元素的方法

    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;
    }

首先进行index检查,然后通过node(index)获取index下的元素,最后通过node.item获取到值,需要注意index检查的时候与add
index检查的方法存在一点点细微的区别:index >= 0 && index <
size;
这里index必须在[0,size-1]

jdk还提供了一些取特殊位置元素的方法

    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
  1. 删除元素

LinkedList提供了头删除removeFirst()、尾删除removeLast()、remove(int
index)、remove(Object o)、clear()这些删除元素的方法

    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

首先index检查与上面get中的方式相同,然后调用找到index指向的元素,调用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 {
            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;
    }

因为node(index)方法返回一个非null的node,所以这边把 x !=
null
注释掉了,unlink是一个双向链表删除的操作

  • 首先获取x的值,值作为最后的返回
  • 分别获取x next和prev指向的元素
  • 如果prev==null 表示要删除的是第一个元素,同样,如果next ==
    null表示要删除的是最后一个元素
  • 如果prev==null
    将first指向链表的第二个元素即next指向的元素,否则prev.next =
    next;x.prev = null;
  • 如果next==null 表示要删除的是最后一个元素,last =
    prev;表示将x前面的一个元素作为链表的最后一个元素,否则 next.prev =
    prev;x.next = null;
  • 最后x.item = null size– modCount++
    最好的方式还是画一张图帮助理解

同样的,jdk也提供了一些在特殊位置删除元素的方法

    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);
    }
        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;
    }

    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;
    }

不详细展开了,需要注意的是比如删除第一个节点的时候需要注意链表只有一个元素的情况

  1. 修改元素的值

    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

需要注意最后返回原先的值

  1. 其他常见操作

    public int size() {
        return size;
    }

返回当前链表中元素的个数

   public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    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 {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

    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--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

返回元素o在链表中的index,准确说应该是第一个o的index,与ArrayList中处理的方式是一样的,遍历的时候对null和non-null做了判断

  1. Queue操作

Queue操作提供了peek()、element()、poll()、remove()、offer(E e)这些方法

    //获取但不移除此队列的头;如果此队列为空,则返回 null
    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

    //获取但不移除此队列的头;如果此队列为空,则抛出NoSuchElementException异常
    public E element() {
        return getFirst();
    }

    //获取并移除此队列的头,如果此队列为空,则返回 null
    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    //获取并移除此队列的头,如果此队列为空,则抛出NoSuchElementException异常
    public E remove() {
        return removeFirst();
    }

    //将指定的元素值(E e)插入此列表末尾
    public boolean offer(E e) {
        return add(e);
    }

Deque操作提供了offerFirst(E e)、offerLast(E
e)、peekFirst()、peekLast()、pollFirst()、pollLast()、push(E
e)、pop()、removeFirstOccurrence(Object o)、removeLastOccurrence(Object
o)这些方法

 //获取但不移除此队列的头;如果此队列为空,则返回 null
    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

    //获取但不移除此队列的头;如果此队列为空,则抛出NoSuchElementException异常
    public E element() {
        return getFirst();
    }

    //获取并移除此队列的头,如果此队列为空,则返回 null
    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    //获取并移除此队列的头,如果此队列为空,则抛出NoSuchElementException异常
    public E remove() {
        return removeFirst();
    }

    //将指定的元素值(E e)插入此列表末尾
    public boolean offer(E e) {
        return add(e);
    }

    // Deque operations

    //将指定的元素插入此双端队列的开头
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

    //将指定的元素插入此双端队列的末尾
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

    //获取,但不移除此双端队列的第一个元素;如果此双端队列为空,则返回 null
    public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

    //获取,但不移除此双端队列的最后一个元素;如果此双端队列为空,则返回 null
    public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }

    //获取并移除此双端队列的第一个元素;如果此双端队列为空,则返回 null
    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    //获取并移除此双端队列的最后一个元素;如果此双端队列为空,则返回 null
    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

    //将一个元素推入此双端队列所表示的堆栈(换句话说,此双端队列的头部)
    public void push(E e) {
        addFirst(e);
    }

    //从此双端队列所表示的堆栈中弹出一个元素(换句话说,移除并返回此双端队列的头部)
    public E pop() {
        return removeFirst();
    }

    //从此双端队列移除第一次出现的指定元素,如果列表中不包含次元素,则没有任何改变
    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

    //从此双端队列移除最后一次出现的指定元素,如果列表中不包含次元素,则没有任何改变
    public boolean removeLastOccurrence(Object o) {
        //由于LinkedList中允许存放null,因此下面通过两种情况来分别处理
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) { //逆向向前
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
  1. 遍历方式
  • 使用迭代器iterator遍历

Iterator iter = list.iterator();
   while (iter.hasNext())
   {
       System.out.println(iter.next());
   }    
  • 使用listIterator遍历

ListIterator<String> lIter = list.listIterator();
  //顺向遍历
  while(lIter.hasNext()){
      System.out.println(lIter.next());
  }
  //逆向遍历
  while(lIter.hasPrevious()){
      System.out.println(lIter.previous());
  }
  • 使用foreach遍历

 for(String str:list)
    {
        System.out.println(str);
    }    

内部变量

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

总共就三个内部变量, size 是元素个数, first 是指向第一个元素的指针,
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;
    }
}

可以看到这是一个双向链表的结构,每个节点保存它的前驱节点和后继节点。

私有方法

LinkedList
内部有几个关键的私有方法,它们实现了链表的插入、删除等操作。比如在表头插入:

private void linkFirst(E e) {
    final Node<E> f = first;    //先保存当前头节点
    //创建一个新节点,节点值为e,前驱节点为空,后继节点为当前头节点
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;    //让first指向新节点
    if (f == null)    //如果链表原来为空,把last指向这个唯一的节点
        last = newNode;
    else    ·        //否则原来的头节点的前驱指向新的头节点
        f.prev = newNode;
    size++;
    modCount++;
}

其实就是双向链表的插入操作,调整指针的指向,时间复杂度为 O(1)
,学过数据结构的应该很容易看懂。其它还有几个类似的方法:

//尾部插入
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)    //如果链表原来为空,让first指向这个唯一的节点
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
//中间插入
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++;
}
//删除头节点
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;    //让first指向下一个节点
    if (next == null)    //如果下一个节点为空,说明链表原来只有一个节点,现在成空链表了,要把last指向null
        last = null;
    else        //否则下一个节点的前驱节点要置为null
        next.prev = null;
    size--;
    modCount++;
    return element;
}
//删除尾节点
 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;    //last指向前一个节点
    if (prev == null)    //与头节点删除一样,判断是否为空
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}
//从链表中间删除节点
 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要指向下一个节点
        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;
}
List list=Collections.synchronizedList(new LinkedList(...));

公开方法

公开的方法几乎都是调用上面几个方法实现的,例如 add 方法:

public boolean add(E e) {
    linkLast(e);
    return true;
}
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));
}

这些方法的实现都很简单。注意最后一个方法 add(int index, E element)
,这个方法是在指定的位置插入元素。首先判断位置是否越界,然后判断是不是最后一个位置。如果是就直接插入链表末尾,否则调用
linkBefore(element, node(index) 方法。这里在传参数的时候又调用了
node(index) ,这个方法的目的是找到这个位置的节点对象,代码如下:

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;
    }
}

这里有个小技巧是先判断位置是在链表的前半段还是后半段,然后决定从链表的头还是尾去寻找节点。要注意的是
遍历链表寻找节点的时间复杂度是 O(n)
,即使做了位置的判断,最坏情况下也要遍历链表中一半的元素。所以此时插入操作的时间复杂度就不是
O(1) ,而是 O(n/2)+O(1) 。用于查找指定位置元素的 get(int index)
方法便是调用 node 实现的:

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

再看一下 remove 方法:

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

public boolean remove(Object o) {
    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;
}

第一个 remove(int index) 方法同样要调用 node(index)
寻找节点。而第二个方法 remove(Object o)
是删除指定元素,这个方法要依次遍历节点进行元素的比较,最坏情况下要比较到最后一个元素,比调用
node 方法更慢,时间复杂度为 O(n) 。另外从这个方法可以看出 LinkedList
的元素可以是 null 。

iterator()和listIterator()返回的迭代器都遵循fail-fast机制。

总结

  • LinkedList 基于双向链表实现,元素可以为 null 。
  • LinkedList
    插入、删除元素比较快,如果只要调整指针的指向那么时间复杂度是 O(1)
    ,但是如果针对特定位置需要遍历时,时间复杂度是 O(n) 。

澳门新葡萄京官网注册 2

从上图可以看出LinkedList与ArrayList的不同之处

  • ArrayList直接继承自AbstractList
  • LinkedList继承自AbstractSequentialList,然后再继承自AbstractList。另外还实现了Dequeu接口,双端队列。

内部结构

LinkedList内部是一个双端链表的结构

澳门新葡萄京官网注册 3

LinkedList的结构

从上图可以看出,LinkedList内部是一个双端链表结构,有两个变量,first指向链表头部,last指向链表尾部。

澳门新葡萄京官网注册 4

成员变量

size表示当前链表中的数据个数

下面是Node节点的定义,LinkedList的静态内部类

澳门新葡萄京官网注册 5

从Node的定义可以看出链表是一个双端链表的结构。

构造方法

LinkedList有两个构造方法,一个用于构造一个空的链表,一个用已有的集合创建链表

澳门新葡萄京官网注册 6

添加

因为LinkedList即实现了List接口,又实现了Deque,所以LinkedList既可以添加将元素添加到尾部,也可以将元素添加到指定索引位置,还可以添加添加整个集合;另外既可以在头部添加,又可以在尾部添加。

分别从List接口和Deque接口介绍。

List接口的添加

add(E e)

add(E e)用于将元素添加到链表尾部,实现如下:

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(int index,E e)

add(int index,E e)用于在指定位置添加元素

澳门新葡萄京官网注册 7

  1. 检查index的范围,否则抛出异常
  2. 如果插入位置是链表尾部,那么调用linkLast方
  3. 如果插入位置是链表中间,那么调用linkBefore

看一下linkBefore的实现
在看linkBefore之前,先看一下node(int
index)方法,该方法返回指定位置的节点

澳门新葡萄京官网注册 8

node(int index)将根据index是靠近头部还是尾部选择不同的遍历方向
一旦得到了指定索引位置的节点,再看linkBefore()

澳门新葡萄京官网注册 9

linkBefore()方法在第二个参数节点前插入一个新节点

澳门新葡萄京官网注册 10

linkBefore#第一步

澳门新葡萄京官网注册 11

linkBefore#第二步

澳门新葡萄京官网注册 12

linkBefore#第三步

linkBefore主要分三步

  1. 创建newNode节点,将newNode的后继指针指向succ,前驱指针指向pred
  2. 将succ的前驱指针指向newNode
  3. 根据pred是否为null,进行不同操作。
  • 如果pred为null,说明该节点插入在头节点之前,要重置first头节点
  • 如果pred不为null,那么直接将pred的后继指针指向newNode即可

addAll

addAll有两个重载方法

  • 一个参数的方法表示将集合元素添加到链表尾部
  • 两个参数的方法指定了开始插入的位置

//将集合插入到链表尾部,即开始索引位置为size
public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

//将集合从指定位置开始插入
public boolean addAll(int index, Collection<? extends E> c) {
        //Step 1:检查index范围
        checkPositionIndex(index);

        //Step 2:得到集合的数据
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        //Step 3:得到插入位置的前驱节点和后继节点
        Node<E> pred, succ;
        //如果插入位置为尾部,前驱节点为last,后继节点为null
        if (index == size) {
            succ = null;
            pred = last;
        }
        //否则,调用node()方法得到后继节点,再得到前驱节点
        else {
            succ = node(index);
            pred = succ.prev;
        }

        //Step 4:遍历数据将数据插入
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //创建新节点
            Node<E> newNode = new Node<>(pred, e, null);
            //如果插入位置在链表头部
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        //如果插入位置在尾部,重置last节点
        if (succ == null) {
            last = pred;
        }
        //否则,将插入的链表与先前链表连接起来
        else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }    
  1. 检查index索引范围
  2. 得到集合数据
  3. 得到插入位置的前驱和后继节点
  4. 遍历数据,将数据插入到指定位置

Deque接口的添加

addFirst(E 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;
        //如果链表为空,last节点也指向该节点
        if (f == null)
            last = newNode;
        //否则,将头节点的前驱指针指向新节点
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

在头节点插入一个节点使新节点成为新节点,但是和linkLast一样需要注意当链表为空时,对last节点的设置

addLast(E e)

将元素添加到链表尾部,与add()方法一样

public void addLast(E e) {
        linkLast(e);
}

offer(E e)

将数据添加到链表尾部,其内部调用了add(E e)方法

  public boolean offer(E e) {
        return add(e);
}

offerFirst(E e)方法

将数据插入链表头部,与addFirst的区别在于

  • 该方法可以返回特定的返回值
  • addFirst的返回值为void。

  public boolean offerFirst(E e) {
        addFirst(e);
        return true;
}

offerLast(E e)方法

offerLast()与addLast()的区别和offerFirst()和addFirst()的区别一样

添加操作总结

LinkedList由于实现了List和Deque接口,所以有多种添加方法,总结一下

  • 将数据插入到链表尾部
    • boolean add(E e):
    • void addLast(E e)
    • boolean offerLast(E e)
  • 将数据插入到链表头部
    • void addFirst(E e)
    • boolean offerFirst(E e)
  • 将数据插入到指定索引位置
    • boolean add(int index,E e)

2检索

2.1 根据位置取数据

2.1.1 get(int index)

获取任意位置的,get(int
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;
    }

1.检查index边界,index>=0&&index
2.返回指定索引位置的元素

2.1.2 获得位置为0的头节点数据

LinkedList中有多种方法可以获得头节点的数据,区别在于对链表为空时的处理,是抛异常还是返回null
主要方法有getFirst()、element()、peek()、peekFirst()
其中getFirst()和element()方法将会在链表为空时,抛出异常

   /**
     * 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;
    }

   /**
     * 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();
    }

从代码可以看到,element()方法的内部就是使用getFirst()实现的。它们会在链表为空时,抛NoSuchElementException
下面再看peek()和peekFirst()

   /**
     * 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
     */
    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

   /**
     * 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;
     }

当链表为空时,peek()和peekFirst()方法返回null

2.1.3 获得位置为size-1的尾节点数据

获得尾节点数据的方法有

  • getLast()

   /**
     * 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;
    }

getLast()在链表为空时,会抛NoSuchElementException

  • peekLast()
    只是会返回null
    peekLast()

   /**
     * 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;
    }

2.2 根据对象得到索引

  • 第一个匹配的索引
    从前往后遍历
  • 最后一个匹配的索引
    从后往前遍历

2.2.1 indexOf()

/**
     * 返回第一个匹配的索引
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for
     * @return the index of the first occurrence of the specified element in
     *         this list, or -1 if this list does not contain the element
     */
    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 {
            //从头往后遍历
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

可以看到,LinkedList可包含null,遍历方式都是从前往后,一旦匹配了,就返回索引

2.2.2 lastIndexOf()

返回最后一个匹配的索引,实现为从后往前遍历

   /**
     * Returns the index of the last occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the highest index {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for
     * @return the index of the last occurrence of the specified element in
     *         this list, or -1 if this list does not contain the element
     */
    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--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

2.3 检查是否包含某对象

contains(Object o)
检查对象o是否存在于链表中

  /**
     * Returns {@code true} if this list contains the specified element.
     * More formally, returns {@code true} if and only if this list contains
     * at least one element {@code e} such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o element whose presence in this list is to be tested
     * @return {@code true} if this list contains the specified element
     */
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

从代码可以看到contains()方法调用了indexOf()方法,只要返回结果不是-1,那就说明该对象存在于链表中

2.4 检索操作总结

检索操作分为按照位置得到对象以及按照对象得到位置两种方式,其中按照对象得到位置的方法有indexOf()和lastIndexOf();按照位置得到对象有如下方法:

  • 根据任意位置得到数据的get(int index)方法,当index越界会抛出异常
  • 获得头节点数据
  • getFirst()和element()方法在链表为空时会抛出NoSuchElementException
  • peek()和peekFirst()方法在链表为空时会返回null
  • 获得尾节点数据
  • getLast()在链表为空时会抛出NoSuchElementException
  • peekLast()在链表为空时会返回null

3删除

  • 按照位置删除
    • 返回是否删除成功的标志
    • 返回被删除的元素
  • 按照对象删除

3.1 删除指定对象

remove(Object o)
一次只删除一个匹配的对象,如果删除了匹配对象,返回true,否则false

   /**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If this list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns {@code true} if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return {@code true} if this list contained the specified element
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                //一旦匹配,调用unlink()方法和返回true
                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;
    }

由于LinkedList可以存储null,所以对删除对象以是否为null做区分
然后从链表头开始遍历,一旦匹配,就会调用unlink()方法将该节点从链表中移除

下面是unlink()

   /**
     * Unlinks non-null node x.
     */
    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;
    }

澳门新葡萄京官网注册 13

unlink第一步

第一步:得到待删除节点的前驱节点和后继节点

澳门新葡萄京官网注册 14

unlink第二步

第二步:删除前驱节点

澳门新葡萄京官网注册 15

unlink第三步

第三步:删除后继节点
经过三步,待删除的结点就从链表中脱离了。需要注意的是删除位置是头节点或尾节点时候的处理,上面的示意图没有特别指出。

3.2 按照位置删除对象

3.2.1 删除任意位置的对象

  • boolean remove(int index)
    删除任意位置的元素,删除成功将返回true,否则false

  /**
    * Removes the element at the specified position in this list.  Shifts any
    * subsequent elements to the left (subtracts one from their indices).
    * Returns the element that was removed from the list.
    *
    * @param index the index of the element to be removed
    * @return the element previously at the specified position
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
   public E remove(int index) {
       checkElementIndex(index);
       return unlink(node(index));
   }
  1. 检查index范围,属于[0,size)
  2. 将索引出节点删除

3.2.2 删除头节点的对象

  • remove()、removeFirst()、pop()
    在链表为空时将抛出NoSuchElementException

  /**
     * 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();
    }

  /**
     * 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();
    }

  /**
     * 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);
    }

remove()和pop()内部调用了removeFirst()
而removeFirst()在链表为空时将抛出NoSuchElementException

  • poll()和,pollFirst()
    在链表为空时将返回null

  /**
     * 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 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);
    }

poll()和pollFirst()的实现代码是相同的,在链表为空时将返回null

3.2.3 删除尾节点的对象

  • removeLast()

  /**
     * 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);
    }

可以看到removeLast()在链表为空时将抛出NoSuchElementException

  • pollLast()

  /**
     * 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);
    }

可以看到pollLast()在链表为空时会返回null,而不是抛出异常

3.3 删除操作总结

删除操作由很多种方法

按照指定对象删除

boolean remove(Object o),一次只会删除一个匹配的对象

按照指定位置删除

  • 删除任意位置的对象
    E remove(int index),当index越界时会抛出异常
  • 删除头节点位置的对象
    • 在链表为空时抛出异常
      E remove()、E removeFirst()、E pop()
    • 在链表为空时返回null
      E poll()、E pollFirst()
  • 删除尾节点位置的对象
    • 在链表为空时抛出异常
      E removeLast()
    • 在链表为空时返回null
      E pollLast()

4迭代器

LinkedList的iterator()内部调用了其listIterator()方法,所以可只分析listIterator()方法listIterator()提供了两个重载方法。

iterator()方法和listIterator()方法的关系如下

 public Iterator<E> iterator() {
        return listIterator();
    }

public ListIterator<E> listIterator() {
        return listIterator(0);
    }

 public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

从上面可以看到三者的关系是iterator()——>listIterator(0)——>listIterator(int index)
最终都会调用listIterator(int index),其中参数表示迭代器开始的位置
ListIterator是一个可以指定任意位置开始迭代,并且有两个遍历方法

下面直接看ListItr

private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;//保存当前modCount,确保fail-fast机制

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);//得到当前索引指向的next节点
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        //获取下一个节点
        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        //获取前一个节点,将next节点向前移
        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;
        }

        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

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

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

构造器中,得到了当前位置的节点,就是变量next
next()返回当前节点的值并将next指向其后继节点
previous()返回当前节点的前一个节点的值并将next节点指向其前驱节点
由于Node是一个双端节点,所以这儿用了一个节点就可以实现从前向后迭代和从后向前迭代
另外在ListIterator初始时,exceptedModCount保存了当前的modCount,如果在迭代期间,有操作改变了链表的底层结构,那么再操作迭代器的方法时将会抛出ConcurrentModificationException。

5 例子

由于LinkedList是一个实现了Deque的双端队列,所以LinkedList既可以当做Queue,又可以当做Stack,下面的例子将LinkedList成Stack

public class LinkedStack<E> {

    private LinkedList<E> linkedList;

    public LinkedStack() {
        linkedList = new LinkedList<E>();
    }

    //压入数据
    public void push(E e) {
        linkedList.push(e);
    }

    //弹出数据,在Stack为空时将抛出异常
    public E pop() {
        return linkedList.pop();
    }

    //检索栈顶数据,但是不删除
    public E peek() {
        return linkedList.peek();
    }

}

在将LinkedList当做Stack时,使用pop()、push()、peek()方法需要注意的是LinkedList内部是将链表头部当做栈顶,链表尾部当做栈底,也就意味着所有的压入、摊入操作都在链表头部进行

6总结

LinkedList是基于双端链表的List,其内部的实现源于对链表的操作

  • 适用于频繁增加、删除的情况
  • 该类不是线程安全的
  • 由于LinkedList实现了Queue接口,所以LinkedList不止有队列的接口,还有栈的接口,可以使用LinkedList作为队列和栈的实现

发表评论

电子邮件地址不会被公开。 必填项已用*标注