数据结构之顺序表的模拟实现

 💕"世事犹如书籍，一页页被翻过去。人要向前看，少翻历史旧账。"💕

作者：Mylvzi 

 文章主要内容：数据结构之顺序表的模拟实现 

 一.线性表

1.概念

线性表(liner list)是n个具有相同特性元素的有限序列的集合

相同特性指的是一个线性表内部存储的数据类型要都是相同的，可以都是Integer，String也可以是其他的引用类型

常见的线性表有：顺序表，链表，栈，队列

2.性质

  线性表最大特点在于他是一种连续存储数据的结构，其在逻辑上一定是连续的，但是物理上不一定连续，主要是因为线性表既可以通过数组表示，又可以通过链表实现 

二.顺序表(ArrayList)

1.概念：

  顺序表是使用物理地址连续的内存存储数据的线性表

2.接口实现

 ArrayList中有很多内置的接口，不过这里我们先模拟实现一下

1.顺序表的结构

顺序表最大的特点是它使用"物理地址连续"的内存进行数据的存储，在我们学习过的知识中，数组的存储刚好满足顺序表的特点

    // 结构
    public int[] elem;// 使用数组来存储数据
    public int usedsize;// 有效数据个数
    
    // 初始化顺序表
  
    // 默认大小
    public static final int DEFAULT_SIZE = 10;
    
    public MyArrayList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    
    // 用户指定数组大小
    public MyArrayList(int initCapacity) {
        this.elem = new int[initCapacity];
    }

2.顺序表的添加

  顺序表的添加就是在顺序表中新增一个数据，但是插入的位置要分类讨论，大致上可分为两类：

• 默认插入:在 顺序表的末尾进行数据的插入
• 在指定位置进行插入 

