数据结构-顺序表

package arraylist;

interface IList {
    // 新增元素,默认在数组最后新增
    void add(int data);

    // 在 pos 位置新增元素
    void add(int pos, int data);

    // 判定是否包含某个元素
    boolean contains(int toFind);

    // 查找某个元素对应的位置
    int indexOf(int toFind);

    // 获取 pos 位置的元素
    int get(int pos);

    // 给 pos 位置的元素设为 value
    void set(int pos, int value);

    //删除第一次出现的关键字key
    void remove(int toRemove);

    // 获取顺序表长度
    int size();

    // 清空顺序表
    void clear();

    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    void display();

    //判断数组是否满
    Boolean isFull();
}

package arraylist;

public class MyArrayList implements IList{
    public int[] elem;//定义一个elem数组
    int usedSize;//记录数组中所存的个数

    public MyArrayList() {
        this.elem = new int[10];
    }

    @Override
    public void add(int data) {

    }

    @Override
    public void add(int pos, int data) {

    }

    @Override
    public boolean contains(int toFind) {
        return false;
    }

    @Override
    public int indexOf(int toFind) {
        return 0;
    }

    @Override
    public int get(int pos) {
        return 0;
    }

    @Override
    public void set(int pos, int value) {

    }

    @Override
    public void remove(int toRemove) {

    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void clear() {

    }

    @Override
    public void display() {

    }

    @Override
    public Boolean isFull() {
        return null;
    }
}

package arraylist;

//异常类的处理 更多内容请看专栏JavaSE语法
public class PosNotLegalException extends RuntimeException {
    public PosNotLegalException() {
    }

    public PosNotLegalException(String msg) {
        super(msg);
    }
}

package arraylist;

public class Test {
    public static void main(String[] args) {
        //实现之后 有两种方法来使用此顺序表
        MyArrayList myArrayList = new MyArrayList();
        IList iList = new MyArrayList();
    }
}

各个方法的实现

判断数组是否满

@Override
public Boolean isFull() {
    return usedSize == elem.length;
}

在数组最后新增元素

1、先要判断数组是否满了

2、如果满了进行扩容

3、没满则elem[usedSize]=data;

@Override
public void add(int data) {
    if (isFull()) {
        this.elem = Arrays.copyOf(elem, 2 * elem.length);
    } else this.elem[usedSize] = data;
    this.usedSize++;
 }

在pos位置插入元素

1、先判断pos位置是否合法

2、再判断数组元素是否已满

3、找到pos位置，再移动元素（从最后一个元素向前遍历）elem[i]=elem[i-1];i>=pos+1;

4、插入元素elem[pos]=data;

@Override
public void add(int pos, int data) {
    try {
        checkPosOfAdd(pos);
    } catch (PosNotLegalException e) {
        e.printStackTrace();
    }
    if (isFull()) {
        this.elem = Arrays.copyOf(elem, 2 * elem.length);
    }
    for (int i = this.usedSize - 1; i >= pos; i--) {
        this.elem[i] = this.elem[i - 1];
    }
    this.elem[pos] = data;
    this.usedSize++;
}

//该方法用来判断插入元素的pos位置是否合法
private void checkPosOfAdd(int pos) throws PosNotLegalException {
    if (pos < 0 || pos > usedSize)
        throw new PosNotLegalException("pos位置不合法");
}

判断是否包含某个元素

@Override
public boolean contains(int toFind) {
    for (int i = 0; i < usedSize; i++) {
        if (this.elem[i] == toFind)
            return true;
    }
    return false;
}

查找某个元素对应的位置

1、遍历找到这个元素并返回对应的位置

2、找不到返回-1

@Override
public int indexOf(int toFind) {
    for (int i = 0; i < usedSize; i++) {
        if (this.elem[i] == toFind)
            return i;
    }
    return -1;
}

获取/改变pos位置的元素

先判断pos位置是否合法

@Override
public int get(int pos) {
    try {
        checkPosGetAndSet(pos);
    } catch (PosNotLegalException e) {
        e.printStackTrace();
    }
    return this.elem[pos];
}

@Override
public void set(int pos, int value) {
    try {
        checkPosGetAndSet(pos);
    } catch (PosNotLegalException e) {
        e.printStackTrace();
    }
    this.elem[pos] = value;
}

private void checkPosGetAndSet(int pos) throws PosNotLegalException {
    if (pos < 0 || pos >= usedSize)
        throw new PosNotLegalException("get/set pos位置不合法");
}

删除第一次出现的元素

1、先找到这个元素所在的位置

2、再从这个位置开始往后进行遍历elem[i]=elem[i+1];i<usedSize-1;

@Override
public void remove(int toRemove) {
    int pos = indexOf(toRemove);
    if (pos == -1) {
        System.out.println("没有找到要删除的元素!");
        return;
    }
    for (int i = pos; i < usedSize - 1; i++) {
        this.elem[i] = this.elem[i + 1];
    }
    usedSize--;
}

获取顺序表的长度

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

清空顺序表

引用类型和基本数据类型不一样，引用类型会引用一个对象，如果只是将usedSize置为0，里面的对象还在引用着之前的对象—"内存泄漏"（本来不需要的对象还有元素在引用）。

@Override
public void clear() {
//    for (int i = 0; i < usedSize; i++) {
//        elem[i]=null;
//    }
    this.usedSize = 0;
}

打印顺序表

@Override
public void display() {
     for (int i = 0; i < this.usedSize; i++) {
        System.out.print(this.elem[i] + " ");
    }
    System.out.println();
}

注意事项

使用usedSize来记录当前有效数据个数，在增加了元素或删除了元素时要随时对usedSize++/--。

使用顺序表

以后在使用顺序表的时候，不可能再重头搭建一个顺序表。在Java当中已经实现了一个顺序表，我们只需来使用这个集合类。

此时仍然有两种方法来使用

public static void main(String[] args) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
}
通过list访问的方法比通过arrayList访问的方法少，因为前者只能访问接口中特有的方法，而后者为对象可以访问arrayList自己的方法。

