提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  IT要闻

当前栏目

集合框架学习（一）：List&&Map

集合 学习 框架
2023-04-18 14:41:00 时间

集合框架

  1. 集合实现了动态保存
  2. 集合提供了方便的操作方法

Collection：单列集合

List 单列集合 有序集合 可重复集合

ArrayList

  1. ArrayList可以加入NULL值，且可加入多个
  2. ArrayList是数组实现存储的
  3. ArrayList是线程不安全的

源码：

  1. ArrayList中维护了一个Object[]类型的elementData
  2. 扩容机制：
    1. 使用无参构造器构造时，初始化长度为0，插入数据后，扩容elementData长度到10，再次扩容时，扩容至原来的1.5倍
    2. 使用有参构造器时，elementData的长度为初始的指定大小，需要扩容时，扩容至elementData长度的1.5倍 
 扩容机制的原因：
 	// 以无参构造ArrayList的扩容为例   	// 调用add方法后，会调用方法：ensureCapacityInternal 	public boolean add(E e) {         ensureCapacityInternal(size + 1);  // Increments modCount!!         elementData[size++] = e;         return true;     } 	// 先调用calculateCapacity再调用ensureExplicitCapacity     private void ensureCapacityInternal(int minCapacity) {         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));     } 	// 在方法中calculateCapacity，判断了初始化的elementData是否为空，若为空则返回大小为DEFAULT_CAPACITY, minCapacity中的最大值，此时minCapacity = 0，而DEFAULT_CAPACITY 默认值为10     private static int calculateCapacity(Object[] elementData, int minCapacity) {         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {             return Math.max(DEFAULT_CAPACITY, minCapacity);         }         return minCapacity;     } 	// 判断最小需要空间是否大于目前空间的长度，若大于则需要扩容，调用grow方法     private void ensureExplicitCapacity(int minCapacity) {         modCount++;          // overflow-conscious code         if (minCapacity - elementData.length > 0)             grow(minCapacity);     } 	// 在grow方法中，首先把elementData的长度赋值给了oldCapacity，再用oldCapacity计算新的空间，此时：oldCapacity = 0；newCapacity = 0+0/2=0，minCapacity = 10；通过if判断得到最后newCapacity = 10，即未初始化长度时，第一次扩容会扩增到长度为10。 	// 注：oldCapacity >> 1 即 oldCapacity/2  	// 所以 newCapacity = oldCapacity + oldCapacity/2  即扩容1.5倍     private void grow(int minCapacity) {         // overflow-conscious code         int oldCapacity = elementData.length;         int newCapacity = oldCapacity + (oldCapacity >> 1);         if (newCapacity - minCapacity < 0)             newCapacity = minCapacity;         if (newCapacity - MAX_ARRAY_SIZE > 0)             newCapacity = hugeCapacity(minCapacity);         // minCapacity is usually close to size, so this is a win:         elementData = Arrays.copyOf(elementData, newCapacity);     } 复制代码

LinkedList

  1. 底层的数据结构是双向链表和双端队列
  2. 可以添加任何元素、可以重复、可以为null
  3. 线程不安全，没有实现同步、互斥

源码：

  1. LinkedList维护了size（元素个数）first（指向首节点）last（指向末节点）
  2. 每个节点（Node对象）维护了prev（指向前一个节点） next（指向下一个节点） item（数据）
  3. 增、删数据的时候是通过改变该节点前后节点的指向关系实现的，不牵扯数组，不扩容，相对效率更高
// add方法调用linkLast
void linkLast(E e) {
    	// 创建一个Node对象l，此时l=last为null
        final Node<E> l = last;
    	// 创建一个Node对象newNode且自定参数，则newNode数据结构为： prev：null item：e next：null
        final Node<E> newNode = new Node<>(l, e, null);
    	// last 指向newNode节点
        last = newNode;
    	// 此时为ture
        if (l == null)
            // first 指向newNode
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
// 此时数据已经插入，总体结构
// 链表：first指向newNode，last指向newNode，size=1
// Node节点：prev：null item：e next：null

相关文章