1.默认插入 

  注意在插入数据这样的操作中，要考虑你要插入的容器的容量是否达到最大值，如果达到最大值需要进行扩容，否则就会发生越界访问

    // 默认插入
    public void add(int data) {
        // 插入之前要先检查是否需要扩容
        if(isFull()) {
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        
        // 插入
        this.elem[usedsize] = data;
        this.usedsize++;
        
    }
    
    public boolean isFull() {
        // 如果有效的数据个数和数组的长度一致  扩容
        return this.elem.length == usedsize;
    }

2.在指定位置插入数据

要在指定位置插入数据需要考虑的是原有的位置已经存在数据了，要想插入新的数据，就要将插入位置之后的所有元素都往后挪动

图解：

代码实现:

    // 在指定位置进行插入
    public void addPos(int pos,int data) {
        // 检查pos是否合法
        if(pos < 0 || pos > this.usedsize) {
            throw new posOutOfBoundException(pos + "位置不合法");
        }
 
        if(isFull()) {
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        
        // 挪动数据
        for (int i = this.usedsize-1; i >= pos; i--) {
            this.elem[i+1] = this.elem[i];
        }
        
        // 插入数据
        this.elem[pos] = data;
        this.usedsize++;
    }

注意:在pos位置插入数据的时候要检查pos是否合法，即不能产生越界访问 

 

3.判断顺序表中是否包含某个元素

  遍历顺序表，包含返回true；不包含，返回false

代码实现：

    public boolean contains(int key) {
        for (int i = 0; i < this.usedsize; i++) {
            if (this.elem[i] == key) {
                return true;
            }
        }
        
        // 没找到
        return false;
    }

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

如果数组包含某个元素，则返回其对应的下标

代码实现:
 

    public int indexOf(int key) {
        for (int i = 0; i < this.usedsize; i++) {
            if (this.elem[i] == key) {
                return i;
            }
        }
 
        System.out.println("数组不包含该元素");
        return -1;
    }

5.获取pos位置的元素

返回pos位置对应的元素 

代码实现

    public int get(int pos) {
        // 检查pos 的位置是否合法
        if(pos < 0 || pos >= this.usedsize) {
            throw new posOutOfBoundException(pos + "位置不合法");
        }
        
        return this.elem[pos];
    }

注意：此处要检查pos是否合法，这里的pos最大只能访问到usedSize-1的元素

6.给pos位置的元素设置为value

即更新pos位置的元素 

 代码实现

    public void set(int pos,int value) {
        // 检查pos 的位置是否合法
        if(pos < 0 || pos >= this.usedsize) {
            throw new posOutOfBoundException(pos + "位置不合法");
        }
        
        this.elem[pos] = value;
    }

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

遍历顺序表，找到值等于key的元素，删除他(只删除第一次出现的key)

但是该则么删除呢？将要删除的元素设置为0？这显然是行不通的，可以采用"数据覆盖"来进行数据的删除，即应该先找到要删除元素的位置，在从后往前进行数据的覆盖

图解

代码实现

    public void remove(int key) {
        // 1.获取key的pos
        int pos = indexOf(key);
        if (pos == -1) {
            System.out.println("没有你要删除的数据！");
            return;
        }
        
        // 2.挪动数据 进行删除    注意范围
        for (int i = pos; 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() {
        // 如果是引用类型 要一一置空
//        for (int i = 0; i < this.usedsize; i++) {
//            this.elem[i] = null;
//        }
        this.usedsize = 0;
    }

10.自定义异常

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 绿字
 */
public class posOutOfBoundException extends RuntimeException{
    public posOutOfBoundException() {
    }
 
    public posOutOfBoundException(String message) {
        super(message);
    }
}

三.ArrayList简介

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

源码:

注意:
1. ArrayList是以泛型的形式实现的，必须要先实例化

2.ArrayList实现了Cloneable接口，表明ArrayList是可以clone的

3.ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问

4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的

5，ArrayList是线程不安全的，在多线程中常使用Vector或者 CopyOnWriteArrayList

6.ArrayList底层是一段连续的内存空间，可以动态扩容

补充:

1.RandomAccess接口是Java中的"标记接口(marker interface)",用于指示列表是否能高效的进行数据的访问，对于ArrayList接口来说，他能够根据索引快速的进行数据的访问。但是对于链表(LinkedList)则没有被标记，因为链表通过索引访问数据的开销和时间复杂度很高

2.在Java中，Serializable也是一个标记接口（marker interface），用于表明一个类的对象可以被序列化。序列化指的是将对象转换为字节流，以便在网络上传输或保存到文件系统中，同时也可以通过反序列化将字节流重新转换为对象。

3.transient关键字：用于标记某些属性在序列化的时候应该被忽略，翻译为"短暂的，暂时的"

四. ArrayList使用

1.构造方法

1.无参构造  

ArrayList()

2.指定容量

ArrayList(int initCapacity)

3.利用其他集合构建 ArrayList

ArrayList(Collection c)

代码实现:

    public static void main(String[] args) {
 
        // 1.无参构造  推荐使用向上转型
        List list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
 
        System.out.println(list.toString());
 
        // 2.有参构造  设置容量为10
        List list2 = new ArrayList<>(10);
        list2.add(1);
        list2.add(2);
        list2.add(3);
 
        // 3.利用其他Collection 来构建ArrayList
        List list3 = new ArrayList<>(list2);
        System.out.println(list3.toString());// 输出1，2，3
 
    }

 2 ArrayList常见操作

ArrayList虽然提供的方法比较多，但是常用方法其实不多，使用到其他方法时可自行查阅

1.add

在ArrayList接口中，对应的也有两个add方法

1.bollean add(E e)  尾插e

2.void add(int index,E element)  将e插入到index位置

2.addAll

 boolean addAll(Collection c) 尾插 c 中的元素

这个方法适合将另一个集合中的元素尾插到创建的list中 

 

3.remove

 E remove(int index) 删除 index 位置元素，并返回删除的元素

boolean remove(Object o) 删除遇到的第一个 o 

 

4. get和set

E get(int index) 获取下标 index 位置元素

E set(int index, E element) 将下标 index 位置元素设置为 element

源码:

    public E get(int index) {
        rangeCheck(index);
 
        return elementData(index);
    }

    public E set(int index, E element) {
        rangeCheck(index);
 
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

5.clear

 void clear() 清空

    public void clear() {
        modCount++;
 
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
 
        size = 0;
    }

注意：GC指的是“垃圾回收”（Garbage Collection）是Java中用于处理使用过的内存资源的一种机制，用于提高效率

6.contains

 boolean contains(Object o) 判断 o 是否在线性表中

源码剖析 

 

7.indexOf

 int indexOf(Object o) 返回第一个 o 所在下标

 源码：

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

8.lastIndexOf

int lastIndexOf(Object o) 返回最后一个 o 的下标

源码:

    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

 9.subList

List subList(int fromIndex, int toIndex) 截取部分 list  并返回被截取的集合

3.ArrayList的遍历 

ArrayList的遍历方式有三种，for循环+下标，for each循环，迭代器

public static void main(String[] args) {
        List list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
 
        // 使用for循环+下标
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");// 输出1，2，3
        }
 
        // 使用for each循环
        for (Integer i : list) {
            System.out.print(i + " ");// 输出1，2，3
        }
 
        // 使用迭代器
        Iterator iterator = list.listIterator();
        while (iterator.hasNext()) {
            // iterator.next()用于获取list中的下一个元素
            // 注意 迭代器指针刚开始并不指向第一个元素
            System.out.print(iterator.next() + " ");// 输出1，2，3
        }
}

五.ArrayList的扩容机制(源码剖析)

 先来观察一下以下代码

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

这段代码有缺陷么？首先，我们知道ArrayList的构造方法有三种，不带参数的构造方法会自动为数组分配一个默认容量，这个默认容量是10，很明显，我们这里插入了100个元素，则必然会触发扩容机制，我们需要知道 ArrayList是怎么扩容的？以及他的扩容方式是否真的合理呢？

先来看ArrayList 的相关属性

观察一下源码中是如何触发扩容机制的

下面讲解扩容机制 

总结：

1.检测是否真的需要扩容，如果需要，使用grow进行扩容

2.预估需要的新内存大小

• 先按照原先1.5倍的大小进行扩容
•  如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
• 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败(判断扩容后的大小与> MAX_ARRAY_SIZE的关系)

3.使用copyOf进行扩容

六. ArrayList的一道题目

https://leetcode.cn/problems/pascals-triangle/

代码实现:

    class Solution {
        public List> generate(int numRows) {
            // 先创建一个List用于存放杨辉三角
            List> ret = new ArrayList<>();
 
            // 处理第一行
            List row = new ArrayList<>();
            row.add(1);
            ret.add(row);// 把第一行插入到ret中
 
            // 处理中间行
            for (int i = 1; i 
                List curRow = new ArrayList<>();
                curRow.add(1);// 每一行的第一个元素都是1
 
                // 处理中间元素
                // 先获取前一行  ret.get(i-1)
                List prevRow = ret.get(i-1);
                for (int j = 1; j < i ; j++) {
                    int x = prevRow.get(j-1)+prevRow.get(j);
                    curRow.add(x);
                }
                curRow.add(1);// 每一行的最后一个元素都是1
 
                // 最后不要忘记把curRow插入到ret中
                ret.add(curRow);
            }
            return ret;
        }
    }

七.ArrayList的问题及思考

1.

ArrayList的底层使用连续的内存空间，虽然数据检索的效率很高，但是对于数据的插入和删除操作均需要挪动大量的数据，效率较慢

2.

ArrayList的扩容机制是按照原数组大小的1.5倍进行扩容，但是有可能扩容之后造成大量空间的浪费(有很多空间并没有被使用)，同时增容需要拷贝数据，释放旧空间，会有不小的消耗

给大家留一个思考题：如何解决上述问题呢？答案请见下期博客！！！