2020-04-25

基础 / JavaSE

23 分钟读完 (大约 3495 个字) 0次访问

LinkedList 源码分析

LinkedList

部分参考来源:

https://www.cnblogs.com/aflyun/p/6481274.html

https://www.cnblogs.com/ysocean/p/8657850.html

图片来源于 ysocean博主博客的图片

LinkedList 介绍

LinkedList 的继承结构:

1
2
3

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

LinkedList 底层是使用链表实现的. 通过源码可以看出，具有 prev 和 next ，则是一个双向链表。除了当链表之外，我们也可以当成栈(先进后出)，队列(先进先出)和双端队列进行操作。不是线程安全的，继承自AbstractSequentialList ,实现 List, Deque, Cloneable, Serializable.

LinkedList继承自AbstractSequentialList. Sequential的中文意思就是按顺序的，故：LinkedList是不支持随机访问（ArrayList是支持随机访问的）。
LinkedList实现了List接口，即拥有List的所有特点
LinkedList实现了Deque(双端队列)接口，所以可以实现双端队列的作用。
LinkedList实现了Cloneable接口，即覆盖了clone()方法，可以实现克隆。
LinkedList实现了Serializable接口，这意味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 的方法总结

// Get Element
public E getFirst() {}
public E getLast() {}
public E get(int index) {}
public E peek() {}
public E element() {}
public E peekFirst() {}
public E peekLast() {}
public E pollFirst() {}
public E pollLast() {}

// Remove Element
public E pop() {}
public E poll() {}
public E removeFirst() {}
public E removeLast() {}
public boolean remove(Object o) {}
public E remove(int index) {}
public E remove() {}
public boolean removeFirstOccurrence(Object o) {}
public boolean removeLastOccurrence(Object o) {}


// Add Element
public void addFirst(E e) {}
public void addLast(E e) {}
public boolean add(E e) {}
public void add(int index, E element) {}
public boolean addAll(Collection<? extends E> c) {}
public boolean addAll(int index, Collection<? extends E> c) {}
public E set(int index, E element) {}

public boolean offer(E e) {}
public boolean offerFirst(E e) {}
public boolean offerLast(E e) {}
public void push(E e) {}

// Search Element
public boolean contains(Object o) {}
public int size() {}
Node<E> node(int index) {}
public int indexOf(Object o) {}
public int lastIndexOf(Object o) {}

// other
public void clear() {}
public Object[] toArray() {}
public <T> T[] toArray(T[] a) {}

LinkedList 源码分析

Get Element

/**
 * 获取第一个节点，如果集合为empty，则抛出NoSuchElementException
 */
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

/**
 * 获取最后一个节点，如果List为null，则抛出NoSuchElementException
 */
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

/**
 * 返回指定下标的元素
 */
public E get(int index) {
    //检查元素下标是否合法
    checkElementIndex(index);
    return node(index).item;
}

/**
 * 检索返回第一个元素,但不删除，与element()方法不同，如果元素为null,则返回null，不抛出异常
 */
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

/**
 * 检索返回第一个元素，但不删除，如果List为null.抛出 NoSuchElementException
 */
public E element() {
    return getFirst();
}

/**
 * 检索返回第一个元素，但不删除，若List为empty,则返回null
 */
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

/**
 * 检索返回最后一个元素，但不删除，若List为empty，则返回null
 */
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

/**
 * 检索返回第一个元素，但不删除，如果List为empty，则返回null
 */
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * 检索返回最后一个元素，但不删除，如果List为empty，则返回null
 */
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

Remove Element

/**
 * 删除并返回第一个元素，等同于removeFirst().
 */
public E pop() {
    return removeFirst();
}

/**
 * 删除并返回第一个元素。如果List为null，则返回null
 */
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * 删除第一个元素，并返回数据，如果List为空，则抛出NoSuchElementException
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/**
 * 删除最后一个元素，并返回数据，如果List为空，则抛出NoSuchElementException
 */
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

/**
 * 删除第一个符合要求的元素，如果不存在，则不进行任何改变。即：删除符合的元素中下标最小的那个。
 *      分为null 和 not null。返回是否包含指定值（true和false）
 */
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;
}

/**
 * 移除并返回指定下标的元素（后面的元素全部左移，对于链表来说，无需手动移动）。
 *      如果下标不合法，则抛出 IndexOutOfBoundsException
 */
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

/**
 * 检索返回第一个元素，并移除，如果List为null，则抛出NoSuchElementException
 */
