LinkedList和ArrayList一样是集合List的实现类,虽然较之ArrayList,其使用场景并不多,但同样有用到的时候,那么接下来,我们来认识一下它。
 
一. 定义一个LinkedList
public static void main(String[] args) {
    List<String> stringList = new LinkedList<>();
    List<String> tempList = new ArrayList<>();
    tempList.add("牛魔王");
    tempList.add("蛟魔王");
    tempList.add("鹏魔王");
    tempList.add("狮驼王");
    tempList.add("猕猴王");
    tempList.add("禺贼王");
    tempList.add("美猴王");
    List<String> stringList2 = new LinkedList<>(tempList);
}
ASP站长网上面代码中采用了两种方式来定义LinkedList,可以定义一个空集合,也可以传递已有的集合,将其转化为LinkedList。我们看一下源码
 
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Java.io.Serializable{
    transient int size = 0;
 
    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;
 
    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
 
    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }
 
    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
}
LinkedList继承了AbstractSequentialList类,实现了List接口,AbstractSequentialList中已经实现了很多方法,如get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index),这些方法是我们集合操作时使用最多的,不过这些方法在LinkedList中都已经被重写了,而抽象方法在LinkedList中有了具体实现。因此我们回到LinkedList类
 
LinkedList类中定义了三个变量
 
size:集合的长度
 
first:双向链表头部节点
 
last:双向链表尾部节点
 
针对first变量和last变量,我们看到是Node类的实体,这是一个静态内部类,关于静态内部类的讲解,我们在static五大应用场景一章已经有说明
 
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是通过双向链表实现的,而双向链表就是通过Node类来体现的,类中通过item变量保存了当前节点的值,通过next变量指向下一个节点,通过prev变量指向上一个节点。
 
二. LinkedList常用方法
1. get(int index)
我们知道随机读取元素不是LinkedList所擅长的,读取效率比起ArrayList也低得多,那么我来看一下为什么
 
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
 
/**
 * 返回一个指定索引的非空节点.
 */
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;
    }
}
从上述代码中我们可以看到get(int index)方法是通过node(int index)来实现的,它的实现机制是:
 
比较传入的索引参数index与集合长度size/2,如果是index小,那么从第一个顺序循环,直到找到为止;如果index大,那么从最后一个倒序循环,直到找到为止。也就是说越靠近中间的元素,调用get(int index方法遍历的次数越多,效率也就越低,而且随着集合的越来越大,get(int index)执行性能也会指数级降低。因此在使用LinkedList的时候,我们不建议使用这种方式读取数据,可以使用getFirst(),getLast()方法,将直接用到类中的first和last变量。
 
2. add(E e) 和 add(int index, E element)
大家都在说LinkedList插入、删除操作效率比较高,以stringList.add(“猪八戒”)为例来看到底发生了什么?
 
在LinkedList中我们找到add(E e)方法的源码
 
public boolean add(E e) {
    linkLast(e);
    return true;
}
 
/**
 * 设置元素e为最后一个元素
*/
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++;
}
很好理解:
 
情况1:假如stringList为空,那么添加进来的node就是first,也是last,这个node的prev和next都为null;

dawei

【声明】:九江站长网内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。