devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java8集合之LinkedList_unlinkfirst

作者：繁依Fanyi0 | 2024-06-16 10:35:44

赞

踩

unlinkfirst

参考资料：

《Java集合：LinkedList详解》

《Collection - LinkedList源码解析》

《LinkedList》

写在开头：本文为个人学习笔记，内容比较随意，夹杂个人理解，如有错误，欢迎指正。

目录

一、基础概念

        1、基本属性

        2、构造方法

二、修改

三、查找

        1、node

        2、get

         3、peek

        4、element

四、增加

        1、link

       2、add

     2.1、add

     2.2、addAll

        3、offer

        4、push

五、删除

        1、unlink

     1.1、unlink

     1.2、unlinkFirst

     1.3、unlinkLast

        2、remove

       3、poll

一、基础概念

         LinkedList是基于链表实现的数组，同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(Stack)。

        1、基本属性

        我们可以看到LinkedList每一个节点都会记录本节点信息，以及前后节点的指针，这也表明了其本质是一个双向链表。

  1. // 链表长度
  2. transient int size = 0; 
  3.  
  4. // 链表头节点
  5. transient Node<E> first;    
  6.  
  7. // 链表尾节点
  8. transient Node<E> last; 
  9.  
  10. // Node属性
  11. private static class Node<E> {  
  12.     // 存放的对象
  13.     E item; 
  14.     // 下一个节点
  15.     Node<E> next;   
  16.     // 上一个节点
  17.     Node<E> prev;   
  18.  
  19.     Node(Node<E> prev, E element, Node<E> next) {
  20.         this.item = element;
  21.         this.next = next;
  22.         this.prev = prev;
  23.     }
  24. }

        2、构造方法

        LinkedList提供了2个，一个无参一个有参，无参构造方法不做任何操作，将创建工作延后到add时进行，而有参构造函数是其他集合类型转换而来。

  1. public LinkedList() {
  2. }
  3.  
  4. public LinkedList(Collection<? extends E> c) {
  5.     this();
  6.     addAll(c);
  7. }

二、修改

        修改方法最简单，传入Index和修改后的值element即可

  1.     public E set(int index, E element) {
  2.         checkElementIndex(index);
  3.         // 首先使用node方法先找出index位置的元素并返回
  4.         Node<E> x = node(index);
  5.         // 修改旧元素的值并返回
  6.         E oldVal = x.item;
  7.         x.item = element;
  8.         return oldVal;
  9.     }

三、查找

        1、node

        node方法是查找链表中元素的基本方法，后续几个方法中都会有用到。

        这里在查找前先进行了位置判断，index < (size >> 1)，缩小查找范围为原先的一半。

  1.     Node<E> node(int index) {
  2.         // 这里右移一位然后判断index靠近左侧还是右侧，以此来虽小查找范围
  3.         if (index < (size >> 1)) {
  4.             // 如果是在左半侧，则从first元素开始查找
  5.             Node<E> x = first;
  6.             for (int i = 0; i < index; i++)
  7.                 x = x.next;
  8.             return x;
  9.         } else {
  10.             // 如果是在右半侧，则从last元素开始查找
  11.             Node<E> x = last;
  12.             for (int i = size - 1; i > index; i--)
  13.                 x = x.prev;
  14.             return x;
  15.         }
  16.     }

        2、get

                get方法有三个：       

                get：调用上文中的node方法查找给定下标位置元素并返回

                getFirst：直接返回first位置的元素

                getLast：直接返回last位置的元素                                                                                                                           

  1.     public E get(int index) {
  2.         // 索引下标校验
  3.         checkElementIndex(index);
  4.         // 调用node方法查找并返回结果
  5.         return node(index).item;
  6.     }
  7.  
  8.     public E getFirst() {
  9.         // 直接返回first位置的元素
  10.         final Node<E> f = first;
  11.         if (f == null)
  12.             throw new NoSuchElementException();
  13.         return f.item;
  14.     }
  15.  
  16.     public E getLast() {
  17.         // 直接返回last位置的元素
  18.         final Node<E> l = last;
  19.         if (l == null)
  20.             throw new NoSuchElementException();
  21.         return l.item;
  22.     }

         3、peek

                peek方法有三个：       

                peek：直接返回first位置的元素

                getFirst：直接返回first位置的元素

                getLast：直接返回last位置的元素  

  1.     public E peek() {
  2.         final Node<E> f = first;
  3.         return (f == null) ? null : f.item;
  4.     }
  5.  
  6.     public E peekFirst() {
  7.         final Node<E> f = first;
  8.         return (f == null) ? null : f.item;
  9.      }
  10.  
  11.     public E peekLast() {
  12.         final Node<E> l = last;
  13.         return (l == null) ? null : l.item;
  14.     }

      

        4、element

                直接调用getFirst方法返回first位置的元素

  1.     public E element() {
  2.         return getFirst();
  3.     }

