• 顺序表和ArrayList

    什么是顺序表？

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

    模拟实现ArrayList的源码

    1. public class MyArrayList {
    2.     public int[] array;
    3.     public int usedSize;//记录有效数据
    4.     public static final int DEFAULT_CAPACITY=2;
    5.     public MyArrayList(){
    6.        this.array=new int[DEFAULT_CAPACITY];
    7.     }
    8.     //打印顺序表
    9.     public void display() {
    10.         for (int i = 0; i < this.usedSize; i++) {
    11.             System.out.print(this.array[i]);
    12.         }
    13.         System.out.println();
    14.     }
    15.     // 新增元素,默认在数组最后新增
    16.     //在数据结构中，每次添加数据前面都要有前驱信息，不能跳着放
    17.     public void add(int data) {
    18.         try{
    19.             if(isFull()){
    20.                 array= Arrays.copyOf(array,array.length*2);
    21.             }
    22.         }catch (NegativeArraySizeException e){
    23.             e.printStackTrace();
    24.         }
    25.         array[usedSize++]=data;
    26.     }
    27.     public boolean isFull(){
    28.         return usedSize==array.length;
    29.     }
    30.     public void isPosLegal(int pos){
    31.         if(pos<0||pos>usedSize){
    32.             throw new PosIndexNotLegal("pos下标不合法");
    33.         }
    34.     }
    35.     // 在 pos 位置新增元素
    36.     public void add(int pos, int data) {
    37.         try {
    38.             isPosLegal(pos);
    39.             //判断是否满了
    40.             if (isFull()){
    41.                 array=Arrays.copyOf(array,array.length*2);
    42.             }
    43.             for (int i = usedSize-1; i >=pos ; i--) {
    44.                 array[i+1]=array[i];
    45.             }
    46.             array[pos]=data;
    47.             usedSize++;
    48.         }catch (PosIndexNotLegal e){
    49.             e.printStackTrace();
    50.         }
    51.     }
    52.     // 判定是否包含某个元素
    53.     public boolean contains(int toFind) {
    54.         for (int i = 0; i < usedSize; i++) {
    55.             if(array[i]==toFind){
    56.                 return true;
    57.             }
    58.         }
    59.         return false;
    60.     }
    61.     // 查找某个元素对应的位置
    62.     public int indexOf(int toFind) {
    63.         for (int i = 0; i < usedSize; i++) {
    64.             if(array[i]==toFind){
    65.                 return i;
    66.             }
    67.         }
    68.         return -1;
    69.     }
    70.     // 获取 pos 位置的元素
    71.     public void checkGetPos(int pos){
    72.         if(pos<0||pos>=usedSize){
    73.             throw new PosIndexNotLegal("pos下标不合法");
    74.         }
    75.     }
    76.     public int get(int pos) {
    77.         /**
    78.         try {
    79.             checkGetPos(pos);
    80.         }catch (PosIndexNotLegal e){
    81.             //处理异常的代码
    82.             e.printStackTrace();
    83.         }
    84.         return array[pos];
    85.          */
    86.         checkGetPos(pos);
    87.         return array[pos];
    88.     }
    89.     // 给 pos 位置的元素设为 value
    90.     public void set(int pos, int value) {
    91.         checkGetPos(pos);
    92.         array[pos]=value;
    93.     }
    94.     //删除第一次出现的关键字key
    95.     public void remove(int key) {
    96.         int index=indexOf(key);
    97.         if(index==-1){
    98.             System.out.println("没有这个数字");
    99.             return;
    100.         }else {
    101.             for (int i = index; i < usedSize-1; i++) {
    102.                 array[i]=array[i+1];
    103.             }
    104.         }
    105.         //array[usedSize-1]=null如果是引用类型，要置为null，防止内存泄露
    106.         usedSize--;
    107.     }
    108.     // 获取顺序表长度
    109.     public int size() {
    110.         return usedSize;
    111.     }
    112.     // 清空顺序表
    113.     public void clear() {
    114.         /**
    115.         for (int i = 0; i < usedSize; i++) {
    116.             array[i]=null;
    117.         }
    118.         */
    119.         usedSize=0;
    120.     }
    121. }

     ArrayList的构造

    1.ArrayList()无参构造

    1.  public static void main(String[] args) {
    2.         ArrayList<Integer> arrayList=new ArrayList<>();//顺序表大小是0
    3.         arrayList.add(1);//大小变为10
    4.         arrayList.add(2);
    5.         //.........当添加到10个时，要再次扩容
    6.     }

     通过源码分析整个构造过程（按照我的箭头，从上到下分析扩容原理）

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

    2.ArrayList(int initialCapacity)  指定大小的构造方法

    1.  public static void main(String[] args) {
    2.        
    3.         ArrayList<Integer> arrayList=new ArrayList<>(15);
    4.     }

    3.ArrayList(Collection<? extends E> c) 利用Collection接口构造

    1. public static void main(String[] args) {       
    2.          /**
    3.          * 都实现了Collection接口
    4.          */
    5.         ArrayList<Integer> arrayList2=new ArrayList<>(15);
    6.         ArrayList<Integer> arrayList3=new ArrayList<>(arrayList2);
    7.         LinkedList<Integer>linkedList=new LinkedList<>();
    8.         ArrayList<Integer> arrayList4=new ArrayList<>(linkedList);
    9.     }

    ArristList的遍历

    1. public static void main(String[] args) {
    2.         List<String> list=new ArrayList<>();
    3.         list.add("javase");
    4.         list.add("javaee");
    5.         list.add("javaweb");
    6.         list.add("jvm");
    7.         list.add("测试课程");
    8.         /**
    9.          * 直接打印
    10.          */
    11.         System.out.println(list);
    12.         /**
    13.          * for循环
    14.          */
    15.         for (int i = 0; i < list.size(); i++) {
    16.             System.out.print(list.get(i)+" ");
    17.         }
    18.         System.out.println();
    19.         /**
    20.          * for each
    21.          * 冒号的左边是集合元素，冒号的右边是集合
    22.          */
    23.         for (String x: list) {
    24.             System.out.print(x+" ");
    25.         }
    26.         /**
    27.          *迭代器1
    28.          */
    29.         Iterator<String> it=list.iterator();
    30.         while (it.hasNext()){
    31.             System.out.print(it.next());
    32.         }
    33.         System.out.println();
    34.         /**
    35.          * 迭代器2
    36.          */
    37.         ListIterator<String> it2= list.listIterator();
    38.         while (it2.hasNext()){
    39.             System.out.print(it2.next());
    40.         }
    41.     }

     ArrayList的应用

    扑克牌（铁甲版本）

    1. import java.util.ArrayList;
    2. import java.util.List;
    3. import java.util.Random;
    4.  
    5. /**
    6.  * 一张扑克牌
    7.  */
    8. class Card{
    9.     public int number;
    10.     public String color;
    11.  
    12.     public Card(int number, String color) {
    13.         this.number = number;
    14.         this.color = color;
    15.     }
    16.  
    17.     @Override
    18.     public String toString() {
    19.         return ""+number+" "+color;
    20.     }
    21. }
    22.  
    23. /**
    24.  * 一套扑克牌
    25.  */
    26. public class CardDemo {
    27.  
    28.     public static final String[] colors=new String[]{"♥","♠","♦","♣"};//花色
    29.  
    30.     /**
    31.      * 准备一套扑克牌
    32.      * @return
    33.      */
    34.     public List<Card> cardList(){
    35.         List<Card> cards=new ArrayList<>();
    36.         for (int i = 1; i <=13; i++) {
    37.             for (int j = 0; j < 4; j++) {
    38.                 Card card=new Card(i,colors[j]);
    39.                 cards.add(card);
    40.             }
    41.         }
    42.         return cards;
    43.     }
    44.  
    45.     /**
    46.      * 洗牌
    47.      * @param cards
    48.      * @param i
    49.      * @param j
    50.      */
    51.     private void swap(List<Card> cards,int i,int j){
    52.         Card tmp=cards.get(i);
    53.         cards.set(i,cards.get(j));
    54.         cards.set(j,tmp);
    55.     }
    56.     public void washCard(List<Card> cards){
    57.         Random random=new Random();
    58.         for (int i = cards.size()-1; i >0 ; i--) {
    59.                 int index= random.nextInt(i);;
    60.                 swap(cards,i,index);
    61.         }
    62.     }
    63.     /**
    64.      * 分牌，每人5张
    65.      */
    66.     public List<List<Card>> DistributeCard(List<Card> cards){
    67.         List<Card>person1=new ArrayList<>();
    68.         List<Card>person2=new ArrayList<>();
    69.         List<Card>person3=new ArrayList<>();
    70.         List<List<Card>> persons=new ArrayList<>();//persons里面的元素是person，所以<>放的元素是List<Card>
    71.         /**
    72.          * 给persons数组里面放3个人，每个人又是一个数组，也就是二维数组
    73.          */
    74.         persons.add(person1);
    75.         persons.add(person2);
    76.         persons.add(person3);
    77.         for (int i = 0; i < 5; i++) {//分5次
    78.             for (int j = 0; j < 3; j++) {//3个人
    79.                 Card card= cards.remove(0);//不断删除0位置的牌，从0位置取牌
    80.                 persons.get(j).add(card);
    81.             }
    82.         }
    83.         return persons;
    84.     }
    85. }
    1. import java.util.List;
    2.  
    3. public class Test {
    4.     public static void main(String[] args) {
    5.         CardDemo cardDemo=new CardDemo();
    6.         List<Card>ret=cardDemo.cardList();
    7.         System.out.println("洗牌前");
    8.         System.out.println(ret);
    9.         System.out.println("洗牌后");
    10.         cardDemo.washCard(ret);
    11.         System.out.println(ret);
    12.         List<List<Card>> ret2=cardDemo.DistributeCard(ret);
    13.         for (int i = 0; i <3; i++) {
    14.             System.out.println("第"+(i+1)+"个人的牌"+ret2.get(i));
    15.         }
    16.     }
    17. }

    顺序表的思考

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

    上面问题可以用链表来解决

    链表：是以链式的形式进行存储

    顺序表：是以顺序的形式进行存储 

  • 相关阅读:
    法定代表人和股东是什么关系
    Leetcode2937. 使三个字符串相等
    Redis数据类型-需求实战记录
    【校招VIP】“推推”产品项目课程:产品的脑图分析
    视频直播美颜SDK算法代码解析
    塑胶材料检测对激光焊机的作用
    thingsboard3.4版本之OTA升级
    15.Redis系列之使用Redisson分布式锁实现秒杀
    java应聘面试自我介绍范文
    超详细的Python安装和环境搭建教程
  • 原文地址：https://blog.csdn.net/weixin_61427900/article/details/125536309