AI 助理
备案控制台
开发者社区 云原生 文章 正文

Collection 集合源码剖析（下）

2023-08-09 55
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： Collection 集合源码剖析（下）

LinkedList源码剖析


LinkedList res = new LinkedList<>();


LinkedList同时实现了List接口和Deque接口，所以说我们既可以将其视为一个容器，又可以将其视为一个队列乃至栈


LinkedList底层通过双向链表实现


LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候first和last都指向null。


LinkedList它的内部定义了一个私有的Node链表


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


三个构造器


transient是Java语言的关键字，用来表示一个成员变量不是该对象序列化的一部分


public LinkedList() {
}
/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}
/**
 * Links e as first element.
 */
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++;
}
/**
 * Links e as last element.
 */
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++;
}

getFirst() 获取第一个元素


只要对LinkedList一设置值，那么last 和first就会被赋值


/**
    * Returns the first element in this list.
    *
    * @return the first element in this list
    * @throws NoSuchElementException if this list is empty
    */
   public E getFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return f.item;
   }

getLast() 获取最后一个元素:


/**
   * Returns the last element in this list.
   *
   * @return the last element in this list
   * @throws NoSuchElementException if this list is empty
   */
  public E getLast() {
      final Node<E> l = last;
      if (l == null)
          throw new NoSuchElementException();
      return l.item;
  }

删除元素（如下）


removeFirst(), removeLast(), remove(e), remove(index)



从源码中我们可以得出,如果需要删除某个节点，那么就将这个节点传入，或者传入该节点的索引


public boolean remove(Object o) {
       if (o == 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;
   }
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; // GC
       size--;
       modCount++;
       return element;
   }


对于removeFirst 和 removeLast


public E removeFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return unlinkFirst(f);
   }
   /**
    * Unlinks non-null first node f.
    */
   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;
   }


public E removeLast() {
       final Node<E> l = last;
       if (l == null)
           throw new NoSuchElementException();
       return unlinkLast(l);
   }
   /**
    * Unlinks non-null last node l.
    */
   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;
   }


add方法


对于Add方法，官网给出了两类添加的方法，一种是直接添加到链表的末尾。还有一种是插入链表。


public boolean add(E e) {
       linkLast(e);
       return true;
   }
   /**
    * Links e as last element.
    */
   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++;
   }


public void add(int index, E element) {
    //先检查索引位置是否越界
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
  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++;
    }


addAll()


同样，addAll也是有两种构造器，第一个是将另一个集合全部添加到链表的末尾，另一个是将另一个集合添加到指定的位置


public boolean addAll(Collection<? extends E> c) {
       return addAll(size, c);
   }
   /**
    * Inserts all of the elements in the specified collection into this
    * list, starting at the specified position.  Shifts the element
    * currently at that position (if any) and any subsequent elements to
    * the right (increases their indices).  The new elements will appear
    * in the list in the order that they are returned by the
    * specified collection's iterator.
    *
    * @param index index at which to insert the first element
    *              from the specified collection
    * @param c collection containing elements to be added to this list
    * @return {@code true} if this list changed as a result of the call
    * @throws IndexOutOfBoundsException {@inheritDoc}
    * @throws NullPointerException if the specified collection is null
    */
   public boolean addAll(int index, Collection<? extends E> c) {
       checkPositionIndex(index);
       Object[] a = c.toArray();
       int numNew = a.length;
       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;
           Node<E> newNode = new Node<>(pred, e, null);
           if (pred == null)
               first = newNode;
           else
               pred.next = newNode;
           pred = newNode;
       }
       if (succ == null) {
           last = pred;
       } else {
           pred.next = succ;
           succ.prev = pred;
       }
       size += numNew;
       modCount++;
       return true;
   }


Set方法


对于set方法，就像源码中提及的那样，如果判断索引位置数组下标没有越界，那么就直接赋值即可


/**
  * Replaces the element at the specified position in this list with the
  * specified element.
  *
  * @param index index of the element to replace
  * @param element element to be stored at the specified position
  * @return the element previously at the specified position
  * @throws IndexOutOfBoundsException {@inheritDoc}
  */
 public E set(int index, E element) {
     checkElementIndex(index);
     Node<E> x = node(index);
     E oldVal = x.item;
     x.item = element;
     return oldVal;
 }


get方法


获取数据索引位置数据，检查是否越界。如果没有，然后返回即可


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


Clear()


/**
 * Removes all of the elements from this list.
 * The list will be empty after this call returns.
 */
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;
    }
    first = last = null;
    size = 0;
    modCount++;
}


查看元素（indexOf / lastIndexOf）


和ArrayList集合一样，indexOf作用就是为了返回元素首次出现的位置


而lastIndexOf就是返回元素最后出现的位置


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;
}
/**
 * Returns the index of the last occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the highest index {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * @param o element to search for
 * @return the index of the last occurrence of the specified element in
 *         this list, or -1 if this list does not contain the element
 */
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}
Queue<Integer> queue = new LinkedList<>();

