Java集合之List

List接口

1 List接口概述

• 鉴于Java中数组用来存储数据的局限性，我们通常使用List替代数组
• List集合类中元素有序(存储和取出元素顺序相同)、且可重复，集合中的每个元素都有其对应的顺序索引，可以使用普通的for循环遍历
• List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素
• JDK API中List接口的实现类常用的有：ArrayList、LinkedList和Vector(线程安全的)。

2 List接口中的方法

List除了从Collection集合继承的方法外，List 集合里添加了一些根据索引来操作集合元素的方法。

• void add(int index, Object obj)：在index位置插入obj元素
• boolean addAll(int index, Collection coll)：从index位置开始将coll集合中的所有元素添加进来
• Object get(int index)：获取指定index位置的元素
• int indexOf(Object obj)：返回obj在集合中首次出现的位置
• int lastIndexOf(Object obj)：返回obj在当前集合中末次出现的位置
• Object remove(int index)：移除指定index位置的元素，并返回此元素
• Object set(int index, Object obj)：设置指定index位置的元素为obj
• List subList(int fromIndex, int toIndex)：返回从fromIndex到toIndex位置的子集合

3 List实现类之一：ArrayList

• ArrayList 是 List 接口的典型实现类、主要实现类
• 本质上，ArrayList是对象引用的一个**"变长"数组**
• ArrayList的JDK1.8之前与之后的实现区别？
  • JDK1.7：ArrayList像饿汉式，直接创建一个初始容量为10的数组
  • JDK1.8：ArrayList像懒汉式，一开始创建一个长度为0的数组，当添加第一个元素时再创建一个始容量为10的数组
• Arrays.asList(…) 方法返回的 List 集合，既不是 ArrayList 实例，也不是Vector 实例。 Arrays.asList(…) 返回值是一个固定长度的 List 集合

4 List实现类之二：LinkedList

• 对于频繁的插入或删除元素的操作，建议使用LinkedList类，效率较高
• LinkedList：双向链表，内部没有声明数组，而是定义了Node类型的first和last，用于记录首末元素。同时，定义内部类Node，作为LinkedList中保存数据的基本结构。Node除了保存数据，还定义了两个变量：
  • prev变量记录前一个元素的位置
  • next变量记录下一个元素的位置

private static class Node<E>{
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next){
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
}
1
2
3
4
5
6
7
8
9
10
11

• 新增方法:

  • void addFirst(Object obj)：在次列表的开始处插入指定的元素。
  • void addLast(Object obj)：在此列表的末尾处插入指定的元素
  • Object getFirst()：返回此列表中的第一个元素。
  • Object getLast()：返回此列表中的最后元素。
  • Object removeFirst()：移除并返回此列表中的第一个元素
  • Object removeLast()：移除并返回此列表中的最后一个元素

5 List实现类之三：Vector

• Vector是一个古老的集合，JDK1.0就有了。大多数操作与ArrayList相同，区别之处在于Vector是线程安全的。
• 在各种list中，最好把ArrayList作为缺省选择。当插入、删除频繁时，使用LinkedList；Vector总是比ArrayList慢，所以尽量避免使用
• 新增方法：
  • void addElement(Object obj)：将指定的组件添加到此向量的末尾，将其大小增加1。
  • void insertElementAt(Object obj,int index)：将指定的对象作为组件插入此Vector中。
  • void setElementAt(Object obj,int index)：将位于此Vector的指定索引处的组件设置为指定对象。
  • void removeElement(Object obj)：从该向量中移除第一个（最低索引）发生的参数
  • void removeAllElements()：从该向量中移除所有组件，并将其大小设置为零。

6 三个实现类的异同(重点)

面试题：请问ArrayList/LinkedList/Vector的异同？谈谈你的理解？ArrayList底层是什么？扩容机制？Vector和ArrayList的最大区别?

• ArrayList和LinkedList的异同：

  • 二者都线程不安全，相对线程安全的Vector，执行效率高。

  • ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

  • 对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。对于新增和删除操作add(特指插入)和remove，LinkedList比较占优势，因为ArrayList要移动数据。

• ArrayList和Vector的区别：

  • Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized)，属于强同步类。因此开销就比ArrayList要大，访问要慢。正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。
  • Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。
  • Vector还有一个子类Stack。