【数据结构】Java顺序表—ArrayList详解_java arraylist 有序

Java顺序表—ArrayList

1. ArrayList简介

在Java的集合框架中，ArrayList类是List接口的一个具体实现类，其继承框架图如下：

说明：

• ArrayList是一个泛型类，在实例化时可以指定对应的类型参数
• ArrayList实现了RandomAccess接口，表明该类支持随机访问
• ArrayList实现了Cloneable接口，表明该类支持clone方法
• ArrayList实现了Serializable接口，表明该类支持可序列化
• ArrayList与Vector不同，ArrayList是线程不安全的，若想要安全的可以使用Vector和CopyOnWriteArrayList
• ArrayList底层使用的数据结构为数组，是一段连续的内存空间，是一个可以实现动态扩容的顺序表

2. ArrayList的使用

2.1 ArrayList的构造方法

import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        // 构造方法一: 无参构造
        ArrayList<Integer> list = new ArrayList<>();
        System.out.println(list);

        // 构造方法二: 初始化容量
        ArrayList<String> list2 = new ArrayList<>(20);
        list2.add("hello");
        list2.add("world");
        System.out.println(list2);

        // 构造方法三: 利用别的Collection初始化
        ArrayList<String> list3 = new ArrayList<>(list2);
        // 此时list3与list2中存储元素一致
        System.out.println(list3);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.2 ArrayList的常用操作方法

2.2.1 增加系列方法

