[游戏开发]ArrayListVectorLinkedList

ArrayList

特点

• 有序
• 线程不安全(没有加入锁机制)
• 默认初始容量为10
• 查询元素效率高

数据结构

• 基于数组实现 类型为Object

时间复杂度

O(1): 只需要通过查询一次就能找到元素 get(index)基于下标查询
O(n): 需要从头查询到尾部 例如根据元素值查询 链表
O(log n): 二叉树 红黑树

扩容

原来容量1.5倍
源码:

private void grow(int minCapacity) {
        //获取原来容量
        int oldCapacity = elementData.length;
        //计算新容量 新容量=原容量+原容量÷2 位运算提升代码执行效率
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果新的容量比
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //检查新的容量是否超过容量最大限制(Integer类型最大长度-8=2147483639)
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 扩容操作
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

缩容

源码:

   public boolean remove(Object o) {
       if (o == null) {
           for (int index = 0; index < size; index++)
               if (elementData[index] == null) {
                   fastRemove(index);
                   return true;
               }
       } else {
           for (int index = 0; index < size; index++)
               if (o.equals(elementData[index])) {
                   fastRemove(index);
                   return true;
               }
       }
       return false;
   }
  
   private void fastRemove(int index) {
          modCount++;
          int numMoved = size - index - 1;
          if (numMoved > 0)
              System.arraycopy(elementData, index+1, elementData, index,
                               numMoved);
          elementData[--size] = null; // clear to let GC do its work
   }

modCount

作用:

防止列表遍历时列表大小发生变化,如果在遍历时对该列表进行删除或添加元素到列表则会抛出异常.

	public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

Vector

特点

• 线程安全
• 扩容时为原来容量的2倍
• 默认初始容量为10

LinkedList

特点

• 底层基于链表结构的双向链表
• 新增删除元素效率高