List集合

基本概念

java.util.List集合是Collection集合的子集合

• List集合中允许有重复的元素并且有先后放入次序。
• List集合的主要实现类有：ArrayList类、LinkedList类、Stack类、Vector类。
  • ArrayList类的底层是采用动态数组进行数据管理的，支持下标访问，增删元素不方便。
  • LinkedList类的底层是采用双向链表进行数据管理的，访问不方便，增删元素方便。
  • Stack类的底层是采用动态数组进行数据管理的，主要管理的是后进先出特征的数据结构，叫做栈
  • Vector类是比ArrayList类更线程安全的类，但是效率比较低，已过时。每次扩容是2倍。

ArrayList

特点：

• ArrayList类的底层是采用动态数组进行数据管理的
• 支持下标访问
• 增删元素不方便

以前声明数组的时候，就固定好了数组大小，如果数组需要添加元素的时候，我们会创建一个新的数组，然后把原来的数组内容拷贝过来。但是ArrayList不需要，它直接帮我们动态扩容添加元素，这就是一个动态扩容，其实就是ArrayList的底层帮我们做了数组的拷贝到新数组的操作，内部扩容。

数组特点

• 一块连续的存储内存空间
• 只存放具体数据

数组声明原理

• 声明一个List接口类型的引用指向ArrayList类型的对象，形成了多态

List arrayList = new ArrayList();

声明使用的是ArrayList的无参构造函数

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private int size;
    transient Object[] elementData;
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
}

• 无参构造只是指明了elementData
  • elementData：数组缓冲区，Object[]数组类型的一个缓冲区。验证了对应的ArrayList底层是一个数组类型的缓冲区
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA：Object的一维空数组
  • size：ArrayList 的大小，就是包含的元素数量

new创建ArrayList并没有去申请内存空间，只是声明了一个空数组。对应size值为0

增加元素

可以看到数组添加的时候是一个个添加，如果说在指定位置进行元素的添加，那么首先需要把元素都往后移动，把指定位置空出来才能进行添加操作。

看一下添加元素的底层源码

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }
    private Object[] grow() {
        return grow(size + 1);
    }
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                newCapacity(minCapacity));
    }
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                //private static final int DEFAULT_CAPACITY = 10;
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
                ? newCapacity
                : hugeCapacity(minCapacity);
    }
}

• add()
  • e：要添加的元素对象，比如66
    
• add(E e, Object[] elementData, int s)：
  • elementData：初始化时声明的数组
  • s：size，初始化的值为0
  • elementData = grow()：进行扩容

• grow(int minCapacity)：
  • 数组拷贝到新数组中

动态扩容

看一下对应ArrayList的源码，是不是扩容原来的1.5倍

• newCapacity(int minCapacity)：
  • int newCapacity = oldCapacity + (oldCapacity >> 1);
    • 新数组大小 = 旧大小 + 旧大小/2 {得到对应的新数组大小为原来的1.5倍} ``` << : 左移运算符，num << 1,相当于num乘以2

: 右移运算符，num >> 1,相当于num除以2 ```

• Math.max(DEFAULT_CAPACITY, minCapacity);
  • 如果添加元素对应数组大小小于10的时候，直接创建一个长度为10的数组。
    

动态扩容数组1.5倍在数组长度大于10以后才真正生效。

访问元素

ArrayList对应的是连续的，下标从0开始，所以想要访问哪个元素，直接填写对应的索引下标index就可以访问到。

删除元素

对应的删除同样，删除完对应下标元素后，需要把其它元素从后往前移动。

LinkedList

特点：

• LinkedList类的底层是采用双向链表进行数据管理的
• 访问不方便
  • 访问需要一个个遍历查看
• 增删元素方便

link数组是一个链表结构，在查找的时候需要都遍历一遍，遍历到哪里就是在哪里。

链表特点

• 链表的每个元素被称为结点
• 结点组成部分：
  • 结点的存储位置「地址」
  • 存储的具体数据
  • 下一个节点的地址

为了数据连接起来所以结点必须有下一个的内存地址

链表声明原理

• 声明一个List接口类型的引用指向LinkedList类型的对象，形成了多态

List linkList = new LinkedList<>();

声明使用的是LinkedList的无参构造函数

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
    public LinkedList() {
    }
}

• Node：就是一个结点
  • first：第一个结点
  • last：最后一个结点

new创建LinkedList并没有去申请内存空间，只是声明了一个空数组。对应size值为0

增加元素

对应添加元素，需要把地址连接起来
增加元素的方式有三种：链表头部插入值、尾部插入值、中间某个元素前插入值

