秦怀杂货店

General Store

  • 首页
  • 文章归档
  • 标签
  • 分类
  • 关于页面

  • 搜索
随便聊聊 数据结构 小游戏 数据库 Docker Springboot 系统设计 雪花算法 分布式 海量ip 最长回文子串 算法 面试题 线程池 多线程 线程 java学习 布隆过滤器 github 架构设计 docsify Git JVM LeetCode 杂货思考 设计模式 Lambda native isAssignableFrom 反射 剑指Offer mybatis SPI JDBC 编程工具 Java基础 集合

java集合【10】——— LinkedList源码解析

发表于 2020-12-05 | 分类于 Java集合 | 0 | 阅读次数 258

1.LinkedList介绍

我们除了最最常用的ArrayList之外,还有LinkedList,这到底是什么东西?从LinkedList官方文档,我们可以了解到,它其实是实现了List和Queue的双向链表结构,而ArrayList底层则是数组结构。

下面的讲解基于jdk 1.8:

继承了AbstractSequentialList,实现了List,Queue,Cloneable,Serializable,既可以当成列表使用,也可以当成队列,堆栈使用。主要特点有:

  • 线程不安全,不同步,如果需要同步需要使用List list = Collections.synchronizedList(new LinkedList());
  • 实现List接口,可以对它进行队列操作
  • 实现Queue接口,可以当成堆栈或者双向队列使用
  • 实现Cloneable接口,可以被克隆,浅拷贝
  • 实现Serializable,可以被序列化和反序列化

下面是LinkedList的结构,注意:指针结束指向的是node,开始的是prev或者next

源码定义如下:

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

2.成员变量

成员变量相对比较简单,因为不像ArrayList一样,需要使用数组保存元素,LinkedList是靠引用来关联前后节点,所以这里只有大小,第一个节点,最后一个节点,以及序列化的uid。

    // 大小
    transient int size = 0;
    // 第一个节点
    transient Node<E> first;
    // 最后一个节点
    transient Node<E> last;
		// 序列化uid
    private static final long serialVersionUID = 876323262645176354L;

我们来看看Node到底是何方神圣?
其实就是内部类,里面的item是真正保存节点的地方,next是下一个节点的引用,prev是上一个节点的引用。这里也体现了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;
        }
    }

3. 构造函数

构造函数有两个,一个是无参数构造函数,另一个是初始化集合元素,里面调用的其实是addAll,一看就是将里面所有的元素加入到集合中。

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

4. 常用List方法解析

4.1 查找相关

4.1.1 getFirst()

获取第一个元素:

    public E getFirst() {
        // 保存第一个元素为f,注意是final的,
        final Node<E> f = first;
        if (f == null)
            // 如果没有第一个元素,那么就会抛出异常
            throw new NoSuchElementException();
        // 返回第一个元素的item
        return f.item;
    }

4.1.2 getLast()

获取最后一个元素,和获取第一个的原理差不多

    public E getLast() {
        // 保存最后一个元素的引用为l
        final Node<E> l = last;
        // 如果为空,抛出错误
        if (l == null)
            throw new NoSuchElementException();
        // 返回item
        return l.item;
    }

4.1.3 get(int index)

通过索引来获取元素,里面是调用了另外一个方法先获取节点,再获取该节点的item,在此之前,做了index安全性校验。

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

在👆上面的代码中调用了通过索引位置查找节点位置的函数,下面我们来分析一下这个函数,由于底层是链表实现的,所以呢?遍历起来不是很方便,就考虑到位运算,如果索引位置在后面一半,就从后往前遍历查找,否则从前往后遍历。

    Node<E> node(int index) {
        // assert isElementIndex(index);
				// size>>1 表示除以2,相当于index小于size的一半
        if (index < (size >> 1)) {
          	// 从前面开始遍历,取出first节点,因为中间过程引用会变化,所以不可直接操作first
            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;
        }
    }

4.1.4 indexOf(Object o)

查找某一个元素的索引位置,分为两种情况讨论,如果要查找的元素为空,那么就使用==,否则使用equals(),这也从侧面印证了LinedList实际上是可以存储null元素的。使用计数查找:

    public int indexOf(Object o) {
        int index = 0;
      	// 如果需要查找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++;
            }
        }
        return -1;
    }

4.1.5 lastIndexOf(Object o)

和前面的indexOf差不多,区别就是这个是后面开始查找,找到第一个符合的元素。

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

