前言
😀😄😁😊🤨🥰😚😗😄🫠😀😄😁😊🤨🥰😗🫢🫠🥰
欢迎开始数据结构的学习,本章讲解List与ArrayList
😀😄😁😊🤨🥰😗🫢🫠🥰😀😄😁😊🤨🥰😗🫢🫠🥰
List
什么是List?
在集合框架中，List是一个接口，继承自Collection。Collection也是一个接口,常用方法如下
站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。
List中提供了好的方法，虽然方法比较多，但是常用方法如下：
List
注意：List是个接口，并不能直接用来实例化。
如果要使用，必须去实例化List的实现类。在集合框架中ArrayList和LinkedList都实现了List接口。
ArrayList
在集合框架中，ArrayList是一个普通的类，实现了List接口
【说明】
- ArrayList是以泛型方式实现的，使用时必须要先实例化
- ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
- ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
- ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
- . 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
- ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
ArrayList使用
public static void main(String[] args) { // ArrayList创建，推荐写法 // 构造一个空的列表 List<Integer> list1 = new ArrayList<>(); // 构造一个具有10个容量的列表 List<Integer> list2 = new ArrayList<>(10); list2.add(1); list2.add(2); list2.add(3); // list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素 // list3构造好之后，与list中的元素一致 ArrayList<Integer> list3 = new ArrayList<>(list2); // 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难 List list4 = new ArrayList(); list4.add("111"); list4.add(100); }
ArrayList常见操作
ArrayList虽然提供的方法比较多，但是常用方法如下所示:
public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("JavaSE"); list.add("JavaWeb"); list.add("JavaEE"); list.add("JVM"); list.add("测试课程"); System.out.println(list); // 获取list中有效元素个数 System.out.println(list.size()); // 获取和设置index位置上的元素，注意index必须介于[0, size)间 System.out.println(list.get(1)); list.set(1, "JavaWEB"); System.out.println(list.get(1)); // 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置 list.add(1, "Java数据结构"); System.out.println(list); // 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置 list.remove("JVM"); System.out.println(list); // 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常 list.remove(list.size()-1); System.out.println(list); // 检测list中是否包含指定元素，包含返回true，否则返回false if(list.contains("测试课程")){ list.add("测试课程"); } // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找 list.add("JavaSE"); System.out.println(list.indexOf("JavaSE")); System.out.println(list.lastIndexOf("JavaSE")); // 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组 List<String> ret = list.subList(0, 4); System.out.println(ret); list.clear(); System.out.println(list.size()); }
ArrayList的遍历
ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器
public static void main(String[] args) { List<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); // 使用下标+for遍历 for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i) + " "); } System.out.println(); // 借助foreach遍历 for (Integer integer : list) { System.out.print(integer + " "); } System.out.println(); Iterator<Integer> it = list.listIterator(); while(it.hasNext()){ System.out.print(it.next() + " "); } System.out.println(); }
注意：
- ArrayList最长使用的遍历方式是：for循环+下标 以及 foreach
- 迭代器是设计模式的一种，后序容器接触多了再给大家铺垫
ArrayList的扩容机制
下面代码有缺陷吗？为什么？
public static void main(String[] args) { List<Integer> list = new ArrayList<>(); for (int i = 0; i < 100; i++) { list.add(i); } }
ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。
源码我就不展示了,有兴趣的小伙伴可以去搜.
【总结】
- 检测是否真正需要扩容，如果是调用grow准备扩容
- 预估需要库容的大小
- 初步预估按照1.5倍大小扩容
- 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
- 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
- 使用copyOf进行扩容
ArrayList的具体使用
public class Card { public int rank; // 牌面值 public String suit; // 花色 @Override public String toString() { return String.format("[%s %d]", suit, rank); } } import java.util.List; import java.util.ArrayList; import java.util.Random; public class CardDemo { public static final String[] SUITS = {"♠", "♥", "♣", "♦"}; // 买一副牌 private static List<Card> buyDeck() { List<Card> deck = new ArrayList<>(52); for (int i = 0; i < 4; i++) { for (int j = 1; j <= 13; j++) { String suit = SUITS[i]; int rank = j; Card card = new Card(); card.rank = rank; card.suit = suit; deck.add(card); } } return deck; } private static void swap(List<Card> deck, int i, int j) { Card t = deck.get(i); deck.set(i, deck.get(j)); deck.set(j, t); } private static void shuffle(List<Card> deck) { Random random = new Random(20190905); for (int i = deck.size() - 1; i > 0; i--) { int r = random.nextInt(i); swap(deck, i, r); } } public static void main(String[] args) { List<Card> deck = buyDeck(); System.out.println("刚买回来的牌:"); System.out.println(deck); shuffle(deck); System.out.println("洗过的牌:"); System.out.println(deck); // 三个人，每个人轮流抓 5 张牌 List<List<Card>> hands = new ArrayList<>(); hands.add(new ArrayList<>()); hands.add(new ArrayList<>()); hands.add(new ArrayList<>()); for (int i = 0; i < 5; i++) { for (int j = 0; j < 3; j++) { hands.get(j).add(deck.remove(0)); } } System.out.println("剩余的牌:"); System.out.println(deck); System.out.println("A 手中的牌:"); System.out.println(hands.get(0)); System.out.println("B 手中的牌:"); System.out.println(hands.get(1)); System.out.println("C 手中的牌:"); System.out.println(hands.get(2)); } }