@Test
public void test_add() {
    ArrayList<Integer> list = new ArrayList<>();
    // 1. add(E e)方法的使用
    list.add(1);
    list.add(2);
    list.add(3);
    System.out.println(list);
    // 2. add(int index, E element)方法的使用
    list.add(1, 4);
    System.out.println(list);
    // 3. addAll(Collection<? extends E> c)方法的使用
    ArrayList<Integer> tmp = new ArrayList<>();
    tmp.add(10);
    tmp.add(20);
    list.addAll(tmp); // 将tmp集合元素全部添加到list末尾
    System.out.println(list);
    // 4. addAll(int index, Collection<? extends E> c)
    list.addAll(2, tmp); // 将tmp集合元素全部添加到指定下标
    System.out.println(list);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行效果如下：

2.2.2 删除系列方法

@Test
public void test_remove() {
    ArrayList<Integer> list = new ArrayList<>();
    // 创建集合
    list.addAll(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)); // asList方法可以看做构建一个集合
    System.out.println(list);
    // 1. remove(int index)方法的使用
    list.remove(0);
    System.out.println(list);
    // 2. remove(Object o)方法的使用
    list.remove(Integer.valueOf(5));
    System.out.println(list);
    // 3. removeAll(Collection<?> c)
    ArrayList<Integer> tmp = new ArrayList<>();
    tmp.add(2);
    tmp.add(3);
    list.removeAll(tmp);
    System.out.println(list);
    // 4. retainAll(Collection<?> c)
    ArrayList<Integer> tmp2 = new ArrayList<>();
    tmp2.add(4);
    tmp2.add(6);
    list.retainAll(tmp2);
    System.out.println(list);
    // 5. clear()
    list.clear();
    System.out.println(list);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

注意：

• 如果想要使用remove(Object o)删除整型元素，则参数不能使用自动装箱，因为会优先调用remove(int index)方法，必须显式装箱如（Integer.valueOf()方法）

运行效果如下：

2.2.3 修改系列方法

@Test
public void test_modify() {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    System.out.println(list);
    // E set(int index, E element)方法
    list.set(1, 100);
    System.out.println(list);
}
1
2
3
4
5
6
7
8
9
10
11

运行效果如下：

2.2.4 查询系列方法

@Test
public void test_search() {
    ArrayList<String> list = new ArrayList<>();
    list.add("Java");
    list.add("Spring");
    list.add("JavaWeb");
    list.add("Spring");
    list.add("SpringBoot");
    list.add("Mybatis");
    list.add("redis");
    // 1. E get(int index)
    System.out.println(list.get(2));
    // 2. boolean contains(Object o)
    System.out.println(list.contains("redis"));
    // 3. int indexOf(Object o)
    System.out.println(list.indexOf("Spring"));
    // 4. int lastIndexOf(Object o)
    System.out.println(list.lastIndexOf("Spring"));
    // 5. int size()
    System.out.println(list.size());
    // 6. boolean isEmpty()
    System.out.println(list.isEmpty());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行效果如下：

2.2.5 其他方法

注意：

• 该方法参数区间为左闭右开，即[fromIndex, toIndex)

• 该方法返回类型为List，而不是ArrayList

• 该方法返回的子列表如果涉及修改操作，则会直接影响原先列表中的值，举例如下

@Test
public void test_subList() {
    // 构建原列表
    ArrayList<String> srcList = new ArrayList<>();
    srcList.add("MySQL");
    srcList.add("Linux");
    srcList.add("Docker");
    srcList.add("redis");
    // 构建子列表
    List<String> subList = srcList.subList(1, 3);
    System.out.println(subList);
    // 尝试修改subList中的元素
    subList.set(0, "Spring");
    System.out.println(subList); //打印子列表
    System.out.println(srcList); // 打印原列表
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

程序运行结果如下：

2.3 ArrayList的遍历方式

2.3.1 for循环+下标

@Test
public void test_traverse_forIndex() {
    // for循环加下标遍历
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    for (int i = 0; i < list.size(); i++) {
        System.out.println(list.get(i));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3.2 forEach遍历

@Test
public void test_traverse_forEach() {
    // 增强for循环遍历
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    for (int elem : list) {
        System.out.println(elem);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3.3 使用迭代器遍历

@Test
public void test_traverse_iterator() {
    // 迭代器遍历
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    Iterator<Integer> iter = list.iterator();
    while (iter.hasNext()) {
        int elem = iter.next();
        System.out.println(elem);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3. ArrayList的扩容机制

ArrayList是一个在插入元素过程中自动扩容的顺序表，其源码实现如下：

// 部分成员变量
Object[] elementData; // 存放元素的空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间
private static final int DEFAULT_CAPACITY = 10; // 默认容量大小

// 无参构造方法
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

// add方法
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// edsureCapacityInternal方法
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

// ensureExplicitCapacity方法
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// grow方法
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

扩容流程分析（以无参构造为例）：①、当通过无参构造器初始化ArrayList对象时，属性ElementData指向空对象DEFAULTCAPACITY_EMPTY_ELEMENTDATA ②、调用add方法时，调用ensureCapacityInternal方法检查容量，传递参数size + 1即所需最小空间 ③、在ensureCapacityInternal方法中，判断如果是第一次调用add方法，就申请当前minCapacity和默认容量DEFAULT_CAPACITY其中更大值作为申请空间大小，然后调用ensureExplicitCapacity方法。④、在方法ensureExplicitCapacity中，判断当前所需空间minCapacity是否超过当前数组容量，如果超过则调用grow方法进行扩容 ⑤、在grow方法中，newCapacity是1.5倍扩容后的大小最后调用Arrays.copyOf()进行扩容

总结：

1. 扩容策略首先判断是否需要扩容，如果需要则调用grow()方法扩容
2. 初步预计1.5倍的方式进行扩容，如果用户所需大于1.5倍则按照需求进行扩容
3. 扩容通过调用Arrays.copyOf方法

4. ArrayList的使用场景—简单洗牌小案例

简单洗牌小案例我们模拟用户斗地主时的场景，可以将洗牌过程抽象为如下几个步骤

1. 生成一副完整的扑克牌（不考虑大小王）
2. 将扑克牌进行洗牌（打乱扑克牌）
3. 模拟给用户发牌

package CardDemo;

import java.util.ArrayList;

public class Player {
    private String name;
    private ArrayList<Poker.Card> cardList; // 牌组

    public Player(String name) {
        this.name = name;
        this.cardList = new ArrayList<>();
    }

    // 给玩家发牌方法
    public void distributeCards(ArrayList<Poker.Card> cards) {
        // 从剩余牌中随机选择一张
        int randomIndex = (int) (Math.random() * cards.size());
        cardList.add(cards.get(randomIndex));
        cards.remove(randomIndex);
    }

    @Override
    public String toString() {
        return "Player{" +
                "name='" + name + '\'' +
                ", cardList=" + cardList +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

package CardDemo;

import java.util.ArrayList;
import java.util.Collections;

// 扑克牌类
public class Poker {
    private ArrayList<Card> cards; // 扑克牌
    private static final String[] suits = {"♥", "♠", "♣", "♦"};
    private static final String[] faces = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"};

    // 内部类：单张牌
    static class Card {
        public String face; // 牌面值
        public String suits; // 花色值

        public Card(String face, String suits) {
            this.face = face;
            this.suits = suits;
        }

        @Override
        public String toString() {
            return face + ":" + suits;
        }
    }

    // 初始化扑克牌
    public Poker() {
        cards = new ArrayList<>();
        generateCards();
    }

    // 生成扑克牌函数
    public void generateCards() {
        for (int i = 0; i < suits.length; i++) {
            for (int j = 0; j < faces.length; j++) {
                cards.add(new Card(suits[i], faces[j]));
            }
        }
    }

    // 洗牌方法
    public void shuffleCards() {
        // 调用Collections.shuffle方法
        Collections.shuffle(cards);
    }

    // 返回扑克牌
    public ArrayList<Card> getCards() {
        return this.cards;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

package CardDemo;

import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        // 生成一副扑克牌并打乱
        Poker poker = new Poker();
        poker.shuffleCards(); // 洗牌
        ArrayList<Poker.Card> cards = poker.getCards();
        // 生成四个用户
        Player player1 = new Player("玩家一");
        Player player2 = new Player("玩家二");
        Player player3 = new Player("玩家三");
        Player player4 = new Player("玩家四");
        Player[] players = {player1, player2, player3, player4};
        // 循环给玩家发牌
        int index = 0;
        while (cards.size() > 0) {
            players[index].distributeCards(cards);
            index = (index + 1) % players.length;
        }
        // 打印每个玩家的牌
        System.out.println(player1);
        System.out.println(player2);
        System.out.println(player3);
        System.out.println(player4);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

5. ArrayList的缺点与思考

1. ArrayList底层数据结构为数组，但是删除数据、插入数据最坏时间复杂度都为O（n），如果是大量删除或者插入数据的应用场景下效率十分低下
2. 假设按照1.5倍扩容，原来容量为100，则扩容后为150，但是此时只新增了一个数据，剩下49个空间都被浪费了
3. 频繁的扩容都需要申请新空间、拷贝数据、释放原先空间，存在一定的开销。