Java Collection框架 - ArrayList

Java Collection框架 - ArrayList

基于jdk1.8

简介

ArrayList是基于数组实现的动态数组,不是线程安全

时间复杂度:

  • 查找和修改 ==> O(1)
  • 删除和添加(除了向末尾添加) ==> O(n)

数据结构

先看下ArrayList的数据结构:

ArrayList数据结构

ArrayList的数据结构很简单,就是一个数组跟一个size属性作为尾指针

主要属性与方法列表

//代表ArrayList默认容量 10
DEFAULT_CAPACITY : int
//内部数组
elementData : Object[]
//容量
size : int
//最大容量 Integer.MAX_VALUE - 8
MAX_ARRAY_SIZE : int

trimToSize() : void
ensureCapacity(int) : void
size() : int
isEmpty() : boolean
contains(Object) : boolean
indexOf(Object) : int
lastIndexOf(Object) : int
clone() : Object
toArray() : Object[]
toArray(T[]) : T[]
get(int) : E
set(int, E) : E
add(E) : boolean
add(int, E) : void
remove(int) : E
remove(Object) : boolean
clear() : void
addAll(Collection<? extends E>) : boolean
addAll(int, Collection<? extends E>) : boolean
removeAll(Collection<?>) : boolean
retainAll(Collection<?>) : boolean
listIterator(int) : ListIterator<E>
listIterator() : ListIterator<E>
subList(int, int) : List<E>
sort(Comparator<? super E>) : void

主要代码分析

  1. 查找

ArrayList提供了get(int index)用于读取数组中的元素。由于ArrayList使用数组实现,所以可以直接使用下标来获取元素

  public E get(int index) {
      rangeCheck(index);

      return elementData(index);
  }

  E elementData(int index) {
      return (E) elementData[index];
  }
  1. 增加

ArrayList提供了add(E e)add(int index, E element)addAll(Collection<? extends E> c)addAll(int index, Collection<? extends E> c)四个方法来添加元素

  • add(E e):将元素添加到ArrayList末尾

      public boolean add(E e) {
          ensureCapacityInternal(size + 1);  // Increments modCount!!
          elementData[size++] = e;
          return true;
      }
    

    这里的ensureCapacityInternal()方法的作用是尝试对数组进行扩容

  • add(int index, E element):将元素添加至指定位置,并将之后的元素向后移一位

      public void add(int index, E element) {
          //判断索引位置是否合法
          rangeCheckForAdd(index);
    
          ensureCapacityInternal(size + 1);  // Increments modCount!!
          //将原数组从index之后的元素,全部向后移动一位
          //其目的是将index位置空出来
          System.arraycopy(elementData, index, elementData, index + 1,
                           size - index);
          elementData[index] = element;
          size++;
      }
    

    这里的rangeCheckForAdd(index)方法的作用是检查index的值是否在0~size之间。ensureCapacityInternal()方法的作用与上面一样,都是尝试对数组进行扩容。System.arraycopy()方法用于将elementDataindex开始的元素复制到elementDataindex+1位置,一共复制size-index个元素,目的是将index位置空出来,方便后来的重新赋值

  • addAll(Collection<? extends E> c):将集合内的所有元素依次添加到ArrayList末尾

      public boolean addAll(Collection<? extends E> c) {
          Object[] a = c.toArray();
          int numNew = a.length;
          ensureCapacityInternal(size + numNew);  // Increments modCount
          //将a数组内的元素添加到内部数组中
          System.arraycopy(a, 0, elementData, size, numNew);
          size += numNew;
          return numNew != 0;
      }
    

    这里的System.arraycopy()方法用于将a数组从0开始的所有元素复制到elementDatasize位置,一共复制numNew个,使用System.arraycopy()方法相比于一个个复制速度更快

  • addAll(int index, Collection<? extends E> c):将集合内所有元素依次添加到指定位置

      public boolean addAll(int index, Collection<? extends E> c) {
          //确定索引位置是否合法
          rangeCheckForAdd(index);
    
          Object[] a = c.toArray();
          int numNew = a.length;
          ensureCapacityInternal(size + numNew);  // Increments modCount
    
          //计算需要后移的元素个数
          int numMoved = size - index;
          //如果大于0,就将指定元素后移
          if (numMoved > 0)
              System.arraycopy(elementData, index, elementData, index + numNew,
                               numMoved);
    
          System.arraycopy(a, 0, elementData, index, numNew);
          size += numNew;
          return numNew != 0;
      }
    

    在这里System.arraycopy()的作用是先将指定元素后移numNew位(如果有必要),然后将a数组中的元素复制到指定位置

  1. 修改

ArrayList提供了set(int index, E element)方法来修改指定位置的元素

  • set(int index, E element):将index位置的元素设置为element

      public E set(int index, E element) {
          rangeCheck(index);
    
          E oldValue = elementData(index);
          elementData[index] = element;
          return oldValue;
      }
    

    add(int index, E element)方法类似,只不过不需要后移元素了

  1. 删除