看一下添加元素的底层源码：

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
}

• add(E e)
  • e：要添加的元素对象，比如：添加string类型的”java”

• linkLast(E e)
  • l：声明一个node对象，把最后的结点复制过来
  • 创建一个新的node
• 添加有先后顺序，因为每次都是往后面放linkLast

• Node<E> newNode = new Node<>(l, e, null)
  • l：对应的是prev
  • e：对应是element/item
  • null：对应的是next

• newNode：prev、next前后地址为null。element元素数据为传入的内容，比如:java
• last = newNode
  • 把新生成的node结点放在最后一个
• 如果第一次添加，则first也等于

尾部插入值

• 存储数据25，保存在地址0x10
• 存储数据69，保存在地址0x20
• 存储数据51，保存在地址0x40
• 存储数据98，保存在地址0x50

链表头部插入值

指定位置添加元素

• 把74数字添加到69和51中间。

步骤

• 数据74对应的下一个数据地址指向数据51
• 数据69对应的下一个数据地址指向数据74

删除元素

• 把25和51中间的数字69删除掉。

步骤

• 数据25对应的下一个数据地址指向51
• 数据69删除

总结

可以认为ArrayList和LinkedList的方法在逻辑上完全一样，只是在性能上有一定的差别

• ArrayList更适合于随机机访问
• LinkedList更适合于插入和删除

在性能要求不是特别苛刻的情形下可以忽略这个差别。

Stack

• 后进先出

多本书打包装箱，吃了就吐

其中Stack类的底层是采用动态数组进行数据管理的，该类主要用于描述一种具有后进先出特征的数据结构，叫做栈(last in fifirst out LIFO)。

Vector

其中Vector类的底层是采用动态数组进行数据管理的，该类与ArrayList类相比属于线程安全的类，效率比较低，以后开发中基本不用。「过时」每次扩容2倍

方法

list集合常用方法有以下几个，这些方法在list实现类里面都可以使用。我这里给大家说一下对应的通用方法对应各个实现类特定的方法，大家后面可以自己去看下。后续我们涉及到的方法再给大家讲解。

添加

添加对象

add()

add就是添加方法，我们在Collection集合里面也讲了对应的add()方法。

当然在List集合这里，对应的add()方法肯定是能继承下来的。
因为List接口是Collection接口的子接口。

只不过Collection里面的add()方法只是单独添加元素，就是一直往后添加。

这里我们说的add()方法是可以具体在指定的某个位置下进行添加

• 集合的开头位置添加
• 集合的中间位置添加
• 集合的结尾位置添加

public class ListDemo {
    public static void main(String[] args) {
        //准备list集合
        List linkedList = new LinkedList();
        System.out.println("list = " + linkedList); // []
        System.out.println("-------------------1.集合添加对象-----------------------");
        //向集合的开头位置添加元素
        //linkedList.add(1);
        linkedList.add(0,1);
        //集合的末尾添加元素 
        //linkedList.add(3);
        linkedList.add(1,3);
        System.out.println("list = " + linkedList); // [1, 3]
        //向集合的中间位置添加元素
        linkedList.add(1,"hello");
        System.out.println("list = " + linkedList);//[1, hello, 3]
        //想要添加到哪个位置，就写哪个位置到下标index
    }
}

添加集合内对象

addAll()

以上就是对应的添加元素，当然还有对应的addAll是一样的，addAll只不过是把对应对象参数换成了集合。

例子：

System.out.println("-------------------2.集合添加集合的对象-----------------------");
//要添加的集合
List linkedList1 = new LinkedList();
linkedList1.add("hello1");
//        linkedList1.add("hello");
linkedList1.add("list");
System.out.println("linkedList1 = " + linkedList1);//[hello, list]
//集合添加集合的对象
linkedList.addAll(1,linkedList1);
//可以添加重复元素hello 
System.out.println("list = " + linkedList);//[1, hello, list, hello, 3]

获取元素

get()

System.out.println("-------------------3.根据执行下标获取集合元素-----------------------");
//根据参数指定的下标来获取元素
//Object o = linkedList.get(2); //默认返回的是object类型，当我们知道是什么类型的时候可以转换一下
//父类转子类 大到小 强转
String s = (String) linkedList.get(2);
System.out.println("获取到的元素是：" + s);//获取到的元素是：list
//获取元素并进行强制类型转换的时候要慎重，容易发生类型转换异常
//编译正常，运行发生ClassCastException类型转换异常
String s1 = (String) linkedList.get(0);
System.out.println("获取到的元素是：" + s1);//1

