Java集合（2 :List）

List

原型ArrayList

• ArrayList是一个List接口的实现类，底层使用的是一个可以调整大小的数组实现的。
• E>:是一种特殊的数据类型（引用数据类型） – 泛型
• ArrayList 或者 ArrayList 或者 ArrayList

ArrayList构造和添加方法

方法名	说明
public ArrayList()	创建一个空集合
public boolean add(E e)	将指定的参数元素追加到集合的末尾
public void add(int index ,E e)	在集合的指定位置添加指定的元素（插入元素）
public void addAll(E object)	用于将指定集合中所有元素添加到当前集合中

public class ArrayList_01 {public static void main(String[] args) {//创建空集合ArrayList<String> list = new ArrayList<>();//泛型定义为String//采用默认追加的方式添加元素System.out.println(list.add("刘德华"));System.out.println(list.add("张学友"));System.out.println(list.add("郭富城"));System.out.println(list.add("黎明"));//插入的方式添加元素
//        list.add(10,"谭咏麟");//插入元素方法索引值不能大于集合中元素个数
//        list.add(4,"谭咏麟");//表示在集合中最后位置插入元素，与追加相同list.add(1,"谭咏麟");//指定位置插入元素，索引位置之后的元素会自动向后进行移动ArrayList<String> newList = new ArrayList<>();//创建新的集合newList.add("小沈阳");newList.add("宋小宝");newList.add("赵四");newList.add("刘能");//查看集合中的元素System.out.println("原集合内部元素：" + list);System.out.println("新集合内部元素：" + newList);list.addAll(newList); //将新集合全部元素添加到原集合中System.out.println("原集合内部元素：" + list);}
}

ArrayList集合常用方法

方法名	说明
public boolean remove(Object o)	删除指定的元素，成功则返回true
public E remove(int index)	删除指定索引位置的元素，返回被删除的元素
public E set(int index,E e)	修改指定索引位置的元素，返回修改前的元素
public E get(int index)	获取指定索引对应的元素
public int size()	获取结合中元素个数

import java.util.ArrayList;
import java.util.Iterator;public class ArrayList_02 {public static void main(String[] args) {ArrayList<String> list = new ArrayList<>();//追加方式添加元素list.add("东邪");list.add("西毒");list.add("南帝");list.add("北丐");list.add("中神通");//删除System.out.println(list.remove("西毒"));//通过元素名称删除，返回booleanSystem.out.println(list.remove(1));//通过索引删除元素，返回被删除元素名//修改System.out.println(list.set(1,"西毒"));//指定索引位置修改元素，并返回被修改元素System.out.println("原集合中元素有：" + list);//获取方法System.out.println(list.get(1));//通过指定索引位置获取集合元素//获取集合元素个数System.out.println(list.size());//集合的遍历,普通for循环for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + "\t");}System.out.println();//增强版for循环for (String name : list) {System.out.print(name+ "\t");**加粗样式**    }System.out.println();//迭代器Iterator<String> it = list.iterator();//创建迭代器while (it.hasNext()){//判断下一个位置是否有元素System.out.print(it.next() + "\t");  //next方法表示获取下一个位置的元素}System.out.println();//Stream流list.stream().forEach(System.out::println);}
}

ArrayList实现原理

底层代码：
属性：

DEFAULT_CAPACITY = 10 默认长度，初始化容量为10
Object[] EMPTY_ELEMENTDATA = {} //有参构造所创建
Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} //无参构造所创建的
Object[] elementData;底层为Object类型的数组，存储的元素都在此。
int size 实际存放的个数

构造方法 ：

//一个参数的构造
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}
//参数如果大于零，则为创建数组的长度；
//参数如果等于零，EMPTY_ELEMENTDATA；
//参数如果小于0，抛出异常。//无参构造public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA  new对象时默认为0 当添加第一个元素的时候，数组扩容至10

add方法源码：（jdk1.8与之不同，此处为jdk16）