4.2 添加元素

4.2.1 addFirst(E e)

将元素e,添加到第一个节点,公有方法是addFirst(),但是其实内部调用是linkFirst(),这是private方法。

    public void addFirst(E e) {
        linkFirst(e);
    }
    private void linkFirst(E e) {
        // 先保存第一个节点
        final Node<E> f = first;
        // 初始化一个新节点,prev是null,next是f(之前的首节点)
        final Node<E> newNode = new Node<>(null, e, f);
        // 更新first为新节点
        first = newNode;
        // 如果之前的第一个节点是空的,那么就说明里面是空的,没有元素
        if (f == null)
            // 最后一个元素也是新加入的元素
            last = newNode;
        else
            // f的prev前置节点的引用更新为新的节点
            f.prev = newNode;
        // 个数增加
        size++;
        // 修改次数增加
        modCount++;
    }

4.2.2 addLast(E e)

将元素添加在链表最后,其实内部也是直接调用的private方法linkLast():

    public void addLast(E e) {
        linkLast(e);
    }
    void linkLast(E e) {
        // 保存最后一个节点的引用
        final Node<E> l = last;
        // 初始化一个节点,前置节点指针引用指向之前的最后一个节点,后续节点的引用是null
        final Node<E> newNode = new Node<>(l, e, null);
        // 将最后一个节点更新
        last = newNode;
        // 如果之前的最后一个节点是null,说明链表是空的
        if (l == null)
            // 新节点同时是第一个节点
            first = newNode;
        else
            // 否则之前的最后一个节点的后续节点引用更新为新的节点
            l.next = newNode;
        // 大小+1
        size++;
        // 修改次数+1
        modCount++;
    }

4.2.3 add(E e)

增加元素,默认也是在链表的最后添加,完成返回true:

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

4.2.4 addAll(Collection<? extends E> c)

往链表里面批量添加元素,里面默认是在最后面批量添加,内部调用的是addAll(int index, Collection<? extends E> c),添加之前会判断索引位置是不是合法的。
然后查找需要插入的位置的前后节点,循环插入。

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        // 检查添加位置
        checkPositionIndex(index);

        // 将需要添加的集合转换成为数组
        Object[] a = c.toArray();
        // 获取数组的大小
        int numNew = a.length;
        // 如果数组长度为0,说明没有需要添加的元素,返回false
        if (numNew == 0)
            return false;

        // 插入位置的前节点和后续节点
        Node<E> pred, succ;
        // 如果插入位置索引大小等于链表大小,那么就是在最后插入元素
        if (index == size) {
            // 最后插入元素没有后续节点
            succ = null;
            // 前一个节点就是之前的最后一个节点
            pred = last;
        } else {
            // 查找到索引为index 的节点
            succ = node(index);
            // 获取前一个节点
            pred = succ.prev;
        }
        
        // 循环插入节点
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            // 初始化新节点,上一个节点是pred
            Node<E> newNode = new Node<>(pred, e, null);
            // 如果前一个节点是null,那么第一个节点就是新的节点
            if (pred == null)
                first = newNode;
            else
                // 否则pred的next置为新节点
                pred.next = newNode;
            pred = newNode;
        }

        // 如果插入位置没有后续节点,也就是succ为null
        if (succ == null) {
            // 最后一个节点也就是pred,刚刚插入的新节点
            last = pred;
        } else {
            // 加入所有元素之后的最后一个节点的下一个节点指向succ(后续元素)
            pred.next = succ;
            // 插入位置的后续元素的上一个节点引用指向pred
            succ.prev = pred;
        }
      	// 大小改变
        size += numNew;
      	// 修改次数增加
        modCount++;
        return true;
    }

上面的代码调用了node(index),这个在前面查找的时候已经说过了,不再解释。

4.2.5 addAll(int index, Collection<? extends E> c)

