当前位置：网站首页>ArrayList与顺序表

ArrayList与顺序表

2022-06-30 10:10:00 【如风暖阳】

在这里插入图片描述

️前言️

本篇文章是讲数据结构中一个重要部分，会被经常使用，也是链表数据结构部分的铺垫内容。

博客主页：【如风暖阳】
精品Java专栏【JavaSE】、【备战蓝桥】、【JavaEE初阶】、【MySQL】、【数据结构】
欢迎点赞收藏留言评论私信必回哟

本文由 【如风暖阳】 原创，首发于 CSDN

博主将持续更新学习记录收获，友友们有任何问题可以在评论区留言

博客中涉及源码及博主日常练习代码均已上传码云(gitee)、GitHub

内容导读

ArrayList与顺序表

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。

线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述

2.顺序表

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

据的增删查改,其实，说人话就是高级一点的数组，在这个高级数组上能完成一些功能.

那么这个高级的数组到底长啥样呢，让我们一起来看看它的真面目

在这里插入图片描述

其实将它形象化以后它也就长这样，就是比普通的数组多了一个元素——usedSize,用来存放有效数据个数.

下面我们用代码来造出这个顺序表：

public class MyArrayList {
    
    public int[] elem;//数组
    public int usedSize;//有效数据个数 左边这两者就是在堆区形成了我们的顺序表
    public static final int DEFAULT_CAPACITY=5;;//DEFAULT_CAPACITY是顺序表数组的容量，将其存放在方法区，不属于对象

    public MyArrayList() {
    //构造方法将顺序表实例化
        this.elem = new int[DEFAULT_CAPACITY];
        //this.usedSize = 0;默认为0 写不写都可
    }
}

这是这个顺序表所要实现的功能（接口）：

public void display() {
     } // 打印顺序表 
public void add(int pos, int data) {
     } // 在 pos 位置新增元素 
public boolean contains(int toFind) {
     return true; }// 判定是否包含某个元素 
public int search(int toFind) {
     return -1; }// 查找某个元素对应的位置
public int getPos(int pos) {
     return -1; } // 获取 pos 位置的元素value
public void setPos(int pos, int value) {
     } // 给 pos 位置的元素设为key
public void remove(int toRemove) {
     } //删除第一次出现的关键字
public int size() {
     return 0; } // 获取顺序表长度 
public void clear() {
     }// 清空顺序表

接下来为这些接口的具体实现（顺序上下一致）

1.打印顺序表（两种方法）