认识构造方法

无参构造

只是一个数组引用

数组的长度为0

当调用一个不带参数的构造方法的时候，并没有给数组分配大小，数组的长度为0。那为什么可以add元素？

当调用不带参数的构造方法进行add时，第一次add会分配大小为10的内存。扩容机制为1.5倍扩容。

利用其他Collection构建ArrayList

1、ArrayList是实现了Collection接口的

2、参数的类型是当前arrayList2指定的泛型类型本身

指定顺序表初始容量

初始化指定数组大小

ArrayList常见操作

ArrayList的遍历

public class Test1 {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(10);
        arrayList.add(3);
        arrayList.add(9);
        arrayList.add(7);
        arrayList.add(23);

        for (int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i) + " ");
        }
        System.out.println();
        System.out.println("================");

        for (Integer x : arrayList) {
            System.out.print(x + " ");
        }
        System.out.println();
        System.out.println("================");

        Iterator<Integer> it = arrayList.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        System.out.println();
        System.out.println("================");

        ListIterator<Integer> it1 = arrayList.listIterator();
        while (it1.hasNext()) {
            System.out.print(it1.next() + " ");
        }
        System.out.println();
        System.out.println("================");

        //从指定位置开始打印（倒着打印）
        ListIterator<Integer> it2 = arrayList.listIterator(arrayList.size());
        while (it2.hasPrevious()) {
            System.out.print(it2.previous() + " ");
        }
        System.out.println();
        System.out.println("================");
    }
}

顺序表的优缺点

优点：在给定下标的情况下，访问速度比较快-O(1)。适用于经常进行下标查找或更新的操作。

缺点：

对于ArrayList来说不方便插入和删除因为要移动数组元素，最坏情况下，0下标插入，得移动所有元素，删除0下标也得移动所有元素。
扩容可能会浪费空间。假设现在100个长度放满了，还有一个元素没放，假设此时扩容，多了50个，但是实际只需要一个。

原文地址：https://blog.csdn.net/2301_80141037/article/details/142351787

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【Python】快速判断两个commit 是否存在cherry-pick 关系
下一篇：Kettle的安装及简单使用

【Android】使用Room数据库解决本地持久化
Android数据库的使用
阅读更多2024-09-24
MySQL篇（管理工具）
e 选项可以在MySQL客户端执行SQL语句，而不用连接到MySQL数据库再执行，对于一些批处理脚本，这种。执行上述指令，会出错，数据不能完成备份，原因是因为我们所指定的数据存放目录/root，MyS
阅读更多2024-09-24
丢失照片/消息/文件，当发现没有备份 Android 手机数据时急救方法
当人们发现他们没有备份 Android 手机数据时，通常为时已晚。但是，我们都不想永久丢失珍贵的照片，消息和其他文件。这就是为什么您应该检查遵循 5 大免费 Android 数据恢复工具和最佳替代
阅读更多2024-09-24
力扣 —— 删除有序数组中的重复项
两个指针，一个是游标的功能，负责遍历整个数组，一个是定位器的功能，如果有相等的则表示定位器目前指向的元素是重复的，定位器不动，等待游标往下找到不重复的数填充进来，因为游标会遍历整个数组且总是比定位器快
阅读更多2024-09-24
k8s服务发布
为某个节点添加标签 Label在 deployment 或其他控制器中指定将 Pod 部署到该节点该示例为 my-service:80 即可访问到具有 app=nginx 标签的 Pod 的80
阅读更多2024-09-24
Python 去掉文件后缀名
今天遇到了一个问题，去掉文件的后缀名，这里特来对这个问题记录一下。
阅读更多2024-09-24
C++二叉搜索树
二叉搜索树的概念二叉搜索树中可以⽀持插⼊相等的值，也可以不支持插入相等的值，具体看使用场景定义总得来说二叉搜索树他的左子树和根还有右子树的值形成一个阶梯状。
阅读更多2024-09-24
uniapp打包自动上传小程序后台
5、package.json中修改打包命令。3、将生成的密钥放置到项目根目录。6、打包运行，自动上传成功。
阅读更多2024-09-24
Ubuntu的基本用法与指令（为后面学习ROS打基础）
Ubuntu的基本用法与指令
阅读更多2024-09-24
数据结构与算法——Java实现 15.习题——判断回文链表
给你一个单链表的头节点head，请你判断该链表是否为回文链表如果是，返回true；否则，返回false。
阅读更多2024-09-24