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

• • • 前言
    • List
    • • • 什么是List?
        • List
        • ArrayList
        • • • ArrayList使用
            • ArrayList常见操作
            • ArrayList的遍历
            • ArrayList的扩容机制
            • 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使用

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

              ArrayList常见操作

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

               public static void main(String[] args) {
                  List 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 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 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 it = list.listIterator();
                  while(it.hasNext()){
                      System.out.print(it.next() + " ");
                  }
                  System.out.println();
               }
              

              注意：

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

              ArrayList的扩容机制

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

              public static void main(String[] args) {
               List list = new ArrayList<>();
               for (int i = 0; i < 100; i++) {
               list.add(i);
               }
               }
              

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

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

              【总结】

              1. 检测是否真正需要扩容，如果是调用grow准备扩容
              2. 预估需要库容的大小
              3. 初步预估按照1.5倍大小扩容
              4. 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
              5. 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
              6. 使用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 buyDeck() {
              List 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 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 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 deck = buyDeck();
                      System.out.println("刚买回来的牌:");
                      System.out.println(deck);
                      shuffle(deck);
                      System.out.println("洗过的牌:");
                      System.out.println(deck);
                      // 三个人，每个人轮流抓 5 张牌
                      List> 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));
               }
               }