public E remove() {
    return removeFirst();
}

/**
 * 移除第一个命中的元素，（从头到尾遍历，即顺序遍历），若不包含，则不改变
 */
public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}

/**
 * 移除最后一个命中的元素，（从尾遍历到头，即倒序遍历），若不包含，则不改变
 */
public boolean removeLastOccurrence(Object o) {
    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;
}

Add Element

[图片来源于YSOcean]

addFirst(E e) 将指定元素添加到链表头部

addLast(E e) 和 add(E e) 将指定元素添加到链表尾部.

add(int index, E element) 将指定的元素插入到链表的指定位置。

/**
 * 在头部插入一个元素
 */
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * 在尾部插入一个元素，与add()方法作用一致
 */
public void addLast(E e) {
    linkLast(e);
}

/**
 *  add方法默认将 元素添加到链表最后，等同于 addLast()
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 *  将元素添加到指定下标处，原下标位置元素及所有右边元素均向后移动（链表无需手动操作）
 *      如果下边不合法，则抛出IndexOutOfBoundsException
 */
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

/**
 * 添加指定集合中的所有元素到当前链表的最后。
 */
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

/**
 * 添加指定集合中的所有元素到当前集合中。
 *      若给定集合为null，则抛出 NullPointerException
 *      若元素下标不合法，则抛出 IndexOutOfBoundsException
 */
public boolean addAll(int index, Collection<? extends E> c) {
    //检查下标是否违法
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0) //给定集合为empty，则返回false
        return false;

    //分为添加到链表最后，和添加到链表中
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

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

    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;
    modCount++;
    return true;
}

/**
 * 将元素替换指定下标的元素。如果元素不合法，则抛出IndexOutOfBoundsException。
 */
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

/**
 * 添加一个元素到尾部
 */
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;
}

/**
 * 添加一个元素到首部
 */
public void push(E e) {
    addFirst(e);
}

Search Element

/**
 * 判断当前元素是否在集合中，（可以为null）
 * (o==null ? e==null : o.equals(e))
 */
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

/**
 * 查找第一个符合的元素的下标(使用顺序遍历)，如果没有，则返回-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++;
        }
    }
    //如果没有找到，则返回-1
    return -1;
}

/**
 *  查找最后一个符合的元素的下标(使用倒序遍历），如果没有，则返回-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;
}

other

/**
 * 集合元素的个数
 */
public int size() {
    return size;
}

/**
 * 移除集合中的所有元素。
 */
public void clear() {
    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;
    size = 0;
    modCount++;
}

/**
 * 将链表转化为数组
 */
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

/**
 *  将集合填充到给定数据中，如果给定的数组大小小于集合元素的个数，则全部替换。
 *  如果数组元素大于集合元素个数，则将集合大小的下标的元素设置为null，
 *  如果给定数据为null，则抛出NullPointerException
 *
 *  集合为：{"A","B","C","D"}.
 * 若数组为：{"AA","BB","CC","DD","EE","FF"},    ==> {"A","B","C","D",null,"FF"}
 * 若数组为：{"AA","BB","CC"} 或 {"AA","BB","CC","DD"}  ==> {"A","B","C","D"}
 *
 */
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    //如果数据的长度小于当前集合元素的个数，创建一个size大小的数组
    if (a.length < size)
        a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
    int i = 0;
    Object[] result = a;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;

    if (a.length > size)
        //如果数组大小大于元素个数，将size位置上的元素设置为null
        a[size] = null;
    return a;
}

ArrayList与LinkedList遍历性能比较

ArrayList性能测试

@Test
public void test(){
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < 100000; i++) {
        list.add(i);
    }

    long start1 = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {
        list.get(i);
    }
    long end1 = System.currentTimeMillis();
    System.out.println("普通for："+(end1 - start1));

    long start2 = System.currentTimeMillis();
    for (Integer i : list) {}
    long end2 = System.currentTimeMillis();
    System.out.println("增加for："+(end2 - start2));


    long start3 = System.currentTimeMillis();
    ListIterator<Integer> listIterator = list.listIterator();
    while(listIterator.hasNext()){
        listIterator.next();
    }
    long end3 = System.currentTimeMillis();
    System.out.println("ListIterator:"+(end3 - start3));


    long start4 = System.currentTimeMillis();
    Iterator<Integer> iterator = list.iterator();
    while(iterator.hasNext()){
        iterator.next();
    }
    long end4 = System.currentTimeMillis();
    System.out.println("iterator:"+(end4-start4));
}
//测试结果
/**
普通for:1
增加for:3
ListIterator:5
iterator:1
*/

