Java填坑之List

在写代码中会经常用到Collection集合接口，最多用的就是ArrayList、HashMap等实现类，但是在一些面试题或者在看一些文献的时候，会用到Queue或者Set等，每次遇到这一块都是哪里不会查哪里，知识点是零散的，所以决定写一篇梳理一下Collection集合接口的各种知识点；思路是根据自己整理的，其中引用一些大佬的文章的话，链接这样贴出来：https://www.jianshu.com/p/63b01b6379fb
https://www.cnblogs.com/liulin1187740947/p/9164870.html
http://www.yiidian.com/java-collection/java-linkedlist.html

List

如图所见，List是一个接口，在它下面有ArrayList,LinkedList,Vector三个实现类，List有什么特点呢？

• 它是一个元素存取有序的集合
• 它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素
• 集合中可以有重复的元素，通过元素的equals方法，来比较是否为重复的元素。

我们都知道接口中定义的方法在实现类中是一定要实现的，List承诺可以将元素维护在特定的序列中。List接口在Collection的基础上添加了大量的方法，使得可以在List的中间插入和添加元素：

其中有两种类型的List：

• 基本的ArrayList：它擅长于随机访问元素，但是在List的中间插入和移除元素时较慢。
• LinkedList：它通过代价较低的在List中间进行插入和删除操作，提供了比较优化的顺序访问；LinkedList在随机访问方面相对比较慢，但是它的特性集较ArrayList更大。

其中，ArrayList底层通过数组实现，随着元素的增加而动态扩容。而LinkedList底层通过链表来实现，随着元素的增加不断向链表的后端增加节点。

ArrayList

ArrayList是Java集合框架中使用最多的一个类，是一个数组队列，线程不安全集合，它继承于AbstractList，实现了List, RandomAccess, Cloneable, Serializable接口。

• ArrayList实现List，得到了List集合框架基础功能；
• ArrayList实现RandomAccess，获得了快速随机访问存储元素的功能，RandomAccess是一个标记接口，没有任何方法；
• ArrayList实现Cloneable，得到了clone()方法，可以实现克隆功能；
• ArrayList实现Serializable，表示可以被序列化，通过序列化去传输，典型的应用就是hessian协议。

ArrayList的特点

• 容量不固定，随着容量的增加而动态扩容（阈值基本不会达到）
• 有序集合（插入的顺序==输出的顺序）
• 插入的元素可以为null
• 增删改查效率更高（相对于LinkedList来说）
• 线程不安全

思考

1. Java中已经有了Array数组，里面可以存储基本数据类型也能存储对象，那为什么我们还要使用ArrayList，它们有什么区别呢？

答：

• ArrayList是Array的复杂版本
  可以将 ArrayList想象成一种“会自动扩增容量的Array”，ArrayList内部封装了一个Object类型的数组，从一般的意义来说，它和数组没有本质的差别，甚至于ArrayList的许多方法，如Index、IndexOf、Contains、Sort等都是在内部数组的基础上直接调用Array的对应方法。

• 存储的数据类型
  ArrayList可以存储异构对象，而Array只能存储相同数据类型的数据；同构的对象是指类型相同的对象，若声明为int[]的数组就只能存放整形数据,string[]只能存放字符型数据,但声明为object[]的数组除外。 而ArrayList可以存放任何不同类型的数据（因为它里面存放的都是被装箱了的Object型对象，实际上ArrayList内部就是使用"object[] _items;"这样一个私有字段来封装对象的）

  class Apple {}
  class Orange {}
  //	没有使用泛型!!!
  ArrayList apples = new ArrayList();
  apples.add(new Apple());
  apples.add(new Orange());
  

• 长度的可变
  数组具有固定的尺寸，而在一般的情况中，我们在写程序时并不知道将需要多少个对象，或者是否需要更复杂的方式来存储对象，因此数组尺寸固定会非常限制，而ArrayList的长度既可以指定（即使指定了长度，也会自动2倍扩容）也可以不指定，是变长的。

• 存取和增删元素
  对于一般的引用类型来说，这部分的影响不是很大，但是对于值类型来说，往ArrayList里面添加和修改元素，都会引起装箱和拆箱的操作，频繁的操作可能会影响一部分效率。基于效率和类型检验，应尽可能使用Array，无法确定数组大小时才使用ArrayList，不过当你试着解决更一般化的问题时，Array的功能就可能过于受限。

2.在创建集合对象的时候，ArrayList arr = new ArrayList();与 List arr = new ArrayList();的区别

ArrayList arr = new ArrayList();
//推荐
List arr = new ArrayList();