四、增加

                linkBefore：将参数e插入到succ前，调整prev与next节点指向的位置

                linkFirst：头插法，将参数e作为新的first节点插入，原first调整为其next节点

                linkLast：尾插法，直接作为新的last节点接到链表最后

  1.     void linkBefore(E e, Node<E> succ) {
  2.         // 获取succ的prev节点
  3.         final Node<E> pred = succ.prev;
  4.         // 使用prev,e,succ三个值new一个新的节点出来
  5.         final Node<E> newNode = new Node<>(pred, e, succ);
  6.         // 将new出的新节点置为succ的prev节点
  7.         succ.prev = newNode;
  8.         // 如果当前pred节点为空，说明是第一个元素，同时赋值为first节点
  9.         if (pred == null)
  10.             first = newNode;
  11.         else
  12.             pred.next = newNode;
  13.         size++;
  14.         modCount++;
  15.     }
  16.  
  17.    private void linkFirst(E e) {
  18.         final Node<E> f = first;
  19.         final Node<E> newNode = new Node<>(null, e, f);
  20.         first = newNode;
  21.         // 如果当前first节点为空，说明是第一个元素，同时赋值为last节点
  22.         if (f == null)
  23.             last = newNode;
  24.         else
  25.             f.prev = newNode;
  26.         size++;
  27.         modCount++;
  28.     }
  29.  
  30.     void linkLast(E e) {
  31.         // new一个新的节点，接到last节点之后，并修改为新的Last节点
  32.         final Node<E> l = last;
  33.         final Node<E> newNode = new Node<>(l, e, null);
  34.         last = newNode;
  35.         // 如果当前last节点为空，说明是第一个元素，同时赋值为first节点
  36.         if (l == null)
  37.             first = newNode;
  38.         else
  39.             l.next = newNode;
  40.         size++;
  41.         modCount++;
  42.     }

       2、add

                2.1、add

                add(E e)：调用linkLast在链表末尾插入元素

                add(int index,E element)：先找出index所对应的位置

                       1：index为链表末尾

                                调用linkLast在链表末尾插入元素

                       2：index不为链表末尾

                                 调用linkBefore在Index位置前插入元素

                addFirst(E e)：调用linkFirst在链表末尾插入元素

                addLast(E e)：调用linkLast在链表末尾插入元素

  1.     public boolean add(E e) {
  2.         // 调用linkLast方法, 将节点添加到尾部
  3.         linkLast(e);
  4.         return true;
  5.     }
  6.  
  7.     // 在index位置插入节点，节点值为element
  8.     public void add(int index, E element) {
  9.         checkPositionIndex(index);
  10.         // 如果索引为size，即将element插入链表尾部
  11.         if (index == size)
  12.             linkLast(element);
  13.         else
  14.             // 将element插入原index位置节点的前面
  15.             // 即：将element插入index位置，将原index位置节点移到index+1的位置
  16.             linkBefore(element, node(index));
  17.     }
  18.  
  19.     public void addFirst(E e) {
  20.         linkFirst(e);
  21.     }
  22.  
  23.     public void addLast(E e) {
  24.         linkLast(e);
  25.     }

                2.2、addAll

  1.     public boolean addAll(Collection<? extends E> c) {
  2.         return addAll(size, c);
  3.     }
  4.  
  5.     public boolean addAll(int index, Collection<? extends E> c) {
  6.         checkPositionIndex(index);
  7.         
  8.         // 使用toArray方法将集合转为数组
  9.         Object[] a = c.toArray();
  10.         int numNew = a.length;
  11.         if (numNew == 0)
  12.             return false;
  13.  
  14.         Node<E> pred, succ;
  15.         if (index == size) {
  16.             succ = null;
  17.             pred = last;
  18.         } else {
  19.             succ = node(index);
  20.             pred = succ.prev;
  21.         }
  22.  
  23.         // 遍历数组并创建新节点，再加入到原链表中
  24.         for (Object o : a) {
  25.             @SuppressWarnings("unchecked") E e = (E) o;
  26.             Node<E> newNode = new Node<>(pred, e, null);
  27.             if (pred == null)
  28.                 first = newNode;
  29.             else
  30.                 pred.next = newNode;
  31.             pred = newNode;
  32.         }
  33.  
  34.         if (succ == null) {
  35.             last = pred;
  36.         } else {
  37.             pred.next = succ;
  38.             succ.prev = pred;
  39.         }
  40.  
  41.         size += numNew;
  42.         modCount++;
  43.         return true;
  44.     }

        3、offer

                offer：内部调用add(E e)方法

                offerFirst：内部调用addFirst(E e)方法

                offerLast：内部调用addLast(E e)方法

  1.     public boolean offer(E e) {
  2.         return add(e);
  3.     }
  4.  
  5.     public boolean offerFirst(E e) {
  6.         addFirst(e);
  7.         return true;
  8.     }
  9.  
  10.     public boolean offerLast(E e) {
  11.         addLast(e);
  12.         return true;
  13.     }

        4、push

                内部调用addFirst方法实现

  1.     public void push(E e) {
  2.         addFirst(e);
  3.     }