在指定位置批量插入节点:

    public boolean addAll(int index, Collection<? extends E> c) {
      	// 检查索引合法性
        checkPositionIndex(index);
      	// 将需要插入的集合转换成为数组
        Object[] a = c.toArray();
      	// 数组的长度
        int numNew = a.length;
      	// 为0则不需要插入
        if (numNew == 0)
            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;
          	// 初始化节点,前置节点是插入位置的前节点,后续节点为null
            Node<E> newNode = new Node<>(pred, e, null);
          	// 如果插入位置前一个节点是null,说明插入位置是链表首
            if (pred == null)
              	// 首节点就是新插入的节点
                first = newNode;
            else
              	// 前节点的next指向新节点
                pred.next = newNode;
          	// 更新插入位置的前一个节点
            pred = newNode;
        }
      	// 如果插入位置的后一个节点为空,说明插入位置是链表尾部
        if (succ == null) {
          	// 最后一个元素就是插入的元素
            last = pred;
        } else {
          	// 将插入的最后一个元素next指向succ
            pred.next = succ;
          	// succ的上一个元素指向prev
            succ.prev = pred;
        }
      	// 大小更新
        size += numNew;
      	// 修改次数改变
        modCount++;
      	// 返回成功
        return true;
    }

4.2.6 add(int index,E element)

将元素插入在指定位置,先判断索引位置,如果索引位置是最后一个,那么直接调用在最后添加元素函数即可,否则需要调用另外一个函数,在某个元素前面插入:

    public void add(int index, E element) {
      	// index校验
        checkPositionIndex(index);
      	
      	// 索引等于链表大小
        if (index == size)
          	// 直接在最后插入元素
            linkLast(element);
        else
          	// 在某个节点前插入元素
            linkBefore(element, node(index));
    }

4.3 删除元素

4.3.1 removeFirst()

删除第一个节点,先获取首节点,判断第一个节点是不是为空,如果为空则证明没有该节点,抛出异常,内部调用的其实是unlinkFirst()。返回值是被移除的节点里面的数值。

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
		// 移除首节点
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
      	// 获取里面的元素
        final E element = f.item;
      	// 保存下一个节点
        final Node<E> next = f.next;
      	// 将之前的首节点前后节点引用置空,有利于GC
        f.item = null;
        f.next = null; // help GC
      	// 首节点更新
        first = next;
      	// 如果首节点是空的,那么链表没有元素了,最后一个节点自然也是null
        if (next == null)
            last = null;
        else
          	// 否则当前的第一个节点的前置节点置null
            next.prev = null;
      	// 链表大小-1
        size--;
      	// 修改次数增加
        modCount++;
        return element;
    }

4.3.2 removeLast()

删除最后一个节点,和上面的删除首节点差不多,先取出最后一个节点,判断是否为空,如果为空则抛出异常,否则会调用另一个解除连接的函数unLinkLast()。

    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
      	// 保存被移除的节点的item
        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
          	// 否则将上一个节点的next置null
            prev.next = null;
      	// 大小该表
        size--;
      	// 修改次数增加
        modCount++;
      	// 返回被移除的节点的item值
        return element;
    }

4.3.3 remove(Object o)