import java.util.Arrays;//第一种方法
	public void display() {
      //导入until包，然后直接用Arrays.toString（）来将顺序表打印
        System.out.println(Arrays.toString(this.elem));
    }


    public void display() {
    //第二种方法
        for (int i = 0; i < this.usedSize; i++) {
    //设置循环依次打印顺序表中的元素
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

2.在 pos 位置新增元素

完成这一项工作需要分三步：

（1）判断pos位置是否合法

（2）挪数据（pos位置以后的数据给新元素腾地方，整体后移闪出一个空地）

（3）放数据（新来的老大就坐这里了）

import java.util.Arrays;
	private boolean isFull() {
    //判断顺序表是否已满
        return this.usedSize==this.elem.length;//相等返回true，否则返回false
    }    
	public void add(int pos,int data) {
    
        if(pos<0||pos>this.usedSize) {
    //当pos为负数或者大于有效个数时，位置不合法直接返回
            return;
        }
        if (isFull()) {
    //如果顺序表已满，需要进行增容
            this.elem = Arrays.copyOf(this.elem, 2*elem.length);//新数组需要将原数组先进性拷贝，然后其容量变为原来2倍
        }
        for (int i = usedSize-1; i >=pos; i--) {
    //设置循环，从后边开始往前移，到pos位置终止循环，闪出一个位子
            this.elem[i+1]=this.elem[i];
        }
        this.elem[pos]=data;//放数据
        this.usedSize++;//有效个数+1
    }

3.判定是否包含某个元素

    public boolean contains(int toFind) {
    
        for (int i = 0; i < this.usedSize; i++) {
    //遍历顺序表挨个比对，相同返回true
            if(toFind==this.elem[i]) {
    
                return true;
            }
        }
        return false;//遍历完成仍然没有return，就返回false
    }

4.查找某个元素对应的位置

    public int search(int toFind) {
    
        for (int i = 0; i < this.usedSize; i++) {
    //与3其实一样，挨个比对，找到返回其角标
            if(toFind==this.elem[i]) {
    
                return i;
            }
        }
        return -1;//没找到就返回-1，因为数组角标无-1，-1即代表没找到
    }

5.获取 pos 位置的元素

    public int getPos(int Pos) {
    
        if(this.usedSize==0) {
    //顺序表为空直接返回-1
            return -1;
        }
        if(Pos<0||Pos>this.usedSize-1) {
    //pos位置不合法，直接返回-1（合法位置范围[0,this.usedSize-1]）
            return -1;
        }
        return this.elem[Pos];
    }

6.给 pos 位置的元素设为

    private boolean isEmpty() {
    
        return this.usedSize == 0;
    }
	public void setPos(int pos, int value) {
    
        if(pos < 0 || pos >= this.usedSize) {
    
            System.out.println("pos不合法！");
            return;
        }
        if(isEmpty()) {
    
            System.out.println("顺序表为空！");
            return;
        }
        this.elem[pos] = value;
    }

7.删除第一次出现的关键字

    private boolean isEmpty() {
    
        return this.usedSize == 0;
    }
	public void remove(int toRemove) {
    
        if(isEmpty()) return;
        int index = this.search(toRemove);//search方法在4中实现
        if(index == -1) {
    
            System.out.println("没有你要删除的数字");
            return;
        }
        for (int i = index; i < this.usedSize-1; i++) {
    //该关键字后边的数据整体前移，将其覆盖掉
            this.elem[i] = this.elem[i+1];
        }
        this.usedSize--;
    }

8.获取顺序表长度

    public int size() {
    
        return this.usedSize;
    }

9.清空顺序表

    public void clear() {
    
        this.elem=null;//JVM在回收内存时，当该对象没有人在引用它的时候，这个对象才会被回收，将this.elem置为空，则数组将没有对象引用，自动被JVM回收
        this.usedSize = 0;
    }

3. ArrayList

ArrayList底层是一段连续的空间，并且可以动态扩容，其实就是一个动态类型的顺序表

3.1 ArrayList的构造

方法解释
ArrayList()无参构造
ArrayList(Collection<? extends E> c)利用其他Collection构建ArrayList
ArrayList(int initialCapacity)指定顺序表初始容量

代码示例：

public static void main(String[] args) {
    
        // ArrayList创建，推荐写法
        // 构造一个空的列表
        List<Integer> list1=new ArrayList<>();
        List<Integer> list2=new ArrayList<>(10);
        list2.add(1);
        list2.add(2);
        list2.add(3);
        // list3构造好之后，与list2中的元素一致
        ArrayList<Integer> list3=new ArrayList<>(list2);
}

3.2 ArrayList常见操作

大部分操作方法与2中顺序表相同。

方法解释
boolean add(E e)尾插 e
void add(int index, E element)将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)尾插 c 中的元素
E remove(int index)删除 index 位置元素
boolean remove(Object o)删除遇到的第一个 o
E get(int index)获取下标 index 位置元素
E set(int index, E element)将下标 index 位置元素设置为 element
void clear()清空
boolean contains(Object o)判断 o 是否在线性表中
int indexOf(Object o)返回第一个 o 所在下标
int lastIndexOf(Object o)返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)截取部分 list

3.3 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.println(list.get(i)+" ");
        }
        System.out.println();
        for(Integer integer:list) {
    
            System.out.println(integer+" ");
        }
        System.out.println();
        //迭代器遍历
        Iterator<Integer> it=list.listIterator();
        while (it.hasNext()) {
    
            System.out.println(it.next()+" ");
        }
        System.out.println();
}

迭代器起一行一行扫描内容的作用，代码it.next()的作用为获取本行内容，并移步至下一行。

