一、集合概述

        Java 中的集合分为单列集合和双列集合，单列集合顶级接口为 Collection,双列集合顶级接口为 Map。 Collection 的子接口有两个：List 和 Set。本文先介绍List

1、为什么要有集合

        Array存储数据具有一些弊端：

                ①长度不可变：比如  int[ ]  arr  =  new  int [3];此时数组长度不可变

                ②提供的方法少，不便于增删改查操作

                ③类型受限  ： arr[2] = "String"

2、集合类的体系结构

List 接口的特点：元素可重复，有序(存取顺序)。 list 接口的实现类如下：

        ​ ①ArrayList:底层实现是数组，查询快，增删慢，线程不安全，效率高；

        ​ ②Vector:底层实现是数组，查询快，增删慢，线程安全，效率低；【废弃】

        ​ ③LinkedList:底层实现是链表，增删快，查询慢，线程不安全，效率高；

二、Collection接口

1、概述

        是单例集合的顶层接口，JDK 不提供此接口的任何直接实现，它提供更具体的子接口（如Set和List）实现

2、常用方法

        boolean add（E e）：添加 e

        boolean remove（Object o）：删除o

        int size（）：返回集合中元素的个数

        boolean isEmpty（）：判断集合是否为空

        boolean contains（Object obj）：判断集合中是否包含obj

        Iterator iterator()：返回迭代器对象

3、案例

三、List接口

1、特点：

        它是一个元素存取有序的集合

2、常用方法

        void add(int index,E element)：把元素添加到执行下标的位置，其他元素后移

         E get(int index)：返回指定下标的元素

         E set(int index,E element)：修饰指定下标处的元素

         E remove(int index)：删除指定下标的元素

3、案例

四、ArrayList类

1、概述

        ArrayList是List接口基于变长数组的实现；set和get数据速度快，而add或者remove元素时需要移动数据速度比较慢

2、数据结构

3、案例

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class ListTest {
    public static void main(String[] args) {
        List<String> stringList = new ArrayList<>();
        stringList.add("aaa-1");
        stringList.add("aaa-2");
        stringList.add("aaa-3");
        stringList.add(0,"aaa-4");//其他元素后移

        System.out.println("-------增强for循环遍历-------");
        for (String str : stringList) {
            System.out.println(str);
        }

        //修改
        stringList.set(1,"bbb-2");
        System.out.println("-------for循环遍历-------");
        for (int i = 0; i < stringList.size(); i++) {
            String str = stringList.get(i);
            System.out.println(str);
        }

        for (int i = stringList.size()-1; i >= 0; i--) {
            stringList.remove(i);
        }
        stringList.clear();
        System.out.println("-----迭代器遍历-----");
        Iterator<String> iterator = stringList.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

五、Vector集合

        实现List接口的另一个实现类是Vector(jdk1.2)，是线程安全的ArrayList效率低。如果不需要线程安全，建议使用ArrayList。

六、LinkedList类

1、概述

        LinkedList是List接口基于双向链表的实现；add或者remove速度快，而set或get时需要从头开始索引速度比较慢。

2、数据结构

        LinkedList底层使用双向链表存储，即定义了一个保存数据的value，同时定义Node类型的prev和last，用于记录首末元素。

3、案例

public class Node {
    public Object value;
    public Node next;
    public Node prev;

    public Node(Object value) {
        this.value = value;
    }
}

public class LinkedList {
    public Node head;
    
    public LinkedList() {
		head = new Node(null);
	}
    
    //获得指定位置的节点
	public Node get(int index){
		Node node = head;
		for(int i = 0;i<=index;i++){
			node = node.next;
		}
		return node;
	}
    
    /**
     * 删除节点
     * a  -b-  c
     * node:b
     */
    public void remove(Node node){
        node.prev.next = node.next;//a --> c
        node.next.prev = node.prev;//c -->a
        node.next = null;
        node.prev = null;
    }
}    

public class ListSpeedTest {
    private static Integer N = 50000;
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        System.out.println("arrayList添加" + N + "条时间：" + addList(arrayList));
        System.out.println("linkedList添加" + N + "条时间：" + addList(linkedList));
        System.out.println("arrayList查找" + N + "条时间：" + getList(arrayList));
        System.out.println("linkedList查找" + N + "条时间：" + getList(linkedList));
    }

    private static long addList(List<Integer> list){
        long beginTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            list.add(0,i);//注意每次添加的位置
        }
        Long endTime = System.currentTimeMillis();
        return endTime - beginTime;
    }

    private static long getList(List<Integer> list){
        long beginTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            list.get(i);
        }
        Long endTime = System.currentTimeMillis();
        return endTime - beginTime;
    }
}