手把手教你如何实现List—

前言：

线性表

顺序表

接口的实现

一. 打印顺序表

二.新增元素,默认在数组最后新增

三.在 pos 位置新增元素

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

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

六.获取 pos 位置的元素

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

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

九.获取顺序表长度

十.清空顺序表

ArrayList的遍历

ArrayList的问题及思考

前言：

什么是List？

在集合框架中，List是一个接口，继承自Collection。

站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

List中提供了好的方法，具体如下：

注意：List是个接口，并不能直接用来实例化。
如果要使用，必须去实例化List的实现类。在集合框架中，ArrayList和LinkedList都实现了List接口。

本篇我们开始 ArrayList的学习

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...

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

顺序表

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

接口的实现

先初始化数组

有效数字现在为useSize

模拟实现接口里面的所有的功能也基本上就学会了顺序表的所有功能

实现在MyArrayList这个类中重写

一. 打印顺序表

打印顺序表比较简单，知道它的userSize，遍历一遍就可以

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

二.新增元素,默认在数组最后新增

思路：直接找到userSize位置，直接赋值就行有效数组userSize为4

假如我们需要添加5，直接在下标为4的位置上赋值

添加完userSize++

考虑问题要全，如果数组满了，我们需要给它扩容已被才可以添加

所有得先判断是否数组满了，如果满了先扩容再添加

代码实现：

public void add(int data) {
        //判断
        if(useSize == 5) {
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        //添加
        elem[useSize] = data;
        useSize++;
    }

效果：

三.在 pos 位置新增元素

在1下标添加11

应该把1下标后面的元素往后面移动从userSzie-1下标开始向右移动

并且得先从最右边的元素开始移动

最后userSize++；

考虑情况：

另外pos下标值不能小于0或者大于usersize

代码实现：

 public void add(int pos, int data) {
        //先检查是否数组满了吗？
        if(useSize == 5) {
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        // 判断pos是否合法
        if(pos < 0 || pos > useSize) {
            //抛出异常
            throw new PosException("pos未知不合法" + pos);
        }
        for (int i = useSize - 1; i >= pos ; i--) {
            elem[i+1] = elem[i];
        }
        elem[pos] = data;
        useSize++;
    }

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

遍历整个数组，再判断

代码实现：

   public boolean contains(int toFind) {
        for (int i = 0; i < useSize; i++) {
            if(elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

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

代码实现：

   public int indexOf(int toFind) {
        for (int i = 0; i < useSize; i++) {
            if(elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

六.获取 pos 位置的元素

这里的pos不能等于userSize了，否则越界了

代码实现：

   public int get(int pos) {
         判断pos是否合法
        if(pos < 0 || pos >= useSize) {
            //抛出异常
            throw new PosException("pos未知不合法" + pos);
        }
        return elem[pos];
    }

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

代码实现：

 public void set(int pos, int value) {
        // 判断pos是否合法
        if(pos < 0 || pos > useSize) {
            //抛出异常
            throw new PosException("pos未知不合法" + pos);
        }
        elem[pos] = value;
    }

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

先判断顺序表是否为空空的不可以删除的

删除结束userSize--

代码实现：

    public void remove(int toRemove) {
        if(useSize == 0){
           throw new EmptyException("顺序表为空");
        }
        //获取toRemove下标
        int index = indexOf(toRemove);
        for (int i = index; i < useSize - 1 ; i++) {
            elem[i] = elem[i+1];
        }
        useSize--;
    }

九.获取顺序表长度

 public int size() {
        return useSize;
    }

十.清空顺序表

 public void clear() {
        useSize = 0;
    }

以上基本上就是顺序表所有的基本操作

ArrayList的遍历

一：直接打印

二：for循环遍历

三. for each遍历

四.使用迭代器

ArrayList的问题及思考

1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。