Java~数据结构（二）~List集合（ArrayList、LinkedList详细介绍、常用的方法有哪些）

List

Java中的集合有Collection和Map两个体系。其中Collection接口有三个常用的子接口：List(列表)、Set（集）、Queue（队列）。

• List集合有两个主要的实现类：ArrayList、LinkedList。
• 其中ArrayList低层通过数组实现，随着元素的增加而动态扩容。而LinkedList低层通过链表来实现，随着元素的增加不断向链表的后端来增加节点。
• 下面分别详细介绍

ArrayList

ArrayList是Java集合框架中最常使用的一个类，但是线程不安全。
它继承于AbstractList，实现了List，RandomAccess，Cloneable，Serializaable四个接口。

实现了每个接口获得的功能如下：

• 实现了List，获得了List集合框架的基础功能。
• 实现RandomAccess，获得了快速随机访问存储元素的功能。RandomAccess是一个标记接口，没有任何方法。
• 实现了Cloneable，得到了clone（）方法，可是实现克隆。
• 实现了Serializable，表示可以被序列化，进行序列化传输。

ArrayList本身具有以下特点：

• 长度不固定，可以随着存储元素的增加而动态扩容。（阈值几乎不会达到。）
• 集合有序，顺序就是元素插入的顺序
• 插入的元素可以为null
• 改查效率高（相对于LinkedList来说）
• 线程不安全
• 结构如下：（JDK1.7中）
  

LinkedList

LinkedList用双向链表来实现，每一个节点都有指向前后节点的引用。

它继承了AbstractSequentialList，实现了List，Deque，Cloneable，Serializable接口。

实现每个接口后的功能：

• LinkedList实现了List，得到了List集合框架的基础功能。
• 实现了Deque，Deque是一个双向队列，既可以先入先出，也可先入后出。简单理解就是，LinkedList既可以在头部添加元素，也可以在尾部添加元素。
• 实现Cloneable，可以克隆。
• 实现了Serializable，表示可以被序列化，通过序列化进行传输。
• 结构如下：
  

List常用方法

ArrayList基本操作

public static void main(String[] args) {
        List<String> list=new ArrayList<>();
        System.out.println(list.size());//集合的大小 0
        //集合的大小
        list.add("A");
        list.add("A");
        list.add(0,"B");
        System.out.println(list.size());//集合大小 3
        for(String x:list){
            System.out.print(x+" ");
        }  //B A A
        System.out.println(list.isEmpty());//判断集合是否为空
        System.out.println(list.contains("B"));//判断集合中是否包含B
        //修改
        list.set(0,"C");//list中下标为0的元素修改为C
        list.set(1,"D");//list中下标为1的元素修改为D
        System.out.println(list.toString());//以字符串形式输出 C D A
        //获取
        String element=list.get(0);
        System.out.println(element);//D
        //转为数组
        String[] strArray=list.toArray(new String[]{});
        //删除功能
        list.remove(0);//删除下标为0的元素
        list.remove("A");
        list.clear();
        System.out.println(list.size());
 }

LinkedList基本操作

public static void main(String[] args) {
        List<Integer> list=new LinkedList<>();
        list.add(9);
        list.add(8);
        list.add(7);
        list.add(0,1);//向0下标位置添加元素1
        List<Integer> list1=new ArrayList<>();
        list1.add(3);
        list1.addAll(list);//将list集合全部添加到list1中。

        list1.add(3);//允许添加重复元素

        //按照添加顺序打印
        System.out.println(list1);

        //可以用下标访问
        System.out.println(list1.get(0));
        //截取部分
        List<Integer> subList=list1.subList(0,3);
        System.out.println(subList);

        //可以重新构造
        List<Integer> list2=new LinkedList<>(list1);
        System.out.println(list2);
        List<Integer> list3=new LinkedList<>(list2);
        System.out.println(list3);
    }

ArrayList与LinkedList比较

• 添加或删除元素时，ArrayList效率要比LinkedList低一些。因为ArrayList底层是数组实现，需要动态扩容，和移动其他元素，就会导致性能有些损耗。
• 访问或修改元素时，ArrayList效率要更高一些。原因是LinkedList在访问元素时，没有下标，只能一个个的遍历寻找，查找一次就遍历一次，自然慢。
• ArrayList底层是数组实现，在使用add方法添加元素时，如何实现动态扩容？在JDK1.7中，会有一个方法先计算当前ArrayList的长度，然后默认为10，然后有一个grow方法，当需要扩容时，会扩容到原来大小的1.5倍,实际是通过Arrays.copyOf方法实现。