LinkedList性能测试

@Test
public void test(){
    LinkedList<Integer> linkedList = new LinkedList<>();
    for (int i = 0; i < 100000; i++) {
        linkedList.add(i);
    }

    //使用普通for循环遍历
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < linkedList.size(); i++) {
        linkedList.get(i);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("普通for循环："+(endTime-startTime));

    //使用增强for循环遍历
    long start1 = System.currentTimeMillis();
    for (Integer i : linkedList) {}
    long end1 = System.currentTimeMillis();
    System.out.println("增加for循环："+(end1 - start1));

    //使用ListIterator
    ListIterator<Integer> iterator = linkedList.listIterator();
    long start = System.currentTimeMillis();
    while(iterator.hasNext()){
        iterator.next();
    }
    long end = System.currentTimeMillis();
    System.out.println("使用ListIterator遍历:"+(end - start));


    Iterator<Integer> iter = linkedList.iterator();
    long start2 = System.currentTimeMillis();
    while(iter.hasNext()){
        iter.next();
    }
    long end2 = System.currentTimeMillis();
    System.out.println("使用iterator:"+(end2 - start2));
}
//测试结果
/**
普通for循环:3807
增加for循环:2
使用ListIterator遍历:1
使用iterator:1
*/

通过上述测试可以知道，用100000条数据来测试，可以发现遍历所消耗的时间大部分都相似，但是唯独LinkedList 在使用普通for循环的时候，花费的时间是其他的上千倍。

代码很简单，就是使用LinkedList 的 get(int index) 方法，遍历出所有的元素。但是需要注意的是，get(int indx) 方法每次都要遍历该索引之前的所有元素，这句话这么理解：

比如我们使用一个LinkedList 集合，存储A,B,C,D四个元素，总共需要四次遍历：

第一次遍历打印A : 还需要遍历一次。
第二次遍历打印B : 需要先找到A，然后再找到B打印。
第三次遍历打印C : 需要先找到A，然后找到B，然后找到C打印。
第四次遍历打印D : 需要先找到A，然后找到B，然后找到C，最后找到D。

这样如果集合元素越多，查找的时间就越久。如上述测试结果所示。

下面使用YSOcean 博主的图再解释一下：

普通for循环：每次遍历一个索引的元素之前，都要访问之间所有的索引。

迭代器：每次访问一个元素后，都会用游标记录当前访问元素的位置，遍历一个元素，记录一个位置。

总结

LinkedList的实现是基于双向链表，实现了List和Deque接口。实现了所有可选的列表操作，并允许所有元素（包括null）
LinkedList是线程不安全的，只能在单线程的情况下适合使用
这个类的iterator和返回的迭代器listIterator方法是fail-fast, 要注意ConcurrentModificationException.
LinkedList实现了Serializable接口，支持序列化，能够通过序列化传输，实现了Cloneable接口，能被克隆。
在查找和删除元素是，都分为元素是null和不为null两种情况来处理，LinkedList中允许元素为null.
LinkedList是基于链表的，LinkedList没有扩容方法，插入元素默认就自动扩容了。

LinkedList还实现了栈和队列的操作方法，因此也可以作为栈，队列和双端队列来使用。

//栈的特性是:先进后出
可以使用 pop()和push()实现栈 
    pop()  删除并返回第一个元素。
    push() 添加一个元素到首部。
//队列的特性是:先进先出
 可以使用 addFirst(), addLast(), removeFirst()和 removeLast() 
    addFirst() 在头部插入元素
    addLast() 在尾部插入元素
    removeFirst() 在头部移除一个元素并返回
    removeLast() 在尾部移除一个元素并返回

LinkedList是基于链表实现的，因此插入删除效率高，查询效率低，不支持随机访问（只能进行遍历）

本文标题：LinkedList 源码分析
本文作者：ouYang
本文链接：https://ooyhao.github.io/2020/04/25/%E5%9F%BA%E7%A1%80/LinkedList/
发布时间：2020-04-25
版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！

# JavaSE

LinkedList 源码分析

LinkedList

LinkedList 介绍

LinkedList 的方法总结

LinkedList 源码分析

Get Element

Remove Element

Add Element

Search Element

other

ArrayList与LinkedList遍历性能比较

ArrayList性能测试

LinkedList性能测试

总结

评论

目录

链接

分类

标签云

最新文章

归档

标签

Your browser is out-of-date!