Java集合（2 :List）

List

原型ArrayList

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

ArrayList构造和添加方法

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集合常用方法

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("西毒"));//通过元素名称删除，返回boolean
        System.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 默认大小0
        return true;
    }
------------------------------------------------
 private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)//ture
            elementData = grow();
        elementData[s] = e;  //存数据
        size = s + 1; //最小需要长度
    }
----------------------------------------------------------
 private Object[] grow() {
        return grow(size + 1);
    }
-----------------------------------------------------
 private Object[] grow(int minCapacity) { //初始传入为size+1  为1
        int oldCapacity = elementData.length; //初始为0
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
       //if条件为初始数组长度>0或者数组不是无参构造构建的
            int newCapacity = ArraysSupport.newLength(oldCapacity, //旧数组的长度
                    minCapacity - oldCapacity, /* minimum growth */  
                    //最小需要长度-旧数组的长度  大于0代表空间不足
                    oldCapacity >> 1           /* preferred growth */);
                   //二进制位右移1位  位旧数组长度/2
            return 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 > 0
          
        int 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; //初始为null
        final Node<E> newNode = new Node<>(l, e, null);
    //参数1：位上一个节点的内存地址,参数2：e为插入的数据,参数3：下一个节点的内存地址
        last = newNode; // 最后节点为新节点
        if (l == null)  //如果newNode的前一个节点为null,则将新节点赋给first
            first = newNode;
        else
            l.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();//将及格转换为线程安全的。