删除某个元素分为两种情况,元素为null和非null,直接遍历判断,里面真正删除的方法其实是unlink(E e),成功移除则返回true,注意这里只会移除掉第一个,后续要是还有该节点,不会移除。

    public boolean remove(Object o) {
      	// 元素为null
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
          	// 元素不为null
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                  	// 移除节点
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

unLink(E e)方法如下:

    E unlink(Node<E> x) {
        // assert x != null;
      	// 保存被移除节点的item
        final E element = x.item;
      	// 下一个节点
        final Node<E> next = x.next;
      	// 上一个节点
        final Node<E> prev = x.prev;
      	// 如果前置节点为空,那么首节点就是当前节点了
        if (prev == null) {
            first = next;
        } else {
          	// 前一个节点的next置为下一个节点
            prev.next = next;
          	// 之前的节点的前一个节点置null
            x.prev = null;
        }
      	// 如果next是空的,那么上一个节点就是现在最后一个节点
        if (next == null) {
            last = prev;
        } else {
          	// next的上一个节点引用指向prev
            next.prev = prev;
          	// 被删除的元素的next置空
            x.next = null;
        }
      	// item置空
        x.item = null;
      	// 大小改变
        size--;
      	// 修改次数增加
        modCount++;
      	// 返回被删除的节点里面的item
        return element;
    }

4.3.4 clear()

移除里面所有的元素:

    public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        for (Node<E> x = first; x != null; ) {
          	// 保存下一个
            Node<E> next = x.next;
          	// 当前元素置空
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
      	// 首节点和尾节点全部置null
        first = last = null;
        size = 0;
        modCount++;
    }

4.3.5 remove(int index)

移除指定索引的元素。先通过索引找到节点,再移除指定的节点

    public E remove(int index) {
      	// 检查合法性
        checkElementIndex(index);
      	// 先找到节点,再移除指定节点
        return unlink(node(index));
    }

4.4 更新元素

4.4.1 set(int index,E element)

更新指定索引的位置的元素,首先通过索引查找到该元素,然后修改item值,返回旧的item值。

    public E set(int index, E element) {
      	// 检查索引是否合法
        checkElementIndex(index);
      	// 通过索引查找到节点
        Node<E> x = node(index);
      	// 保存旧的值
        E oldVal = x.item;
      	// 修改
        x.item = element;
      	// 返回旧的元素
        return oldVal;
    }

5 queue相关的方法

因为LinkedList也实现了queue接口,所以它肯定也实现了相关的方法,下面我们看看:

5.1 peek()

获取队列第一个元素:

    public E peek() {
      	// 拿到第一个元素,final不可变
        final Node<E> f = first;
      	// 返回item值
        return (f == null) ? null : f.item;
    }

5.2 element()

也是获取队列第一个元素,里面调用的是getFirst()。

    public E element() {
        return getFirst();
    }

5.3 poll()

移除队列第一个节点元素并返回,里面调用的其实是unlinkFirst()

    public E poll() {
      	// 获取到第一个元素
        final Node<E> f = first;
      	// 移除并返回
        return (f == null) ? null : unlinkFirst(f);
    }

5.4 remove()

移除队列第一个元素,里面调用的是removeFirst():

    public E remove() {
        return removeFirst();
    }

5.5 offfer(E e)

在队列后面增加元素:

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

5.6 offerFirst(E e)

往队列的前面插入元素,其实调用的是addFirst()

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

5.7 offerLast(E e)

往队列的后面添加元素,其实调用的是addList()

    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

5.8 peekFirst()

获取第一个节点里面的元素:

    public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

5.9 peekLast()

获取最后一个节点的元素:

    public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }

5.10 pollFirst()

获取第一个元素,并且移除它,使用的是unlinkFirst(E e)

    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

5.11 pollLast()

获取队列最后一个元素,并且移除它,调用的其实是unlinkLast(E e)

    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

5.12 push(E e)

像是堆栈的特点,在前面添加元素:

    public void push(E e) {
        addFirst(e);
    }

5.13 pop()

堆栈的特点,取出队列首的第一个元素

    public E pop() {
        return removeFirst();
    }

5.14 removeFirstOccurrence(Object o)

移除元素,从前往后第一次出现的地方移除掉:

    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

5.15 removeLastOccurrence(Object o)

