Java容器解析——LinkedList

Java容器解析——ArrayList

Java容器解析——LinkedList

Java容器解析——Hashtable

1 LinkedList类定义

LinkedList 是一个继承于AbstractSequentialList的双向链表。其定义如下：

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

由定义可以看出：

LinkedList<E>,支持泛型
实现Deque接口，说明可以当做队列
实现Serializable接口, 可序列化
实现Cloneable接口

2 属性值

//集合元素数量
transient int size = 0;
//链表头节点
transient Node<E> first;
//链表尾节点
transient Node<E> last;

节点结构定义

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是双向链表结构。

3 构造函数

1 无参数构造函数

    public LinkedList() {
    
    }

2 使用集合创建

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

addAll()方法

    public boolean addAll(Collection<? extends E> c) {
    
        //以size为插入位置索引，插入集合c中所有元素
        return addAll(size, c);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
    
        //检查索引位置是否合法
        checkPositionIndex(index);

        //将目标集合c转为数组
        Object[] a = c.toArray();
        //获得待添加目标数组的长度
        int numNew = a.length;
        //若长度为0，无需添加，直接返回
        if (numNew == 0)
            return false;

        //index节点的前置节点，后置节点
        Node<E> pred, succ;
        
        //在链表尾部追加数据
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            //取出index节点，作为后置节点
            succ = node(index);
            //前置节点是，index节点的前一个节点
            pred = succ.prev;
        }
        
        //变量数组a，依次添加节点
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //以前置节点pred 和 元素值e，构建new一个新节点，
            Node<E> newNode = new Node<>(pred, e, null);
            //如果前置节点pred是空，说明是头结点
            if (pred == null)
                first = newNode;
            else////前置节点不为空则将pred的后置节点设置为新节点newNode
                pred.next = newNode;
            pred = newNode;//将当前节点指针向后移动
        }

        //遍历结束，到达链表尾，设置尾节点
        if (succ == null) {
            last = pred;
        } else {
            //否则是在队中插入的节点 ，更新前置节点 后置节点
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;//更新节点数量size
        modCount++;
        return true;
    }

4 核心方法

方法名	含义	时间复杂度
get(int index)	根据索引获取元素	O(n)
add(E e)	添加元素	O(1)
add(int index, E element)	添加元素到指定位置	O(n)
remove(int index)	删除索引为index的元素	O(n)
set(int index, E element)	设置索引为index的元素值	O(n)
size()	返回当前容器元素大小	O(1)
isEmpty()	判断容器是否为空	O(1)
contains(Object o)	判断是否包含某个元素	O(n)
indexOf(Object o)	获取某元素在列表中索引	O(n)
clear()	清空列表	O(n)

5 获取元素get()

//根据索引index获取元素
public E get(int index) {
    checkElementIndex(index);//判断是否越界 [0,size)
    return node(index).item; //调用node()方法 取出 Node节点，
}
//根据index 查询出Node
Node<E> node(int index) {
        // assert isElementIndex(index);
        // 首先根据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;
        }
    }

6 添加元素add

（1）直接添加节点至末尾

    //在尾部插入一个节点： add
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    //生成新节点 并插入到 链表尾部， 更新 last/first 节点。
    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++;//修改size
        modCount++;//修改modCount
    }

（2）在指定下标位置插入节点

    //在指定下标，index处，插入一个节点
    public void add(int index, E element) {
        checkPositionIndex(index);//检查下标是否越界[0,size]
        if (index == size)//在尾节点后插入
            linkLast(element);
        else//在中间插入
            linkBefore(element, node(index));
    }
    //在succ节点前，插入一个新节点e
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        //保存后置节点的前置节点
        final Node<E> pred = succ.prev;
        //以前置和后置节点和元素值e 构建一个新节点
        final Node<E> newNode = new Node<>(pred, e, succ);
        //新节点new是原节点succ的前置节点
        succ.prev = newNode;
        if (pred == null)//如果之前的前置节点是空，说明succ是原头结点。所以新节点是现在的头结点
            first = newNode;
        else//否则构建前置节点的后置节点为new
            pred.next = newNode;
        size++;//修改数量
        modCount++;//修改modCount
    }

7 删除元素remove

（1）删除索引为index的元素

    //删：remove目标节点
    public E remove(int index) {
        //检查是否越界
        checkElementIndex(index);
        //调用unlink删除节点
        return unlink(node(index));
    }
    
    //从链表上删除x节点
    E unlink(Node<E> x) {
    
        // assert x != null;
        //当前节点的元素值，设置为final，不可更改
        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的后置节点置空
        }

        x.item = null; //将当前元素值置空
        size--; //修改数量
        modCount++;  //修改modCount
        return element; //返回取出的元素值
    }
        
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

（2）删除指定的元素

    //因为要考虑 null元素，也是分情况遍历
    public boolean remove(Object o) {
        if (o == null) {//如果要删除的是null节点(从remove和add 里 可以看出，允许元素为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;
    }
    //将节点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) {//前置节点为null，
            first = next;//则首节点为next
        } else {//否则 更新前置节点的后置节点
            prev.next = next;
            x.prev = null;//记得将要删除节点的前置节点置null
        }
        //如果后置节点为null，说明是尾节点
        if (next == null) {
            last = prev;
        } else {//否则更新 后置节点的前置节点
            next.prev = prev;
            x.next = null;//记得删除节点的后置节点为null
        }
        //将删除节点的元素值置null，以便GC
        x.item = null;
        size--;//修改size
        modCount++;//修改modCount
        return element;//返回删除的元素值
    }

8 修改元素set

    public E set(int index, E element) {
     //检查越界[0,size)
        checkElementIndex(index);
        //根据index取出对应的Node
        Node<E> x = node(index);
        //保存旧值 供返回
        E oldVal = x.item;
        //用新值覆盖旧值
        x.item = element;
        //返回旧值
        return oldVal;
    }

9 小结

LinkedList 是双向链表，对其大部分操作属于对双向链表的增删改查。因此，对于LinkedList的学习主要是掌握数据结构链表的操作。此外，LinkedList在查找时使用了折半查找的方式，提升了查找效率。

10 对比

（1）ArrayList是实现了基于动态数组的数据结构，LinkedList是基于链表结构。
（2）对于随机访问的get和set方法，ArrayList要优于LinkedList，因为LinkedList要移动指针。
（3）对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。

11 使用场景

（1）对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是 统一的，分配一个内部Entry对象。
（2）在ArrayList集合中添加或者删除一个元素时，当前的列表所所有的元素都会被移动。而LinkedList集合中添加或者删除一个元素的开销是固定的。
（3）LinkedList集合不支持 高效的随机随机访问（RandomAccess），因为可能产生二次项的行为。
（4）ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间