3.4 ArrayList的扩容机制（源码分析）

 public static void main(String[] args) {
    
        ArrayList<Integer> list=new ArrayList<>();//顺序表大小是0
        list.add(1);//大小变为了10
        list.add(2);
        list.add(3);
        //。。。。。。。。当十个放慢以后，需要扩容，扩容采取的是1.5倍的扩容方式
}

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容：以下是ArrayList源码中扩容方式.

我们先来看ArrayList的构造方法：
在这里插入图片描述
此时给数组分配的大小为0，也就是说在一开始实例化时，数组容量为0

在调用add方法时，会根据目前的容量判断是否需要增容（如果增容增1.5倍）
在这里插入图片描述
【总结】

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

4. 使用实例（扑克牌）

一副牌（除大小王），现在需要进行的操作是先买牌，进行洗牌，然后三个人轮流从牌堆中摸五张牌，该实例是对ArrayList的总结与运用。

CardDemo类：

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Card {
    
    public int rank;//数字
    public String suit;//花色

    public Card(int rank, String suit) {
    
        this.rank = rank;
        this.suit = suit;
    }

    //重写打印方法 数字+花色
    @Override
    public String toString() {
    
        return ""+suit+" "+rank;
    }
}
public class CardDemo {
    
    public static final String[] suits={
    "","","",""};

    /** * 买扑克方法 * @return 扑克 */
    public List<Card> buyDeskCard() {
    
        List<Card> cards=new ArrayList<>();
        //13个数字，每个数字四张不同花色
        for (int i = 1; i <=13 ; i++) {
    
            for (int j = 0; j < 4; j++) {
    
                Card card=new Card(i,suits[j]);
                cards.add(card);
            }
        }
        return cards;
    }

    /** * 洗牌方法 */
    public void shuffle(List<Card> cards) {
    
        for (int i = cards.size()-1; i >0 ; i--) {
    
            Random random=new Random();
            int index=random.nextInt(i);
            swap(cards,index,i);
        }
    }

    /** * 交换两张牌 * @param cards * @param i * @param j */
    private void swap(List<Card> cards,int i,int j) {
    
        Card tmp=cards.get(i);
        cards.set(i,cards.get(j));
        cards.set(j,tmp);
    }

    /** * 摸牌方法 * @param cards 牌堆 * @return 最后的摸牌清空 */
    public List<List<Card>> test(List<Card> cards) {
    
        List<Card> hand1 = new ArrayList<>();
        List<Card> hand2 = new ArrayList<>();
        List<Card> hand3 = new ArrayList<>();
        List<List<Card>> hands = new ArrayList<>();
        hands.add(hand1);
        hands.add(hand2);
        hands.add(hand3);
        //3个人 每个人轮流抓5张牌
        for (int i = 0; i < 5; i++) {
    
            for (int j = 0; j < 3; j++) {
    
                //remove方法返回值为牌堆的第一张牌，并且会把这张牌从牌堆中清除
                Card card = cards.remove(0);
                hands.get(j).add(card);
            }
        }
        return hands;
    }
}

Test类：

import java.util.List;

public class Test {
    
    public static void main(String[] args) {
    
        CardDemo cardDemo=new CardDemo();
        List<Card> ret=cardDemo.buyDeskCard();
        System.out.println(ret);
        System.out.println("洗牌：");
        cardDemo.shuffle(ret);
        System.out.println("摸牌：");
        List<List<Card>> ret2=cardDemo.test(ret);
        for (int i = 0; i < ret2.size(); i++) {
    
            System.out.println("第"+(i+1)+"个人的牌："+ret2.get(i));
        }
        System.out.println("剩余的牌:");
        System.out.println(ret);
    }
}

运行结果：
在这里插入图片描述

️最后的话️

总结不易，希望uu们不要吝啬你们的哟(＾Ｕ＾)ノ~ＹＯ！！如有问题，欢迎评论区批评指正
在这里插入图片描述

原网站

版权声明
本文为[如风暖阳]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_60856948/article/details/125493627

边栏推荐

猜你喜欢

随机推荐