ArrayList提供了remove(int index)remove(Object o)removeAll(Collection<?> c)retainAll(Collection<?> c)四个方法来删除元素

  • remove(int index):删除指定位置的元素

      public E remove(int index) {
          rangeCheck(index);
    
          modCount++;
          //获取指定位置的元素
          E oldValue = elementData(index);
    
          //计算需要移动的元素个数
          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
    
          return oldValue;
      }
    
  • remove(Object o):删除指定元素

      public boolean remove(Object o) {
          if (o == null) { //删除元素为null的情况
              for (int index = 0; index < size; index++)
                  if (elementData[index] == null) {
                      fastRemove(index);
                      return true;
                  }
          } else { //不为null
              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
      }
    
  • removeAll(Collection<?> c):删除所有集合中包含的元素

      public boolean removeAll(Collection<?> c) {
          Objects.requireNonNull(c);
          return batchRemove(c, false);
      }
    
      private boolean batchRemove(Collection<?> c, boolean complement) {
          final Object[] elementData = this.elementData;
          int r = 0, w = 0;
          boolean modified = false;
          try {
              for (; r < size; r++)
                  //保留元素策略取决于complement参数
                  //用于实现removeAll跟retainAll方法
                  if (c.contains(elementData[r]) == complement)
                      //将保留元素移动到列表头部
                      elementData[w++] = elementData[r];
          } finally {
              // Preserve behavioral compatibility with AbstractCollection,
              // even if c.contains() throws.
    
              //当contains方法抛出异常时,r不会等于size
              if (r != size) {
                  //0~w:需要保留
                  //w~r:需要删除
                  //r~size:不能确定
                  //只删除必定需要删除的元素
                  System.arraycopy(elementData, r,
                                   elementData, w,
                                   size - r);
                  w += size - r;
              }
              if (w != size) {
                  // clear to let GC do its work
                  for (int i = w; i < size; i++)
                      elementData[i] = null;
                  modCount += size - w;
                  size = w;
                  modified = true;
              }
          }
          return modified;
      }
    

    removeAll()方法依赖于batchRemove()方法,通过complement属性指定需要删除的元素为c集合包含的元素

  • retainAll(Collection<?> c):删除所有集合中不包含的元素

      public boolean retainAll(Collection<?> c) {
          Objects.requireNonNull(c);
          return batchRemove(c, true);
      }
    

    removeAll()方法类似,通过complement属性指定需要删除的元素为c集合不包含的元素

  1. 扩增

ArrayList提供了ensureCapacity(int minCapacity)ensureCapacityInternal(int minCapacity)两个方法供其他方法调用,用于扩增容量。这两个方法都依赖ensureExplicitCapacity(int minCapacity)方法,ensureExplicitCapacity(int minCapacity)方法又依赖grow(int minCapacity)方法

  public void ensureCapacity(int minCapacity) {
      int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
          // any size if not default element table
          ? 0
          // larger than default for default empty table. It's already
          // supposed to be at default size.
          : DEFAULT_CAPACITY;

      if (minCapacity > minExpand) {
          ensureExplicitCapacity(minCapacity);
      }
  }

  private void ensureCapacityInternal(int minCapacity) {
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }

      ensureExplicitCapacity(minCapacity);
  }

  private void ensureExplicitCapacity(int minCapacity) {
      modCount++;

      // overflow-conscious code
      if (minCapacity - elementData.length > 0)
          grow(minCapacity);
  }

  private void grow(int minCapacity) {
      // overflow-conscious code
      int oldCapacity = elementData.length;
      //计算新的数组容量,以1.5倍扩容
      //1.5倍是通过测试得到的一个最佳值
      //以1.5倍扩容。既不会消耗太多性能,也不会消耗太多内存
      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);
  }
  1. 迭代器

ArrayList实现了ItrListItr两个迭代器。ArrayList的迭代器能在遍历的同时添加或删除元素,是由于在这两个方法中修改了迭代器的expectedModCount记录

  public void remove() {
      if (lastRet < 0)
          throw new IllegalStateException();
      checkForComodification();

      try {
          ArrayList.this.remove(lastRet);
          cursor = lastRet;
          lastRet = -1;
          //修改记录
          expectedModCount = modCount;
      } catch (IndexOutOfBoundsException ex) {
          throw new ConcurrentModificationException();
      }
  }

  public void add(E e) {
      checkForComodification();

      try {
          int i = cursor;
          ArrayList.this.add(i, e);
          cursor = i + 1;
          lastRet = -1;
          //修改记录
          expectedModCount = modCount;
      } catch (IndexOutOfBoundsException ex) {
          throw new ConcurrentModificationException();
      }
  }

总结

  1. ArrayList的默认初始容量为10
  2. ArrayList以1.5倍扩容
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,456评论 5 477
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,370评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,337评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,583评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,596评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,572评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,936评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,595评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,850评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,601评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,685评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,371评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,951评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,934评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,167评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 43,636评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,411评论 2 342

推荐阅读更多精彩内容