Java学习之ArrayList_java list add 排序乱了

ArrayList集合介绍：

List接口的可调整大小的数组实现。

 

一.ArrayList底层数据结构——数组：

数组：一旦初始化长度就不可以发生改变。

add：

数组的增加元素怎么做？eg：已知数组长度为4，分别是9，5，2，7，如何追加一个元素？

答：创建一个新数组，把原来4个长度的数组元素 一 一 拷贝进来，然后在新数组后面添加一个元素。

delete:

eg：已知数组长度为4，分别是9，5,2,7，如何删除索引1对应的元素？

删除索引1对应元素5，然后让这之后的元素往前移动。变成9,2,7.整个数组长度发生改变，元素位置也发生改变了。

update：

eg:已知数组长度为4，分别是9，5，2，7，如何将索引1元素修改为6？

直接根据索引就能修改。

get:

eg:已知数组长度为4，分别是9，5，2，7，如何获取数组索引1对应的元素？

直接根据索引取出对应元素。

数组优缺点：

1.数组查询快，根据地址和索引直接获取元素。

2.数组增删慢，每次都要创建新数组且移动元素位置。

二.ArrayList继承与实现关系

   4个实现：

（1）实现了Serializable标记接口。

（2）实现了Clonable标记接口。（想要克隆必须实现clonable接口，重写clone方法。克隆出来的对象和原对象地址不等，内容相等）

（3） 实现RandomAccess标记接口。

（4）实现list接口。

  1个继承：

（1）继承AbstractList类。-提供list接口的框架。

三.ArrayList随机访问和顺序访问效率对比。

随机访问效率比顺序访问（迭代器）效率高。（因为ArrayList实现了RandomAccess接口，只有实现了这个接口，才会这样）

public class Demo01 {
	public static void main(String[] args) {
		List<String>list=new ArrayList<>();
		for(int i=0;i<100000;i++)
			list.add(i+"a");
		//测随机访问时间
		//开始t
		long startTime=System.currentTimeMillis();
		for(int i=0;i<100000;i++)
			list.get(i);
		//结束t
		long endTime=System.currentTimeMillis();
		System.out.println(endTime-startTime);
		
		//测顺序访问时间
		startTime=System.currentTimeMillis();
		Iterator<String>it=list.iterator();
		while(it.hasNext())
		{
			it.next();
		}
		endTime=System.currentTimeMillis();
		System.out.println(endTime-startTime);
	}
   //最后输出为1  2
}

三.ArrayList分析 

3.1构造方法

 

//DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空的数组
public ArrayList(){
 this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

 

3.2 添加方法

 

方法一：

public boolean add(E e)
{
   //校验扩容
   ensureCapacityInternal(size+1);
   elementData[size++]=e;
   return true;
}

private void ensureCapacityInternal(int minCapacity){
 ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));
}

private static int calculateCapacity(Object[]elementData,int minCapacity){
 if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
  //默认容量10和前一个方法的size+1取最大值，赋值给最小容量
  minCapaticy=Math.max(DEFAULT_CAPACITY,minCapacity);
  }
 return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity){
  //修改集合的次数++
  modCount++;
  //判断容量够不够，不够就扩容
  if(minCapacity-elementData.length>0)
  grow(minCapacity);
}

private void grow(int minCapacity){
   //将存元素的数组的长度赋给旧容量
   int oldCapacity=elementData.length;
   //新容量为旧容量的1.5倍
   int newCapacity=oldCapacity+(oldCapacity>>1);
   //看新容量-最小容量是不是<0
   if(newCapacity-minCapacity<0)
    newCapacity=minCapacity
   //新值-Integer的最大值是否>0
   if(newCapacity-MAX_ARRAY_SIZE>0)
    newCapacity=hugeCapacity(minCapacity);
   //调用copyOf进行元素的一个拷贝
   elementData=Arrays.copyOf(elementData,newCapacity);
}

private static int hugeCapacity(int minCapacity){
 if(minCapacity<0)
  throw new OutOfMemoryError();
 return (minCapacity>MAX_ARRAY_SIZE)?Integer.MAX_VALUE:MAX_ARRAY_SIZE;
}

方法二：

public void add(int index,E element){
  //检验索引
  rangeCheckForAdd(index);
  //校验扩容，同上一个方法
  ensureCapacityInternal(size+1);
  //指定索引为index,从index+1拷贝，拷贝size-index个
  System.arraycopy(elementData,index,elementData,index+1,size-index);
  elementData[index]=element;
  size++;
}

