• JavaSE---ArrayList与顺序表

    1、线性表

            线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...
            线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

     2、顺序表

            顺序表是用一段物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

    2.1 接口的实现 

    1. public class SeqList 
    2. { 
    3.     //打印顺序表
    4.     public void display() 
    5.     { 
    6.  
    7.     }
    8.  
    9.     //新增元素,默认在数组最后新增
    10.     public void add(int data) 
    11.     {
    12.  
    13.     }
    14.  
    15.     //在 pos 位置新增元素
    16.     public void add(int pos, int data) 
    17.     { 
    18.  
    19.     }
    20.     
    21.     //判定是否包含某个元素
    22.     public boolean contains(int toFind) 
    23.     { 
    24.         return true; 
    25.     } 
    26.  
    27.     // 查找某个元素对应的位置
    28.     public int indexOf(int toFind) 
    29.     { 
    30.         return -1; 
    31.     } 
    32.     
    33.     //获取 pos 位置的元素
    34.     public int get(int pos) 
    35.     { 
    36.         return -1; 
    37.     } 
    38.     
    39.     //给 pos 位置的元素设为 value
    40.     public void set(int pos, int value) 
    41.     { 
    42.     
    43.     } 
    44.  
    45.     //删除第一次出现的关键字key
    46.     public void remove(int toRemove) 
    47.     { 
    48.     
    49.     } 
    50.     
    51.     //获取顺序表长度
    52.     public int size() 
    53.     { 
    54.         return 0; 
    55.     } 
    56.     
    57.     //清空顺序表
    58.     public void clear()
    59.     { 
    60.     
    61.     } 
    62. }

    3、ArrayList简介

            在集合框架中，ArrayList 是一个普通的类，实现了 List 接口，具体框架图如下：

     【说明】

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

    4、ArrayList使用

    4.1 ArrayList的构造

     ArrayList （Java Platform SE 8 ） (oracle.com)https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html#ArrayList--

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

    4.2 ArrayList常见操作

    1. public static void main(String[] args) 
    2. { 
    3.     List list = new ArrayList<>(); 
    4.     list.add("JavaSE"); 
    5.     list.add("JavaWeb"); 
    6.     list.add("JavaEE"); 
    7.     list.add("JVM"); 
    8.     list.add("测试课程"); 
    9.     System.out.println(list);
    10.  
    11.     // 获取list中有效元素个数 
    12.     System.out.println(list.size());
    13.  
    14.     // 获取和设置index位置上的元素，注意index必须介于[0, size)间 
    15.     System.out.println(list.get(1)); 
    16.     list.set(1, "JavaWEB"); 
    17.     System.out.println(list.get(1)); 
    18.  
    19.     // 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置 
    20.     list.add(1, "Java数据结构"); 
    21.     System.out.println(list); 
    22.  
    23.     // 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置 
    24.     list.remove("JVM"); 
    25.     System.out.println(list); 
    26.  
    27.     // 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常             
    28.     list.remove(list.size()-1); 
    29.     System.out.println(list);
    30.  
    31.     // 检测list中是否包含指定元素，包含返回true，否则返回false 
    32.     if(list.contains("测试课程"))
    33.     { 
    34.         list.add("测试课程"); 
    35.     }
    36.  
    37.     // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找 
    38.     list.add("JavaSE"); 
    39.     System.out.println(list.indexOf("JavaSE"));         
    40.     System.out.println(list.lastIndexOf("JavaSE")); 
    41.  
    42.     // 使用list中[0, 4)之间的元素构成一个新的ArrayList返回 
    43.     List ret = list.subList(0, 4); 
    44.     System.out.println(ret); 
    45.     
    46.     list.clear(); 
    47.     System.out.println(list.size()); 
    48. }

    4.3 ArrayList的遍历

            ArrayList 可以使用三方方式遍历： for 循环 + 下标、 foreach 、使用迭代器 
    1. public static void main(String[] args) 
    2. { 
    3.     List list = new ArrayList<>(); 
    4.     list.add(1); 
    5.     list.add(2); 
    6.     list.add(3); 
    7.     list.add(4); 
    8.     list.add(5); 
    9.     //使用下标+for遍历 
    10.     for (int i = 0; i < list.size(); i++) 
    11.     { 
    12.         System.out.print(list.get(i) + " "); 
    13.     }
    14.     System.out.println(); 
    15.     // 借助foreach遍历 
    16.     for (Integer integer : list) 
    17.     { 
    18.         System.out.print(integer + " "); 
    19.     }
    20.     System.out.println(); 
    21.     Iterator it = list.listIterator(); 
    22.     while(it.hasNext())
    23.     { 
    24.         System.out.print(it.next() + " "); 
    25.     }
    26.     System.out.println(); 
    27. }

    4.4 ArrayList的扩容机制

    1. public static void main(String[] args) 
    2. { 
    3.     List list = new ArrayList<>(); 
    4.     for (int i = 0; i < 100; i++) 
    5.     { 
    6.         list.add(i); 
    7.     } 
    8. }
            ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容：以下是 ArrayList 源码中扩容方式 
    1. Object[] elementData; // 存放元素的空间
    2. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间
    3. private static final int DEFAULT_CAPACITY = 10; // 默认容量大小
    4.  
    5. public boolean add(E e) 
    6. { 
    7.     ensureCapacityInternal(size + 1); 
    8.     // Increments modCount!! elementData[size++] = e; 
    9.     return true; 
    10. }
    11.  
    12. private void ensureCapacityInternal(int minCapacity) 
    13. { 
    14.     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); 
    15. }
    16.  
    17. private static int calculateCapacity(Object[] elementData, int minCapacity) 
    18. { 
    19.     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) 
    20.     { 
    21.         return Math.max(DEFAULT_CAPACITY, minCapacity); }
    22.         return minCapacity; 
    23.     }
    24.  
    25. private void ensureExplicitCapacity(int minCapacity) 
    26. {
    27.     modCount++; 
    28.     // overflow-conscious code
    29.     if (minCapacity - elementData.length > 0) 
    30.         grow(minCapacity); 
    31. }
    32.  
    33. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    34. private void grow(int minCapacity) 
    35. { 
    36.     // 获取旧空间大小 
    37.     int oldCapacity = elementData.length;
    38.  
    39.     // 预计按照1.5倍方式扩容 
    40.     int newCapacity = oldCapacity + (oldCapacity >> 1); 
    41.  
    42.     // 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容 
    43.     if (newCapacity - minCapacity < 0) 
    44.     newCapacity = minCapacity; 
    45.  
    46.     // 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小 
    47.     if (newCapacity - MAX_ARRAY_SIZE > 0)
    48.     newCapacity = hugeCapacity(minCapacity); 
    49.  
    50.     // 调用copyOf扩容 
    51.     elementData = Arrays.copyOf(elementData, newCapacity); 
    52. }
    53.  
    54. private static int hugeCapacity(int minCapacity) 
    55. { 
    56.     // 如果minCapacity小于0，抛出OutOfMemoryError异常 
    57.     if (minCapacity < 0) 
    58.         throw new OutOfMemoryError(); 
    59.  
    60.     return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; 
    61. }
    【 总结 】
    1. 检测是否真正需要扩容，如果是调用 grow 准备扩容
    2. 预估需要库容的大小
    • 初步预估按照1.5倍大小扩容
    • 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
    • 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
    3. 使用 copyOf 进行扩容

    5、使用示例

    5.1 扑克牌

    1. public class Card 
    2. {
    3.     public int rank; // 牌面值
    4.     public String suit; // 花色
    5.     @Override
    6.     public String toString() 
    7.     { 
    8.         return String.format("[%s %d]", suit, rank); 
    9.     } 
    10. }
    1. import java.util.List; 
    2. import java.util.ArrayList; 
    3. import java.util.Random;
    4.  
    5. public class CardDemo 
    6. {
    7.     public static final String[] SUITS = {"♠", "♥", "♣", "♦"}; // 买一副牌
    8.     private static List buyDeck() 
    9.     { 
    10.         List deck = new ArrayList<>(52); 
    11.         for (int i = 0; i < 4; i++) 
    12.         { 
    13.             for (int j = 1; j <= 13; j++) 
    14.             { 
    15.                 String suit = SUITS[i]; 
    16.                 int rank = j;
    17.                 Card card = new Card();
    18.                 card.rank = rank;
    19.                 card.suit = suit;
    20.                 deck.add(card); 
    21.             } 
    22.         }
    23.     return deck; 
    24. }
    25.  
    26. private static void swap(List deck, int i, int j) 
    27. { 
    28.     Card t = deck.get(i);
    29.     deck.set(i, deck.get(j));
    30.     deck.set(j, t); 
    31. }
    32.  
    33. private static void shuffle(List deck) 
    34. { 
    35.     Random random = new Random(20190905); 
    36.     for (int i = deck.size() - 1; i > 0; i--) 
    37.     { 
    38.         int r = random.nextInt(i); swap(deck, i, r); 
    39.     } 
    40. }
    41.  
    42. public static void main(String[] args) 
    43. {
    44.     List deck = buyDeck(); 
    45.     System.out.println("刚买回来的牌:"); 
    46.     System.out.println(deck); shuffle(deck); 
    47.     System.out.println("洗过的牌:"); 
    48.     System.out.println(deck); 
    49.     // 三个人，每个人轮流抓 5 张牌 
    50.     List> hands = new ArrayList<>(); 
    51.     hands.add(new ArrayList<>()); 
    52.     hands.add(new ArrayList<>()); 
    53.     hands.add(new ArrayList<>()); 
    54.     for (int i = 0; i < 5; i++) 
    55.     { 
    56.         for (int j = 0; j < 3; j++) 
    57.     { 
    58.         hands.get(j).add(deck.remove(0)); 
    59.     } 
    60. }
    61.  
    62.     System.out.println("剩余的牌:"); 
    63.     System.out.println(deck); 
    64.     System.out.println("A 手中的牌:"); 
    65.     System.out.println(hands.get(0)); 
    66.     System.out.println("B 手中的牌:"); 
    67.     System.out.println(hands.get(1)); 
    68.     System.out.println("C 手中的牌:"); 
    69.     System.out.println(hands.get(2)); 
    70. }
    71. }
            运行结果

     5.2 杨辉三角

    给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

    1. class Solution 
    2. {
    3.     // 杨辉三角
    4.     public List> generate(int numRows) 
    5.     {
    6.         List> out = new ArrayList>();
    7.         for (int i = 0; i < numRows; i++) 
    8.         {
    9.             List arr = new ArrayList();
    10.             for (int j = 0; j < i + 1; j++) 
    11.             {
    12.                 if (i == 0) 
    13.                 { // 第一层
    14.                     arr.add(1);
    15.                 } 
    16.                 else if (j == 0 || j == i)
    17.                 { // 第二层 + 下面层的最外面的两个数字
    18.                     arr.add(1);
    19.                 } 
    20.                 else 
    21.                 {
    22.                     List tmp = out.get(i - 1);
    23.                     arr.add(tmp.get(j - 1) + tmp.get(j)); // 计算
    24.                 }
    25.             }
    26.             out.add(arr);
    27.         }
    28.         return out;
    29.     }
    30. }

    6、顺序表的问题及思考

            1. 顺序表中间 / 头部的插入删除，时间复杂度为 O(N)
            2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
            3. 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100 ，满了以后增容到 200 ，我们再继续插入了5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。
            思考： 如何解决以上问题呢

  • 相关阅读:
    Python函数（1）
    大厂边缘组VS小厂核心组，要怎么选？
    C++算法：分发糖果
    Vue中如何进行本地存储（LocalStorage）
    C#，《数值算法：科学计算的艺术，Numerical Recipes: The Art of Scientific Computing》
    学生动漫网页设计模板下载你的名字 大学生HTML网页制作作品 简单漫画网页设计成品 dreamweaver学生网站模板
    Android简易音乐重构MVVM Java版-BottomNavigationView+viewpager主界面结构（十一）
    python 处理锯齿波信号
    毕业论文GPT说：
    什么是模型监控？（Valohai）
  • 原文地址：https://blog.csdn.net/weixin_51912875/article/details/125704015