LinkedList看完你就明白了

JDK版本:1.8

图0

类的结构和常用方法如下:

图中包含两个构造函数，8个方法，我们依次看一下

空构造函数

    /**
     * 初始化一个空的链表
     */
    public LinkedList() {
    }

众所周知，数据结构是用来存放各种数据的，这个空的构造函数直接想让我看一下他的属性或者变量都包含什么东西- -

  //链表中元素数量
   transient int size = 0;

    /**
     * 第一个元素
     */
    transient Node<E> first;

    /**
     * 最后一个元素
     */
    transient Node<E> last;

哦？有个Node<E>的泛型类，Node是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;
        }
    }

Node类中的属性类型也是Node，一个Node 属性包含 上一个node，当前node的值，下一个node，这样就可以组成一个串连接起来
一个node就像下面这个图:三个人手拉手

image.png

item可以认为是当前元素，那如果当前元素是首元素，那么它的pre肯定为null
如果item为最后一个元素，那么它的next肯定为null
LinkedList只是把Node的长度，首元素，尾元素给当做内部变量存了起来
了解到这里我们看第二个构造函数

带参构造函数

//集合的大小
transient int size = 0;
public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
//把size取出用于检
public boolean addAll(Collection<? extends E> c) {
        //此处为插入的位置,如果为size本身 则默认插入从尾部插入
        return addAll(size, c);
    }
public boolean addAll(int index, Collection<? extends E> c) {
        //检测索引位置是否合法
        checkPositionIndex(index);
    
        Object[] a = c.toArray();
        int numNew = a.length;
       //如果为空数组则直接返回false
        if (numNew == 0)
            return false;
        // pred为上一节点 succ为当前节点(插入位置的节点 为index不等于size的情况)
        //succ为被插入当前位置的节点  首次为null
        Node<E> pred, succ;
        if (index == size) {
            //从链表的末尾插入元素
            succ = null;
            pred = last;
        } else {
            //获取被插入的节点 并
            succ = node(index);
            //将被插入节点的上一节点赋值给pred
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            //pred为null 则说明当前插入的是首个元素
            if (pred == null)
                first = newNode;
            else
                //将上一节点的next属性指向新节点
                pred.next = newNode;
            //pred后移一位
            pred = newNode;
        }
        //首次
        if (succ == null) {
            last = pred;
        } else {
           //非首次
            pred.next = succ;
            succ.prev = pred;
        }
        size += numNew;
        modCount++;
        return true;
    }

举个例子:
这个方法同时适配了 空链表和非空脸链表的情况]
拿小朋友手拉手排队举例子
空链表:
A区域没有小朋友，B区域有三个小朋友首拉手 小红<---->小明<---->小黑，现在把B区域的小朋友挪到A区域
流程如下:
①将小红作为A区域的首个人
②将小明挪过来与小红手拉手
③将小黑挪过来和小明手拉手并将小黑作为最后一个人

非空链表:
A区域现在有三个小朋友首拉手 小红<---->小明<---->小黑
C区域现在有两个小朋友手拉手 大力<---->张伟
现在要把C区小朋友插队到小明的位置
①将小红的手与大力的手拉到一起 小红<---->大力 小明<---->小黑
②将张伟的手与大力的手拉到一起 小红<---->大力<---->张伟
③将张伟的手与小明的手拉到一起 小红<---->大力<---->张伟<---->小明<---->小黑
链表的这套算法个人感觉很经典
总结为:处理插入点位置的上一个元素，根据是否存在上一个元素进行不同的处理

方法

contains(object)

 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++;
            }
        }
        //如果链表中不存在 则返回-1
        return -1;
    }

这里我们看到了官方遍历链表的方式

size()

/**
     *直接返回链表中size变量的值
     */
    public int size() {
        return size;
    }

size变量的值会在 add、addAll、remove等方法中改变

add()

    /**
     * 添加元素
     */
public boolean add(E e) {
        linkLast(e);
        return true;
    }
 /**
     * Links e as last element.
     */
    void linkLast(E e) {
        //拿到尾节点
        final Node<E> l = last;
        //创建新节点 新节点的pre节点 挂在尾节点
        final Node<E> newNode = new Node<>(l, e, null);
        //更新尾节点
        last = newNode;
        if (l == null)
            //尾节点如果为null 视为空链表
            first = newNode;
        else
            //次尾节点next节点更新
            l.next = newNode;
        size++;
        modCount++;
    }

好比是:
向队伍的尾巴多加了一个人 让他们手拉手

add(int,E)

    /**
     * 向某一个位置添加元素
     */
 public void add(int index, E element) {
        //索引位置的值和size是否合法
        checkPositionIndex(index);
        //链表size为2，index如果也为2代表要新增一个元素 因为index本身和size是差1的关系
        if (index == size)
            linkLast(element);
        else
            //将元素插入到链表的中间位置
            linkBefore(element, node(index));
    }

 /**
     * Links e as last element.
     */
    void linkLast(E e) {
        //拿到尾节点
        final Node<E> l = last;
        //创建新节点 新节点的pre节点 挂在尾节点
        final Node<E> newNode = new Node<>(l, e, null);
        //更新尾节点
        last = newNode;
        if (l == null)
            //尾节点如果为null 视为空链表
            first = newNode;
        else
            //次尾节点next节点更新
            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++;
    }

    /**
     *  根据索引获取链表中的元素
     */
    Node<E> node(int index) {
        //size右移一位本身值除2 这里用到二分法 看索引距离首个节点较近 还是尾部节点较近
        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;
        }
    }

peek()

//把第一个拿出来
public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

拿第一个出来，如果是个空的链表，则返回null

element()

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

拿第一个出来，如果是个空的链表，则报错

poll()

/**
* 将头元素返回并且删掉
*/
public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        //取出header节点的值
        final E element = f.item;
        //取出第二个节点的值
        final Node<E> next = f.next;
        //将第一个节点值给null
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

拿第一个出来

offer()

//这里的offer完全是为了重写Queue接口的方法 没啥特别的 同add
public boolean offer(E e) {
        return add(e);
    }

队列接口和列表接口
offer -----add
poll -----remove
peek ----get(0)
链表的addAll方法还是值得学习的，这个链表也不是线程安全的噢
如果实现线程安全 请使用
Collections.synchronizedList(new LinkedList())包装一下