共同学习Java源代码--数据结构--LinkedList类(三)

    xiaoxiao2023-03-24  2

    private void linkFirst(E e) {         final Node<E> f = first;         final Node<E> newNode = new Node<>(null, e, f);         first = newNode;         if (f == null)             last = newNode;         else             f.prev = newNode;         size++;         modCount++;

        }

    这个方法是链接到第一个元素的方法,是私有的也就是只有本类可以调用。

    首先创建一个f节点,赋引用为first变量,修饰符为final也就是引用不可改。

    然后创建一个final的新节点,新节点上一个元素为空,元素内容为参数传入的对象引用,下一个元素为f也就是之前的第一个元素。

    然后判断如果f为空,也就是链表是空的,那么last的引用就变为新节点。如果f不为空,f的上一个节点就是新节点。

    最后size自增,修改次数自增。

    其实这个方法就是将参数作为链表的第一个元素。

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

    这个方法是链接到最后一个元素的方法。

    道理同上,不细说了,就是把参数作为链表最后一个元素。

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

    这个方法就是将一个新元素放在指定元素之前的方法。

    首先获取第二个参数也就是目标元素的上一个元素,并赋引用给变量pred。

    然后创建一个新节点,之前元素为pred,之后元素为目标参数,元素内容为第一个参数e。

    目标参数的上一个元素改成新元素。

    判断如果pred为空也就是目标元素为第一个元素,那么新元素就成为第一个元素,否则pred的下一个元素就是新元素。

    最后链表长度自增,修改次数自增。

        private E unlinkFirst(Node<E> f) {         // assert f == first && f != null;         final E element = f.item;         final Node<E> next = f.next;         f.item = null;         f.next = null; // help GC         first = next;         if (next == null)             last = null;         else             next.prev = null;         size--;         modCount++;         return element;     }

    这个方法是将解除首元素的方法。

    注释的第一行是在判断参数节点是否是链表的首节点以及参数节点是否为空。

    首先先获取参数节点的内容,作为返回值。

    然后获取参数的下一个元素,赋引用给next变量。

    将f节点的内容置空,将f节点的下一个节点置空,这是为了解除强引用,方便虚拟机回收。

    然后首节点就变成了next。

    如果next为空,说明链表为空,那么last也为空。如果next不为空,next的上一个节点就置空。

    然后链表长度自减,修改次数自增。

    最后返回参数节点的内容。

        private E unlinkLast(Node<E> l) {         // assert l == last && l != null;         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             prev.next = null;         size--;         modCount++;         return element;     }

    这个方法是将末尾元素解绑的方法。

    具体过程和上面方法大同小异,不细说了。

        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) {             first = next;         } else {             prev.next = next;             x.prev = null;         }         if (next == null) {             last = prev;         } else {             next.prev = prev;             x.next = null;         }         x.item = null;         size--;         modCount++;         return element;     }

    这个方法是解绑某个中间元素的方法。

    首先获取参数元素的内容作为返回值返回。

    然后分别获取参数元素的前一个和后一个元素,赋引用给变量prev和next。

    如果prev为空也就是参数元素是首元素的话,就把首元素设为next也就是参数元素的下一个。否则参数元素的上一个元素的下一个元素就是next,也就是把参数元素之前和之后相关联,然后将参数元素的上一个元素置空。

    如果next为空也就是参数元素是末尾元素,那么末尾元素就改成prev也就是参数元素的上一个元素。否则下一个元素的上一个元素为prev,也就是把参数元素之后和之前相关联,然后将参数元素的下一个元素置空。

    最后将参数元素的内容置空,链表长度自减,修改次数自增,最后返回参数元素的内容。

    转载请注明原文地址: https://ju.6miu.com/read-1200290.html
    最新回复(0)