使用接口 对象名 = new 类名; 方式实例化的对象只能调用接口中有的方法，而不能调用类中特有的方法。


而使用类名 对象名 = new 类名;方式创建出来的对象可以调用所有的方法


对于LinkedList() 它同样可以实现队列


方法有


  • peek() —– 返回队列的头部
  • element() —–返回队列的头部【 此方法与 peek 的不同之处仅在于，如果此队列为空，它会抛出异常。】
  • poll() ——出列
  • offer() —– 入列【使用容量受限队列时，此方法通常更可取， add后者只能通过引发异常来插入元素。】
  • add() ——入列
  • remove() —– 删除队列的头部


public E peek() { 
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
/**
 * Retrieves, but does not remove, the head (first element) of this list.
 *
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 检索但不删除此队列的头部。 此方法与 peek 的不同之处仅在于，如果此队列为空，它会抛出异常。
 */
public E element() {
    return getFirst();
}
/**
 * Retrieves and removes the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
/**
 * Retrieves and removes the head (first element) of this list.
 *
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 检索并删除此队列的头部，如果此队列为空，则返回 null 。
返回值:
此队列的头部，或者 null 如果此队列为空
 */
public E remove() {
    return removeFirst();
}
/**
 * Adds the specified element as the tail (last element) of this list.
 *
 * @param e the element to add
 * @return {@code true} (as specified by {@link Queue#offer})
 * @since 1.5
 */
public boolean offer(E e) {
    return add(e);
}


Deque双端队列


它在queue的基础上又增加了特殊情况，也就是返回值


此接口定义访问双端元素的方法。提供了插入、删除和检查元素的方法。这些方法中的每一个都以两种形式存在：一种在操作失败时引发异常，另一种返回特殊值（ null 或 false，具体取决于操作）。后一种形式的插入操作专门设计用于容量受限 Deque 的实现;在大多数实现中，插入操作不会失败。


详见源码


/**
    * Inserts the specified element at the front of this list.
    *
    * @param e the element to insert
    * @return {@code true} (as specified by {@link Deque#offerFirst})
    * @since 1.6
    */
   public boolean offerFirst(E e) {
       addFirst(e);
       return true;
   }
   /**
    * Inserts the specified element at the end of this list.
    *
    * @param e the element to insert
    * @return {@code true} (as specified by {@link Deque#offerLast})
    * @since 1.6
    */
   public boolean offerLast(E e) {
       addLast(e);
       return true;
   }
   /**
    * Retrieves, but does not remove, the first element of this list,
    * or returns {@code null} if this list is empty.
    *
    * @return the first element of this list, or {@code null}
    *         if this list is empty
    * @since 1.6
    */
   public E peekFirst() {
       final Node<E> f = first;
       return (f == null) ? null : f.item;
    }
   /**
    * Retrieves, but does not remove, the last element of this list,
    * or returns {@code null} if this list is empty.
    *
    * @return the last element of this list, or {@code null}
    *         if this list is empty
    * @since 1.6
    */
   public E peekLast() {
       final Node<E> l = last;
       return (l == null) ? null : l.item;
   }
   /**
    * Retrieves and removes the first element of this list,
    * or returns {@code null} if this list is empty.
    *
    * @return the first element of this list, or {@code null} if
    *     this list is empty
    * @since 1.6
    */
   public E pollFirst() {
       final Node<E> f = first;
       return (f == null) ? null : unlinkFirst(f);
   }
   /**
    * Retrieves and removes the last element of this list,
    * or returns {@code null} if this list is empty.
    *
    * @return the last element of this list, or {@code null} if
    *     this list is empty
    * @since 1.6
    */
   public E pollLast() {
       final Node<E> l = last;
       return (l == null) ? null : unlinkLast(l);
   }
   /**
    * Pushes an element onto the stack represented by this list.  In other
    * words, inserts the element at the front of this list.
    *
    * <p>This method is equivalent to {@link #addFirst}.
    *
    * @param e the element to push
    * @since 1.6
    */
   public void push(E e) {
       addFirst(e);
   }
   /**
    * Pops an element from the stack represented by this list.  In other
    * words, removes and returns the first element of this list.
    *
    * <p>This method is equivalent to {@link #removeFirst()}.
    *
    * @return the element at the front of this list (which is the top
    *         of the stack represented by this list)
    * @throws NoSuchElementException if this list is empty
    * @since 1.6
    */
   public E pop() {
       return removeFirst();
   }
   /**
    * Removes the first occurrence of the specified element in this
    * list (when traversing the list from head to tail).  If the list
    * does not contain the element, it is unchanged.
    *
    * @param o element to be removed from this list, if present
    * @return {@code true} if the list contained the specified element
    * @since 1.6
    */
   public boolean removeFirstOccurrence(Object o) {
       return remove(o);
   }
   /**
    * Removes the last occurrence of the specified element in this
    * list (when traversing the list from head to tail).  If the list
    * does not contain the element, it is unchanged.
    *
    * @param o element to be removed from this list, if present
    * @return {@code true} if the list contained the specified element
    * @since 1.6
    */
   public boolean removeLastOccurrence(Object o) {
       if (o == null) {
           for (Node<E> x = last; x != null; x = x.prev) {
               if (x.item == null) {
                   unlink(x);
                   return true;
               }
           }
       } else {
           for (Node<E> x = last; x != null; x = x.prev) {
               if (o.equals(x.item)) {
                   unlink(x);
                   return true;
               }
           }
       }
       return false;


参考来源: https://pdai.tech/md/java/collection/java-collection-Queue&Stack.html


文章标签：
Java
容器
索引
Rayce.
目录
相关文章
爱敲代码的小黄
|
9月前
|
算法 安全 索引
【面试小知识】Collection（接口）集合
【面试小知识】Collection（接口）集合
爱敲代码的小黄
60 0
lingeringfear
|
Java
java集合框架Set子接口之HashSet源码剖析
HashSet类实现了由哈希表（实际上是HashMap实例）支持的Set接口 , 底层采用HashMap来保存的数据 , 存在HashSet中的元素是无序且不重复的并且HashSet是线程不安全的 , 这种不重复其实是由HashMap实现的 , 所以HashSet的实现也是相对比较简单的 , 对于它的操作其实都是调用HashMap的方法来实现的
lingeringfear
75 2
智商低情商凑
|
8月前
(Collection)集合遍历,进阶
(Collection)集合遍历,进阶
智商低情商凑
60 4
京墨.
|
9月前
|
存储 Java 索引
集合进阶Collection集合
这篇文档介绍了Java中的Collection集合和其子类List与Set的基本概念和特性。
京墨.
79 3
赵广陆
|
存储 Java
Java集合Collection
Java集合Collection
赵广陆
74 0
Rayce.
|
索引
Collection 集合源码剖析（上）
Collection 集合源码剖析（上）
Rayce.
57 0
邱节
|
Java
Java集合-Collection
Java集合-Collection
邱节
152 1
Java集合-Collection
黑洞晓威
|
存储 Java
Java集合Collection类
数组在存储多个数据方面的缺点： 一旦初始化后，其长度就确定了 数组中提供的方法非常有限，对于添加、删除、插入数据等操作非常不便，同时效率不高。 获取数组中实际元素个数的需求，数组没有现成的属性或方法可用。 数组存储数据的特点：有序、可重复。对于无序、不可重复的需求不能满足。
黑洞晓威
95 0
洲的学习日记
|
安全 Java 容器
Java集合学习1：Collection集合、List（二）
概念：对象的容器，定义了对多个对象进行操作的常用方法。可以实现数组的功能。
洲的学习日记
134 0
Java集合学习1：Collection集合、List（二）
洲的学习日记
|
存储 Java API
Java集合学习1：Collection集合、List（一）
概念：对象的容器，定义了对多个对象进行操作的常用方法。可以实现数组的功能。
洲的学习日记
133 0
Java集合学习1：Collection集合、List（一）

热门文章

最新文章

  • 1
    解决kafka集群由于默认的__consumer_offsets这个topic的默认的副本数为1而存在的单点故障问题
  • 2
    oracle 11g 11204补丁信息
  • 3
    Python 命令行之旅：初探 docopt
  • 4
    时间之箭源于量子纠缠？
  • 5
    输入输出流体系图
  • 6
    Windows Server 2008 R2下部署OCS 2007 R2 边缘服务器
  • 7
    从码农到设计者，从单例模式入手设计代码
  • 8
    瑞典力推储能助太阳能发电计划落实
  • 9
    十张图告诉你互联网发展的八大趋势
  • 10
    第7周-任务3-复数模板类
  • 1
    DeepSeek——DeepSeek模型部署实战
    130
  • 2
    基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
    105
  • 3
    基于电导增量MPPT控制算法的光伏发电系统simulink建模与仿真
    29
  • 4
    基于排队理论的客户结账等待时间MATLAB模拟仿真
    44
  • 5
    3天功能开发→3小时：通义灵码2.0+DEEPSEEK实测报告，单元测试生成准确率92%的秘密
    64
  • 6
    Sentinel监测到了服务，但是实时监控不显示曲线图，应该怎么解决这个问题？
    47
  • 7
    通义灵码 2.0 体验报告：AI 赋能智能研发的新范式
    61
  • 8
    通义灵码 2.0 体验报告：AI 赋能智能研发的新范式
    80
  • 9
    类和对象的简述（c++篇）
    48
  • 10
    模拟实现c++中的vector模版
    38

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    PAI Model Gallery 支持云上一键部署 DeepSeek-V3、DeepSeek-R1 系列模型