五、删除

  1. E unlink(Node<E> x) {   // 移除链表上的x节点
  2.     // assert x != null;
  3.     final E element = x.item;   // x节点的值
  4.     final Node<E> next = x.next;    // x节点的下一个节点
  5.     final Node<E> prev = x.prev;    // x节点的上一个节点
  6.  
  7.     if (prev == null) { // 如果prev为空，则代表x节点为头结点，则将first指向next即可
  8.         first = next;
  9.     } else {    // 否则，x节点不为头结点，
  10.         prev.next = next;   // 将prev节点的next属性指向x节点的next属性
  11.         x.prev = null;  // 将x的prev属性清空
  12.     }
  13.  
  14.     if (next == null) { // 如果next为空，则代表x节点为尾节点，则将last指向prev即可
  15.         last = prev;
  16.     } else {    // 否则，x节点不为尾节点
  17.         next.prev = prev;   // 将next节点的prev属性指向x节点的prev属性
  18.         x.next = null;  // 将x的next属性清空
  19.     }
  20.  
  21.     x.item = null;  // 将x的值清空，以便垃圾收集器回收x对象
  22.     size--;
  23.     modCount++;
  24.     return element;
  25. }

                1.2、unlinkFirst

                        删除first元素

  1.     private E unlinkFirst(Node<E> f) {
  2.         // assert f == first && f != null;
  3.         final E element = f.item;
  4.         final Node<E> next = f.next;
  5.         f.item = null;
  6.         f.next = null; // help GC
  7.         first = next;
  8.         if (next == null)
  9.             last = null;
  10.         else
  11.             next.prev = null;
  12.         size--;
  13.         modCount++;
  14.         return element;
  15.     }

                1.3、unlinkLast

                        删除last元素

  1.     private E unlinkLast(Node<E> l) {
  2.         // assert l == last && l != null;
  3.         final E element = l.item;
  4.         final Node<E> prev = l.prev;
  5.         l.item = null;
  6.         l.prev = null; // help GC
  7.         last = prev;
  8.         if (prev == null)
  9.             first = null;
  10.         else
  11.             prev.next = null;
  12.         size--;
  13.         modCount++;
  14.         return element;
  15.     }

        2、remove

                remove()：内部调用removeFirst()方法删除first位置元素

                remove(int index)：根据传入的index调用node找出对应的元素，调用unlink进行删除

                remove(Object o)：根据传入的o，遍历链表找到对应的元素，调用unlink删除

                removeFirst()：内部调用unlinkFirst方法删除first位置元素

                removeLast()：内部调用unlinkLast方法删除last位置元素

  1.     public E remove() {
  2.         return removeFirst();
  3.     }
  4.  
  5.     public E remove(int index) {
  6.         checkElementIndex(index);
  7.         return unlink(node(index));
  8.     }
  9.  
  10.     public boolean remove(Object o) {
  11.         if (o == null) {
  12.             for (Node<E> x = first; x != null; x = x.next) {
  13.                 if (x.item == null) {
  14.                     unlink(x);
  15.                     return true;
  16.                 }
  17.             }
  18.         } else {
  19.             for (Node<E> x = first; x != null; x = x.next) {
  20.                 if (o.equals(x.item)) {
  21.                     unlink(x);
  22.                     return true;
  23.                 }
  24.             }
  25.         }
  26.         return false;
  27.     }
  28.  
  29.     public E removeFirst() {
  30.         final Node<E> f = first;
  31.         if (f == null)
  32.             throw new NoSuchElementException();
  33.         return unlinkFirst(f);
  34.     }
  35.  
  36.     public E removeLast() {
  37.         final Node<E> l = last;
  38.         if (l == null)
  39.             throw new NoSuchElementException();
  40.         return unlinkLast(l);
  41.     }

       3、poll

                poll：判断first元素是否为空，不为空则调用unlinkFirst(E e)删除

                pollFirst：判断first元素是否为空，不为空则调用unlinkFirst(E e)删除

                pollLast：判断last元素是否为空，不为空则调用unlinkLast(E e)删除

  1.     public E poll() {
  2.         // 判断first元素是否为空，不为空则调用unlinkFirst(E e)删除
  3.         final Node<E> f = first;
  4.         return (f == null) ? null : unlinkFirst(f);
  5.     }
  6.  
  7.     public E pollFirst() {
  8.         // 判断first元素是否为空，不为空则调用unlinkFirst(E e)删除
  9.         final Node<E> f = first;
  10.         return (f == null) ? null : unlinkFirst(f);
  11.     }
  12.  
  13.     public E pollLast() {
  14.         // 判断last元素是否为空，不为空则调用unlinkLast(E e)删除
  15.         final Node<E> l = last;
  16.         return (l == null) ? null : unlinkLast(l);
  17.     }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/726284
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号