JavaSE之List中ArrayList底层和LinkedList底层

集合结构

List

List接口下的集合特点：

1.有索引

2.元素可以重复

3.存入和取出顺序一致

补充方法：

void clear()
清空集合中的所有数据

public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("11");
        list.add("22");
        list.add("33");
        System.out.println(list);
        list.clear();
        System.out.println(list);
    }
1
2
3
4
5
6
7
8
9

boolean contains(Object o)
是否包含某个元素

		ArrayList<String> list = new ArrayList<>();
        list.add("11");
        list.add("22");
        list.add("33");
        System.out.println(list.contains("11"));
1
2
3
4
5

ArrayList底层

ArrayList实现了List接口

ArrayList底层数据结构是数组，查询快，增删慢。

1.ArrayList底层是什么数据结构

是Object类型的数组，目的是为了兼容所有数据类型的元素
Object[] elementDate

2.底层的数组何时创建，初始化长度是多少？

调用无参构造方法，数组就会被创建，默认长度为0 （好处是为了节省内存）

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
1
2
3
4
5

3.首次调用add方法添加元素的时候，数组的长度变为多少？

首次添加元素，长度由0变为10

private void add(E e, Object[] elementData, int s) {
//开始数组长度为0，判断为true，进行grow()
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }
1
2
3
4
5
6
7

实际上是新建了一个数组，然后将数组指向新的地址值，并将原始的数组复制到新数组中。

4.如果添加的元素超过数组的长度，会怎样？

超过会进行扩容操作，扩容后变为15

扩容算法：原长度 + 原长度/2

除了调用无参构造方法之外，还可以调用有参的构造方法，这个参数就是数组的初始长度。

调用时机：

如果不知道元素的数量，可以使用无参的。

长度确定的时候，可以之间指定参数（好处是减少扩容的次数，提高效率，节省空间）

LinkedList

LinkedList的底层是一个双向链表，增删快（首尾操作效率最高），查询慢

双向链表可以对首尾元素进行操作，所以LinkedList中有很多首尾操作的API

查询多的场景，使用ArrayList

增删多的场景，使用LinkedList

无法确定场景，使用ArrayList

ArrayList和LinkedList的get(Index)方法，虽然乍一看好像都使用了索引，但是ArrayList的参数就是代表索引，通过索引去查询，而LinkedList的get参数只是一个编号，并不是通过索引去查找，而是通过链表一个一个向下查询，因为是双向链表，所以为了效率用这个编号确定在前半部分，还是后半部分，前半部分就从头开始遍历，在后半部分就从尾遍历。

最后

如果你对本文有疑问，你可以在文章下方对我留言，敬请指正，对于每个留言我都会认真查看。