数据结构第一篇【探究List和ArrayList之间的奥秘 】

数据结构第一篇【探究List和ArrayList之间的奥秘 】

前言

😀😄😁😊🤨🥰😚😗😄🫠😀😄😁😊🤨🥰😗🫢🫠🥰
欢迎开始数据结构的学习,本章讲解List与ArrayList

😀😄😁😊🤨🥰😗🫢🫠🥰😀😄😁😊🤨🥰😗🫢🫠🥰

List

什么是List?

在集合框架中，List是一个接口，继承自Collection。Collection也是一个接口,常用方法如下

站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

List中提供了好的方法，虽然方法比较多，但是常用方法如下：

List

注意：List是个接口，并不能直接用来实例化。
如果要使用，必须去实例化List的实现类。在集合框架中ArrayList和LinkedList都实现了List接口。

ArrayList

在集合框架中，ArrayList是一个普通的类，实现了List接口

【说明】

1. ArrayList是以泛型方式实现的，使用时必须要先实例化
2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
5. . 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

ArrayList使用

publicstaticvoidmain(String[] args){// ArrayList创建，推荐写法// 构造一个空的列表List<Integer> list1 =newArrayList<>();// 构造一个具有10个容量的列表List<Integer> list2 =newArrayList<>(10);
    list2.add(1);
    list2.add(2);
    list2.add(3);// list2.add("hello");  // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素// list3构造好之后，与list中的元素一致ArrayList<Integer> list3 =newArrayList<>(list2);// 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难List list4 =newArrayList();
    list4.add("111");
    list4.add(100);}

ArrayList常见操作

ArrayList虽然提供的方法比较多，但是常用方法如下所示:

publicstaticvoidmain(String[] args){List<String> list =newArrayList<>();
    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，否则返回falseif(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、使用迭代器

publicstaticvoidmain(String[] args){List<Integer> list =newArrayList<>();
    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();}

注意：

1. ArrayList最长使用的遍历方式是：for循环+下标 以及 foreach
2. 迭代器是设计模式的一种，后序容器接触多了再给大家铺垫

ArrayList的扩容机制

下面代码有缺陷吗？为什么？

publicstaticvoidmain(String[] args){List<Integer> list =newArrayList<>();for(int i =0; i <100; i++){
 list.add(i);}}

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。

源码我就不展示了,有兴趣的小伙伴可以去搜.

【总结】

1. 检测是否真正需要扩容，如果是调用grow准备扩容
2. 预估需要库容的大小
3. 初步预估按照1.5倍大小扩容
4. 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
5. 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
6. 使用copyOf进行扩容

ArrayList的具体使用

publicclassCard{publicint rank;// 牌面值publicString suit;// 花色@OverridepublicStringtoString(){returnString.format("[%s %d]", suit, rank);}}importjava.util.List;importjava.util.ArrayList;importjava.util.Random;publicclassCardDemo{publicstaticfinalString[]SUITS={"♠","♥","♣","♦"};// 买一副牌privatestaticList<Card>buyDeck(){List<Card> deck =newArrayList<>(52);for(int i =0; i <4; i++){for(int j =1; j <=13; j++){String suit =SUITS[i];int rank = j;Card card =newCard();
                card.rank = rank;
                card.suit = suit;
                
                deck.add(card);}}return deck;}privatestaticvoidswap(List<Card> deck,int i,int j){Card t = deck.get(i);
        deck.set(i, deck.get(j));
        deck.set(j, t);}privatestaticvoidshuffle(List<Card> deck){Random random =newRandom(20190905);for(int i = deck.size()-1; i >0; i--){int r = random.nextInt(i);swap(deck, i, r);}}publicstaticvoidmain(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 =newArrayList<>();
        hands.add(newArrayList<>());
        hands.add(newArrayList<>());
        hands.add(newArrayList<>());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));}}