private void rangeCheckForAdd(int index){
  //检验索引有没有大于数组长度或者小于0
  if(index>size||index<0)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

方法三：

public boolean addAll(Collection<? extends E> c){
  //把集合转成数组
  Object[] a=c.toArray();
  //有数据集合的长度赋给numNew
  int numNew=a.length;
  //size是新集合的长度，numNew是c长度
  ensureCapacityInternal(size+numNew);
  //把a数组元素拷贝到elementData中
  System.arraycopy(a,0,elementData,size,numNew);
  size+=numNew;
  return numNew!=0;
}

方法四：

public boolean addAll(int index,Collection<? extends E> c){
  //检验索引
  rangeCheckForAdd(index);
  //将集合(数据源)转成数组
  Object[] a=c.toArray();
  //记录集合长度
  int numNew=a.length;
  //校验扩容
  ensureCapacityInternal(size+numNew);
  //numMoved代表要移动元素的个数=集合真实长度-索引位置
  int numMoved=size-index;
  //判断是否需要移动元素
  if(numMoved>0)
   //源数组，从哪个位置，移动到目标数组，目标数组起始位置，要复制目标数组个数
   //这一步只是移动，数据源的元素还没有复制
   System.arraycopy(elementData,index,elementData,index+numNew,numMoved);
  //这才是真正将数据源中所有数据添加到数据目的
  System.arraycopy(a,0,elementData,index,numNew);
  size+=numNew;
  return numNew!=0;
}

3.3 修改（set）方法

public E set(int index,E element)：根据索引修改集合元素

public E set(int index,E element){
 //校验索引
 rangeCheck(index);
 //把索引对应元素取出来赋值给oldValue
 E oldValue=elementData(index);
 //把要修改后的值存到数组中
 elementData[index]=element;
 //返回被替换的元素
 return oldValue;
}

private void rangeCheck(int index){
  if(index>=size)
  throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

3.4 获取（get）方法

public E get (int index) :根据索引获取元素

public E get(int index){
 rangeCheck(index);
 return elementData[index];
}

3.5 toString方法

它不是ArrayList的方法，而是AbstractCollection的方法。但是ArrayList继承了AbstractList，AbstractList继承了AbstractCollection

public String toString():把集合所有数据转换成字符串

public String toString(){
  //获取迭代器
  Iterator<E>it=iterator();
  //判断迭代器是否有元素
  if(!it.hasNext())
  return "[]";
  //创建StringBuilder
  StringBuilder sb=new StringBuilder();
  sb.append('[');
  //无限循环
  for(;;){
  //调用迭代器的next方法取出元素，且向下移动
  E e=it.next();
  sb.append(e==this?"(this Collection)" :e);
  //没有元素了，追加]，且把整个缓冲区数据转成字符串，且结束死循环
  if(!it.hasNext())
    return sb.append(']').toString();
  sb.append(',').append(' ');
}

3.6 迭代器

  public Iterator<E> iterator()普通迭代器

用迭代器遍历集合每个元素：

public static void main(String[] args) {
		List<String>list=new ArrayList<>();
		list.add("Hello");
		list.add("every");
		list.add("body!");
		Iterator<String>it=list.iterator();
		while(it.hasNext())
		{
			String s=it.next();
			System.out.println(s);
		}
		
	}

源码：

public Iterator<E>iterator(){
 //创建了一个对象
 return new Itr();
}

 

private class Itr implements Iterator<E>{
 int cursor;//光标，默认值0
 int lastRet=-1;
 //将集合实际修改次数赋给预期修改次数
 int expectedModCount=modCount;
 //判断集合是否有元素
 public boolean hasNext(){
  //判断光标是否不等于size
  return cursor!=size;
  }
 
  public E next(){
   //校验预期修改次数是否和实际修改次数一样
    checkForComodification();
   //光标赋给i
    int i=cursor;
   //判断是否大于集合size，说明没有元素了
    if(i>=size)
     throw new NoSuchElementException();
   //把集合存储数据数组的地址赋值给该方法的局部变量
   Object[] elementData=ArrayList.this.elementData;
   //进行判断，如果条件满足就会产生并发修改异常
   if(i>=elementData.length)
   throw new ConcurrentModificationException();
 //光标向下移动
  cursor=i+1;
 //从数组中取出元素并返回
  return(E)elementData[lastRet=i];
}

通过迭代器遍历查找元素，如果有就删除（删除的是最后一个元素）：

public static void main(String[] args) {
		List<String>list=new ArrayList<>();
		list.add("Hello");
		list.add("my");
		list.add("friend");
		Iterator<String>it=list.iterator();
		while(it.hasNext())
		{
			String s=it.next();
			if(s.equals("friend"))
				list.remove("friend");
		}
	}

会有并发修改异常。

为什么？

add（）完以后modCount++,实际修改次数=3，预期修改次数=3,删除完元素，modCount++,实际修改次数=4，下次再遍历时，(cursor=3)!=(size=2)，因此还会往下执行，调用next方法，然后校验预期修改次数和实际修改次数不一样，就会有异常。

通过迭代器遍历查找元素，如果有就删除（删除的是集合倒数第二个元素）：

结果：成功，没有异常

为什么？

因为hasNext()中光标的值cursor=size的值，不会调用next（），就不会产生并发修改异常。

3.6 1 remove（）

这个方法是个默认方法，jdk得达到1.8

default void remove():删除集合中元素

1.迭代器调用remove方法删除元素，实际上还是调用集合自己的remove方法删除元素

2.调用remove方法每次都给预期修改次数赋值，不会产生并发修改异常

//迭代器自带方法
public void remove(){
 if(lastRet<0)
    throw new IllegalStateException();
 checkForComodification();
 try{
  ArrayList.this.remove(lastRet);
  cursor=lastRet;
  //实际修改次数赋值给预期修改次数
  expectedModCount=modCount;
 }catch(IndexOutOfBoundsException ex){
   throw new ConcurrentModificationException();
 }
}

//集合删除的方法
public E remove(int index){
 //校验索引
 rangeCheck(index);
 //实际修改次数++
 modCount++;
 //取出修改索引的数值赋给oldValue；
 E oldValue=elementData(index);
 //移动元素个数=实际元素个数-索引之前的-这个索引的
 int numMoved=size-index-1;
 if(numMoved>0)
  System.arraycopy(elementData,index+1,elementData,index,numMoved);
 elementData[--size]=null;
 return oldValue;
}

3.7clear（）

public void clear():清空集合所有数据

public void clear(){
 modCount++;
 for(int i=0;i<size;i++)
  elementData[i]=null;
 size=0;
}

3.8 contains（）

public boolean contains(Object o):判断集合是否包含指定元素

public boolean contains(Object o){
  return indexOf(o)>=0;
}

public int indexOf(Object o){
 //判断要找的元素是否为null
 if(o==null){
   //遍历集合
   for(int i=0;i<size;i++)
    if(elementData[i]==null)
        //找到之后返回该元素索引
        return i;
 }else{
   //遍历集合
   for(int i=0;i<size;i++)
    //拿要找的元素和集合元素比较
    if(o.equals(elementData[i]))
       //返回该元素所在集合索引
       return i;
 }
 return -1;
}

3.9 isEmpty（）

public boolean isEmpty():判断集合是否为空

public boolean isEmpty(){
  return size==0;
}

四.面试题

1.ArrayList怎么扩容的？

第一次扩容10，以后每次是原容量的1.5倍

2.ArrayList频繁扩容导致性能急剧下降，怎么办？

指定初始容量，就不用扩容了。

3.ArrayList插入或删除元素一定比LinkedList慢吗？

不一定。 

ArrayList的remove源码：

//集合删除的方法
public E remove(int index){
 //校验索引
 rangeCheck(index);
 //实际修改次数++
 modCount++;
 //取出修改索引的数值赋给oldValue；
 E oldValue=elementData(index);
 //移动元素个数=实际元素个数-索引之前的-这个索引的
 int numMoved=size-index-1;
 if(numMoved>0)
  System.arraycopy(elementData,index+1,elementData,index,numMoved);
 elementData[--size]=null;
 return oldValue;
}

LinkedList的remove源码

public E remove(int index){
 checkElementIndex(index);
 return unlink(node(index));
}

private void checkElementIndex(int index){
 if(!isElementIndex(index))
    throw new IndexOutOfBoundsException();
}

private boolean IsElementIndex(int index){
 return index>=0&&index<size;
}

//找元素的方法
Node<E>node(int index){
 //判断index是否小于集合长度的一半
 if(index<(size>>1)){
   //如果小于就把第一个节点赋给x
   Node<E>x=first;
   //从头往后找,获取下一个节点
   for(int i=0;i<index;i++)
    x=x.next;
   return x;
  }else{
   Node<E>x=last;
   //从后往前找
   for(int i=size-1;i>=0;i--)
    x=x.prev;
  return x;
}

E unlike(Node<E>x){
  //这个节点的值
  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;
   size--;
   modCount++;
   return element;
}

由此看来效率不见得比ArrayList快多少。

4.ArrayList是线程安全的吗？什么时候需要同步？

不是。解决方法：synchronized、Lock或者用vector。

集合不是成员变量时，不需要同步，每一个线程都有一个独立的方法，不是共享数据，就不用加锁。

反之，成员变量是被所有线程共享的，所以需要。

5.如何复制一个ArrayList到另一个ArrayList去？

（1）clone()方法

（2）ArrayList构造方法

（3）addAll（）

6.已知成员变量集合存储N多用户名称，在多线程情况下，用迭代器读取集合数据时如何保证还可以正常写入数据到集合？

有个集合可以让读写分离：CopyOnWriteArrayList

7.ArrayList和LinkedList的区别？

ArrayList：

基于动态数组的数据结构。

对于随机访问get,set，ArrayList优于LinkedList

对于随机操作的add,remove，ArrayList不一定比LinkedList慢（因为ArrayList底层是基于动态数组，因此不用每次add和remove的时候都需要创建新数组）

LinkedList：

基于链表的数据结构

对于顺序操作，LinkedList不一定比ArrayList慢

对于随机操作，LinkedList效率明显比较低