//源码
public boolean add(E e) {modCount++;//操作次数add(e, elementData, size);
//e 操作对象;  elementData 底层操作的数组;size 默认大小0return true;}
------------------------------------------------private void add(E e, Object[] elementData, int s) {if (s == elementData.length)//tureelementData = grow();elementData[s] = e;  //存数据size = s + 1; //最小需要长度}
----------------------------------------------------------private Object[] grow() {return grow(size + 1);}
-----------------------------------------------------private Object[] grow(int minCapacity) { //初始传入为size+1  为1int oldCapacity = elementData.length; //初始为0if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//if条件为初始数组长度>0或者数组不是无参构造构建的int newCapacity = ArraysSupport.newLength(oldCapacity, //旧数组的长度minCapacity - oldCapacity, /* minimum growth */  //最小需要长度-旧数组的长度  大于0代表空间不足oldCapacity >> 1           /* preferred growth */);//二进制位右移1位  位旧数组长度/2return elementData = Arrays.copyOf(elementData, newCapacity);将数据放入新数组中} else {return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];//数组长度  DEFAULT_CAPACITY为10  此处代表无参构造默认长度为10}}
----------------------------------------------------public static int newLength(int oldLength, int minGrowth, int prefGrowth) {// assert oldLength >= 0// assert minGrowth > 0int newLength = Math.max(minGrowth, prefGrowth) + oldLength;//如果prefGrowth>minGrowth  扩容1.5倍    minGrowth>prefGrowth为需要多少给多少if (newLength - MAX_ARRAY_LENGTH <= 0) {//MAX_ARRAY_LENGTH为int最大值   表示新数组长度如果小于int的最大值return newLength;}return hugeLength(oldLength, minGrowth);//返回int最大值}

ArrayList集合底层是数组，怎么优化？
尽可能少的扩容。因为数组扩容效率比较低，建议在使用ArrayList集合 的时候预估计元素的个数，给定一个初始化容量。
数组优点：
检索效率比较高。（每个元素占用空间大小相同，内存地址是连续的，知道首元素内存地址，
然后知道下标，通过数学表达式计算出元素的内存地址，所以检索效率最高。）
数组缺点：
随机增删元素效率比较低。
另外数组无法存储大数据量。（很难找到一块非常巨大的连续的内存空间。）
向数组末尾添加元素，效率很高，不受影响。

LinkedList实现原理

底层代码：
属性：

    transient int size = 0;//初始长度transient Node<E> first;//头节点transient Node<E> last;//尾节点

add方法源码：（jdk1.8与之不同，此处为jdk16）

public boolean add(E e) {linkLast(e);return true;}
--------------------------------------
void linkLast(E e) {final Node<E> l = last; //初始为nullfinal Node<E> newNode = new Node<>(l, e, null);//参数1：位上一个节点的内存地址,参数2：e为插入的数据,参数3：下一个节点的内存地址last = newNode; // 最后节点为新节点if (l == null)  //如果newNode的前一个节点为null,则将新节点赋给firstfirst = newNode;elsel.next = newNode;  //尾节点下一个节点为新节点size++;//大小modCount++;//操作数}

LinkedList和ArrayList

LinkedList和ArrayList方法一样，只是底层实现不一样。ArrayList底层为数组存储，LinkedList是以双向链表存储。LinkedList集合没有初始化容量。最初这个链表中没有任何元素。first和last引用都是null。
链表的优点：
由于链表上的元素在空间存储上内存地址不连续。
所以随机增删元素的时候不会有大量元素位移，因此随机增删效率较高。
在以后的开发中，如果遇到随机增删集合中元素的业务比较多时，建议
使用LinkedList。
链表的缺点：
不能通过数学表达式计算被查找元素的内存地址，每一次查找都是从头
节点开始遍历，直到找到为止。所以LinkedList集合检索/查找的效率
较低。
ArrayList：把检索发挥到极致。（末尾添加元素效率还是很高的。）
LinkedList：把随机增删发挥到极致。
加元素都是往末尾添加，所以ArrayList用的比LinkedList多。

Vector

1、底层也是一个数组。
2、初始化容量：10
3、怎么扩容的？
扩容之后是原容量的2倍。
10–> 20 --> 40 --> 80
4、Vector中所有的方法都是线程同步的，都带有synchronized关键字，
是线程安全的。效率比较低，使用较少了。
5、怎么将一个线程不安全的ArrayList集合转换成线程安全的呢？
使用集合工具类：
java.util.Collections;
java.util.Collection 是集合接口。
java.util.Collections 是集合工具类。
Collections.synchronizedList();//将及格转换为线程安全的。