移除元素,最后一次出现的地方移除掉,和前面分析的一样,分为两种情况,null和非null。

    public boolean removeLastOccurrence(Object o) {
      	// 元素为null
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
          	// 元素不是null
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

6.其他方法

是否包含某个元素,其实调用的是indexOf()方法,如果返回的索引不为-1,则包含:

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

返回大小:

    public int size() {
        return size;
    }

是否为有效元素下标索引,从0到size-1

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

是否为有效位置索引,从0到size

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

获取指定索引位置的ListIterator:

    public ListIterator<E> listIterator(int index) {
      	// 检查合法性
        checkPositionIndex(index);
        return new ListItr(index);
    }

获取倒序的迭代器:

    public Iterator<E> descendingIterator() {
        return new DescendingIterator();
    }

拷贝克隆函数,一个是父类的克隆函数,另一个是重写的克隆函数,这里比较特殊,因为LinkedList是链表,本身只保存了第一个和最后一个的引用,所以拷贝的时候需要向里面添加元素的方式进行拷贝。

    public Object clone() {
        LinkedList<E> clone = superClone();

        // Put clone into "virgin" state
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;

        // 添加元素到拷贝的队列中
        for (Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);

        return clone;
    }
    private LinkedList<E> superClone() {
        try {
            return (LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

转换成为数组,通过循环实现

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

转换成为指定类型的数组,和前面不同的是,这里初始化的时候使用类型反射创建(T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size)

    public <T> T[] toArray(T[] a) {
        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)
            a[size] = null;

        return a;
    }

获取可分割迭代器:

    public Spliterator<E> spliterator() {
        return new LLSpliterator<E>(this, -1, 0);
    }

7.迭代器

里面定义了三种迭代器,都是以内部类的方式实现,分别是:

  • ListItr:列表的经典迭代器
  • DescendingIterator:倒序迭代器
  • LLSpliterator:可分割迭代器

7.1 ListItr

先来说说ListItr,这个迭代器主要是有next(),hashNext(),hasPrevious(),previous(),nextIndex(),previousIndex(),remove(),set(),add(),forEachRemaining()方法:

  • next():获取下一个元素
  • hashNext():是否有下一个元素
  • hasPrevious():是否有上一个元素
  • previous():上一个元素
  • nextIndex():下一个索引位置
  • previousIndex():上一个索引位置
  • remove():删除当前索引位置的元素
  • set():更新元素
  • add():新增元素
  • forEachRemaining():遍历剩下的元素

里面主要有集合重要的属性:

  • lastReturned:上一次返回的元素
  • next:下一个返回的元素
  • nextIndex:下一个索引
  • expectedModCount:期待修改的次数
    private class ListItr implements ListIterator<E> {
      	// 上一个返回的元素
        private Node<E> lastReturned;
      	// 下一个元素
        private Node<E> next;
      	// 下一个索引
        private int nextIndex;
      	// 期待的修改次数
        private int expectedModCount = modCount;
      	
      	// 初始化
        ListItr(int index) {
            // 根据索引位置更新下一个返回的节点
            next = (index == size) ? null : node(index);
          	// 更新索引
            nextIndex = index;
        }
      	// 是否有下一个元素:索引是否小于size
        public boolean hasNext() {
            return nextIndex < size;
        }
      	// 获取下一个元素
        public E next() {
          	// 检查修改合法化
            checkForComodification();
          	// 如果没有下一个元素会抛异常,所以使用前需要先判断
            if (!hasNext())
                throw new NoSuchElementException();
          	// 上一次返回的元素更新
            lastReturned = next;
          	// 更新下一次返回的元素
            next = next.next;
          	// 更新索引
            nextIndex++;
          	// 返回item
            return lastReturned.item;
        }
      
      	// 是否有上一个:下一个返回的元素索引是不是大于0
        public boolean hasPrevious() {
            return nextIndex > 0;
        }
      	// 返回上一个元素
        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
              	// 否则就是在next索引处添加元素
                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();
        }
    }

上面的迭代器没有什么好说的,就是往前面和后面遍历的功能,以及增删改的功能。

7.2 DescendingIterator

这个迭代器有点意思,也很简单,就是一个倒序的功能,功能实现也十分简单:

  • hasNext:是否有下一个元素,实际上是判断上一个元素
  • next:获取下一个元素,实际上是获取前面一个元素
  • remove:移除元素

倒序就是别人从前往后,它偏偏从后往前遍历,emmmmmmm

    private class DescendingIterator implements Iterator<E> {
        private final ListItr itr = new ListItr(size());
        public boolean hasNext() {
            return itr.hasPrevious();
        }
        public E next() {
            return itr.previous();
        }
        public void remove() {
            itr.remove();
        }
    }

7.3 LLSpliterator

这个迭代器有点东西,感觉和其它的不太一样,LLSpliterator是在使用node的next进行迭代,下面分析一下:主要是为了将元素分为多份,然后再用多线程来处理。

值得注意的是:分割的时候,LinkedList不是1/2分割,而是每一次分割出来的大小都是递增的,递增的大小是BATCH_UNIT,但是返回的不是LLSpliterator,而是ArraySpliterator,每次都分割出更多的元素,转成数组结构,这也许是出自于性能考虑,比较指针遍历太慢了,我猜的的...别打我

    static final class LLSpliterator<E> implements Spliterator<E> {
      	// 分割长度增加单位
        static final int BATCH_UNIT = 1 << 10;  // batch array size increment
      	// 最大分割长度
        static final int MAX_BATCH = 1 << 25;  // max batch array size;
        final LinkedList<E> list; // null OK unless traversed
      	// 当前节点
        Node<E> current;      // current node; null until initialized
      	// 大小估算
        int est;  
      	// 期待修改的次数
        int expectedModCount; // initialized when est set
      	// 分割长度
        int batch;            // batch size for splits

        LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
            this.list = list;
            this.est = est;
            this.expectedModCount = expectedModCount;
        }

        final int getEst() {
            int s; // force initialization
            final LinkedList<E> lst;
            if ((s = est) < 0) {
                if ((lst = list) == null)
                    s = est = 0;
                else {
                    expectedModCount = lst.modCount;
                    current = lst.first;
                    s = est = lst.size;
                }
            }
            return s;
        }
				// 估算大小
        public long estimateSize() { return (long) getEst(); }

      	// 分割
        public Spliterator<E> trySplit() {
            Node<E> p;
          	// 获取大小
            int s = getEst();
          	// 当前节点不为空
            if (s > 1 && (p = current) != null) {
              	// 分割位置结束:分割位置+分割单位
                int n = batch + BATCH_UNIT;
              	// 如果大于大小,就限制最后的位置
                if (n > s)
                    n = s;
              	// 最大的分割位置
                if (n > MAX_BATCH)
                    n = MAX_BATCH;
              	// 数组
                Object[] a = new Object[n];
                int j = 0;
              	// 将当前位置到n的位置循环,存放到a数组中
                do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
                current = p;
                batch = j;
                est = s - j;
              	// ArraySpliterator每次分割成一半一半,而IteratorSpliterator算术递增
                return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
            }
            return null;
        }

      	// 对剩下的元素进行处理
        public void forEachRemaining(Consumer<? super E> action) {
            Node<E> p; int n;
            if (action == null) throw new NullPointerException();
            if ((n = getEst()) > 0 && (p = current) != null) {
                current = null;
                est = 0;
                do {
                    E e = p.item;
                    p = p.next;
                    action.accept(e);
                } while (p != null && --n > 0);
            }
            if (list.modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

      	// 对后面一个元素进行处理
        public boolean tryAdvance(Consumer<? super E> action) {
            Node<E> p;
            if (action == null) throw new NullPointerException();
            if (getEst() > 0 && (p = current) != null) {
                --est;
                E e = p.item;
                current = p.next;
                action.accept(e);
                if (list.modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                return true;
            }
            return false;
        }

        public int characteristics() {
            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
        }
    }

8.序列化和反序列化

序列化和反序列化的时候,需要重写,因为我们保存的只有第一个和最后一个节点的引用,我们序列化需要保存大小和引用,所以需要重写,要不反序列化回来就找不到next,节点之间的关系就会丢失。

序列化的时候如下,写入了size,以及遍历的时候将节点的item值写入。

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out size
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (Node<E> x = first; x != null; x = x.next)
            s.writeObject(x.item);
    }

反序列化的时候,读入大小size以及每个节点里面的元素item

    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // 默认序列化
        s.defaultReadObject();

        // 大小
        int size = s.readInt();

        // 按照顺序读入元素
        for (int i = 0; i < size; i++)
            linkLast((E)s.readObject());
    }

9.总结一下

  • LinkedList底层是用链表实现的,而且是双向链表,并且实现了Queue接口,可以当成双向队列或者堆栈来使用。也正是因为是链表实现,所以删除元素比较快,但是查找的时候相对较慢。当然,也没有什么扩容,除非就是内存不够了。

  • 双向链表,可以从头往尾遍历,也可以从尾部往前遍历。

  • LinkedList继承了AbstractSequentialList,AbstractSequentialList实现了get,set,add,remove等方法。

  • 序列化/反序列化的时候重写了方法,才能达到序列化里面每一个节点元素的效果。

  • 线程不安全

【作者简介】:
秦怀,公众号【秦怀杂货店】作者,技术之路不在一时,山高水长,纵使缓慢,驰而不息。这个世界希望一切都很快,更快,但是我希望自己能走好每一步,写好每一篇文章,期待和你们一起交流。

此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者核实删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~

  • 本文作者: 秦怀杂货店
  • 本文链接: http://aphysia.cn/archives/linkedlist
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 随便聊聊 # 数据结构 # 小游戏 # 数据库 # Docker # Springboot # 系统设计 # 雪花算法 # 分布式 # 海量ip # 最长回文子串 # 算法 # 面试题 # 线程池 # 多线程 # 线程 # java学习 # 布隆过滤器 # github # 架构设计 # docsify # Git # JVM # LeetCode # 杂货思考 # 设计模式 # Lambda # native # isAssignableFrom # 反射 # 剑指Offer # mybatis # SPI # JDBC # 编程工具 # Java基础 # 集合
剑指Offer【26】-- 二叉搜索树和双向链表
使用PicGo存储markdown图片(阿里云或者github)
  • 文章目录
  • 站点概览
秦怀杂货店

秦怀杂货店

纵然缓慢,驰而不息。

145 日志
19 分类
37 标签
Github E-mail
Creative Commons
0%
© 2022 秦怀杂货店
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4