父类转子类，就是大到小的转换，属于强制转换。

但是要注意的点，强转容易发生转换异常，但是编译的时候看不出来，所以，可以用Object类型来接收对象。

get方法写toString

System.out.println("-------------------3.get方法toString-----------------------");
System.out.println("长度："+ linkedList.size());//长度：5
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
//get方法获取集合的所有元素
for (int i = 0; i < linkedList.size(); i++) {
//  System.out.println("获取到的元素下标是：" + i);
//  System.out.println(linkedList.get(i));//打印元素
    Object o = linkedList.get(i);
    /**
     * 下标：0    1       2     3    4
     * 元素：1, hello1, list, hello, 3
     */
    //判断最后一个
    if(linkedList.size()-1 == i){
        stringBuilder.append(o).append("]");
    }else {
        stringBuilder.append(o).append(",").append(" ");
    }
}
System.out.println(stringBuilder);//[1, hello1, list, hello, 3]

元素出现的索引位置

• indexOf()：从前往后数
• lastIndexOf()：从后往前数

System.out.println("-------------------5.元素出现的索引位置-----------------------");
System.out.println("list第一次出现的索引位置："+linkedList.indexOf("list"));//2
System.out.println("list最后一次出现的索引位置："+linkedList.lastIndexOf("list"));//2
linkedList.add(4,"list");
System.out.println("linkedList = " + linkedList);//[1, hello1, list, hello, list, 3]
System.out.println("list第一次出现的索引位置："+linkedList.indexOf("list"));//2
System.out.println("list最后一次出现的索引位置："+linkedList.lastIndexOf("list"));//4

修改元素

• set(int index, E element)：修改的是指定位置的元素
  • 返回值为被修改位置的原来元素

System.out.println("-------------------6.修改指定位置元素-----------------------");
System.out.println("linkedList = " + linkedList);//[1, hello1, list, hello, list, 3]
String str = (String)linkedList.set(4, 2);
System.out.println("被修改的元素是：" + str);//list
System.out.println("修改后的linkedList = " + linkedList);//[1, hello1, list, hello, 2, 3]
Integer i1 = (Integer)linkedList.set(5, "three");
System.out.println("被修改的元素是：" + i1);//3
System.out.println("修改后的linkedList = " + linkedList);//[1, hello1, list, hello, 2, three]

删除元素

• remove()：删除集合中指定位置元素
  • 返回值为被修改位置的原来元素
• 需求：
  • remove删除集合中的所有元素

从前往后删除

for (int i = 0; i < linkedList.size(); i++) {  
    //删除的是1，3，5，7，9  
 System.out.println("被删除的元素是：" + linkedList.remove(i));//[hello1, hello, three]  
}  
System.out.println("删除后的linkedList = " + linkedList);//[hello1, hello, three]

• 删除元素后，后面的元素补位

可以看到对应以上不是我们想要的结果，删除的是下标为1，3，5这样。是因为我们对应删除完元素后，往前挪了一位，如下图：

所以，删除的时候应该是只删除下标为0的元素，循环的时候就不需要i++；只需要比较对应的i是否小于list长度

for (int i = 0; i < linkedList.size();/*i++*/) {
    System.out.println("被删除的元素是：" + linkedList.remove(0));
}
System.out.println("删除后的linkedList = " + linkedList);//[]

从后往前删除

• 还有一种就是从后往前删除元素

for (int i = linkedList.size()-1; i >= 0 ; i--) {
    System.out.println("被删除的元素是：" + linkedList.remove(i));
}
System.out.println("删除后的linkedList = " + linkedList);//[hello1, hello, three]

获取子集合

subList()

System.out.println("-------------------8.获取当前集合的子集合-----------------------");
//获取当前集合中的子集合 将集合的一部分内容获取出来
//子集合和当前集合公用同一块内存空间
//获取当前集合 从下标1开始到3之间的元素[1,3) 包含1不包含3
//[1, hello1, list, hello, 2, three]
List list = linkedList.subList(1, 3);
System.out.println("list= "+ list);//[hello1, list]

• 子集合和当前集合共用同一块内存空间

//删除子集合list中元素的数值
String restr = (String) list.remove(0);
System.out.println("被删除的元素是："+restr);//hello1
System.out.println("list= "+ list);//[list]
System.out.println("linkedList = " + linkedList);//[1, list, hello, 2, three]

可以看到对应的删除子集合内元素的时候对应父类集合的元素也同样被删除掉了