这里涉及到Java基础多态的概念，我们都知道Java是一种面向对象语言，我们编写代码的时候也要秉承着面向对象编程的概念，List 是一个接口，定义了一些方法，但是方法没有被实现，ArrayList是一个类实现了内List这个接口，List里边定义的方法 在ArrayList里边都实现了，同时List也可以被别的类所实现例如Vector，Vector和ArrayList对List定义的方法的实现就有所区别；而且我们用实现接口的方法显得更加灵活：

import org.junit.Test;

import java.util.*;

public class Demo {

    List list;

    public List getArrayList(List list) {
        list = new ArrayList();
        return list;
    }
    
    public List getLinkedList(List list) {
        list = new LinkedList();
        return list;
    }
    
}

我们想拿ArrayList或者LinkedList直接调方法就好了，如果我们一开始就写死是ArrayList类的话，还得重新修改返回类型。但是特殊的一点是，比如我们如果要调用LinkedList具有而在List里面没有的方法（LinkedList特有方法），就不能将它向上转型成更通用的接口了，就只能老老实实用LinkedList list = new LinkedList();了。

3. 添加一组对象

我们怎么向集合里面一次性添加一组对象呢？Collection接口里面自带了一个方法：

boolean addAll(Collection<? extends E> c);

或者在Collection接口的实现类中自带的构造器：

除此之外，我们还可以用java.uitl包中的Arrays和Collections类的使用方法，给Collection中添加一组元素，Arrays.asList()方法接一个数组或者是一个逗号分割的元素列表，并将其转换为一个List对象。

	//逗号分割
	List list1 = Arrays.asList(1, 2, 3);
    Integer[] more = {6, 7, 8};
    //数组
    List list2 = Arrays.asList(more);

我们再看看怎么用Collections里面的addAll()方法：

public static <T> boolean addAll(Collection<? super T> c, T... elements) {
        boolean result = false;
        for (T element : elements)
            result |= c.add(element);
        return result;
    }

Collections的addAll()可以接受一个Collection对象，以及一个数组或是一个用逗号分割列表，将元素添加到Collection中；那用Collections的addAll()与Arrays.asList()有什么区别呢？Arrays.asList()方法的限制是它对所产生的List的类型做出了最理想的假设，而并没有注意到你会对她赋予什么样的类型，我们引用《Thinking in java》里面一个经典的例子：

class Snow{}
class Powder extends Snow{}
class Light extends Powder{}
class Heavy extends Powder{}
class Crustry extends Snow{}
class Slush extends Snow{}

public class AsListInference{
	public static void main(String[] args){
	List<Snow> snow1 = Arrays.asList(new Crustry(),new Slush(),new Powder());
	//Wont compile 因为编译器会以为是转为Powder类型:
	//List<Snow> snow2 = Arrays.asList(new Light(),new Heavy());
	//因为显示指定了是转为Snow类型
	List<Snow> snow3 = new Array<Snow>();
	Collections.addAll(snow3,new Light(),new Heavy());
	//我们也可以插入一条线索 使它识别到我们是想转为Snow类型的
	List<Snow> snow4 = Arrays.<Snow>asList(new Light(),new Heavy());
	
}

LinkedList

LinkedList是一个双向链表，每一个节点都拥有指向前后节点的引用。相比于ArrayList来说，LinkedList的随机访问效率更低。

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

• LinkedList实现List，得到了List集合框架基础功能；
• LinkedList实现Deque，Deque 是一个双向队列，也就是既可以先入先出，又可以先入后出，说简单些就是既可以在头部添加元素，也可以在尾部添加元素；
• LinkedList实现Cloneable，得到了clone()方法，可以实现克隆功能；
• LinkedList实现Serializable，表示可以被序列化，通过序列化去传输，典型的应用就是hessian协议。

LinkedList的特点是：

• Java LinkedList类可以存储重复的元素。
• Java LinkedList类是有序的。
• Java LinkedList类是非同步的（线程不安全的）。
• 在Java LinkedList类中，由于不需要进行任何转换，因此处理速度很快。
• Java LinkedList类可以用作List，Stack或Queue。

LinkedList还添加了可以使其用作栈，队列或双端队列的方法。

思考

1. 为什么Java Vector（和Stack）类被认为已过时或已弃用？

   Vector是1.0的一部分 - 原始实现有两个缺点：
   1.命名：vectors实际上只是可以作为数组访问的列表，因此它应该被称为ArrayList(它是Vector的Java 1.2 Collections替代品)。
   2.并发：所有get()，set()方法都是synchronized，所以你无法对同步进行细粒度控制。
   ArrayList和Vector之间没有太大区别，但你应该使用ArrayList。

转载：https://blog.csdn.net/weixin_37138915/article/details/105884866