概念

线性表的顺序存储结构，指的是用一段连续的存储单元依次存储线性表的数据元素。顺序表在存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时各元素之间不留空位。

优点：

• 空间利用率高，无需为表示表中元素之间的逻辑关系而额外增加存储空间。
• 根据下标查找的时候比较高效，时间复杂度为 O(1)。

缺点：

• 插入和删除复杂度高，需要额外移动大量元素，时间复杂度为 O(n)。
• 存储空间大小一旦申请就无法更改，难以确定需要的存储空间。
• 因为存储空间是连续的，所以对空间利用率不高，容易造成空间碎片。

通常会用数组来实现顺序表。

顺序表实现

抽象数据类型

public class SeqList {

    private int maxSize;
    private int usedSize;
    private Object[] arrayList;

    /**
     * 初始化
     *
     * @param maxSize
     */
    public SeqList(int maxSize) {
        this.maxSize = maxSize;
        this.usedSize = 0;

        arrayList = new Object[maxSize];
    }
}

插入

1. 如果插入位置不合理，抛出异常；
2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
3. 从最后一个元素开始向前遍历到第 i 个位置，分别将它们都向后移动一个位置；
4. 将要插入的元素填入位置 i 处；
5. 表长度加 1。

    /**
     * 插入元素
     *
     * @param index 插入位置
     * @param obj   插入对象
     * @throws Exception
     */
    public void insert(int index, Object obj) throws Exception {
        if (usedSize == maxSize) {
            throw new Exception("顺序表已满！");
        }

        if (index < 0 || index > usedSize) {
            // index > usedSize 是为了保证元素之间不出现空缺位置
            throw new Exception("插入位置不存在");
        }

        // 从 index + 1 到 userSize 位置的元素统统往后移动一个位置
        for (int i = usedSize; i > index; i--) {
            arrayList[i] = arrayList[i - 1];
        }

        arrayList[index] = obj;
        usedSize++;
    }

删除

1. 如果删除位置不合理，抛出异常；
2. 取出删除元素；
3. 从删除元素的位置开始向后遍历到最后一个元素，分别将它们向前移动一个位置；
4. 表长度减 1。

    /**
     * 删除第一个出现的元素
     *
     * @param index 删除元素的下标
     * @return 删除的元素
     */
    public Object delete(int index) throws Exception {
        if (usedSize == 0) {
            throw new Exception("顺序表为空！");
        }

        if (index < 0 || index >= usedSize) {
            throw new Exception("删除位置不存在！");
        }

        // 先把要返回的元素取出来，免得待会删除以后想返回找不到了
        Object obj = arrayList[index];

        // 从index + 1 到 userSize 的元素往前移动一个位置
        for (int i = index; i < usedSize; i++) {
            arrayList[i] = arrayList[i + 1];
        }

        usedSize--;

        return obj;
    }

查找

按元素下标查找：

1. 如果顺序表为空，返回 -1；
2. 如果查找位置不合理，抛出异常；
3. 返回第 i 个位置的元素。

    /**
     * 查找某个位置的元素
     *
     * @param index
     * @return
     */
    public Object search(int index) throws Exception {

        // 这个判断其实可以不要，因为如果 usedSize 为 0，则不论 index 的值如何都会走到下一个判断中
        if (usedSize == 0){
            return -1;
        }

        if(index < 0 || index >= usedSize){
            throw new Exception("查找位置不正确");
        }

        return arrayList[index];
    }

按元素查找：

1. 从前往后遍历，将需要查找的元素和顺序表中的元素对比；
2. 如果元素相等，直接返回元素下标；
3. 遍历结束还未找到，返回 -1。

    /**
     * 查找某个元素的位置
     *
     * @param obj
     * @return
     */
    public int search(Object obj) {
        for (int i = 0; i < usedSize; i++) {
            if (arrayList[i].equals(obj)) {
                return i;
            }
        }

        return -1;
    }

完整代码

package com.sqlboy.lineartable;

/**
 * 顺序表
 *
 * <p>
 */
public class SeqList {

    private int maxSize;
    private int usedSize;
    private Object[] arrayList;

    /**
     * 初始化
     *
     * @param maxSize
     */
    public SeqList(int maxSize) {
        this.maxSize = maxSize;
        this.usedSize = 0;

        arrayList = new Object[maxSize];
    }

    /**
     * 打印顺序表
     */
    public void display() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(arrayList[i] + " ");
        }

        System.out.println();
    }


    /**
     * 插入元素
     *
     * @param index 插入位置
     * @param obj   插入对象
     * @throws Exception
     */
    public void insert(int index, Object obj) throws Exception {
        if (usedSize == maxSize) {
            throw new Exception("顺序表已满！");
        }

        if (index < 0 || index > usedSize) {
            // index > usedSize 是为了保证元素之间不出现空缺位置
            throw new Exception("插入位置不存在");
        }

        // 从 index + 1 到 userSize 位置的元素统统往后移动一个位置
        for (int i = usedSize; i > index; i--) {
            arrayList[i] = arrayList[i - 1];
        }

        arrayList[index] = obj;
        usedSize++;
    }

    /**
     * 删除第一个出现的元素
     *
     * @param index 删除元素的下标
     * @return 删除的元素
     */
    public Object delete(int index) throws Exception {
        if (usedSize == 0) {
            throw new Exception("顺序表为空！");
        }

        if (index < 0 || index >= usedSize) {
            throw new Exception("删除位置不存在！");
        }

        // 先把要返回的元素取出来，免得待会删除以后想返回找不到了
        Object obj = arrayList[index];

        // 从index + 1 到 userSize 的元素往前移动一个位置
        for (int i = index; i < usedSize; i++) {
            arrayList[i] = arrayList[i + 1];
        }

        usedSize--;

        return obj;
    }


    /**
     * 判断是否包含某个元素
     *
     * @param obj
     * @return
     */
    public boolean contains(Object obj) {
        for (int i = 0; i < usedSize; i++) {
            if (arrayList[i].equals(obj)) {
                return true;
            }
        }

        return false;
    }

    /**
     * 查找某个元素的位置
     *
     * @param obj
     * @return
     */
    public int search(Object obj) {
        for (int i = 0; i < usedSize; i++) {
            if (arrayList[i].equals(obj)) {
                return i;
            }
        }

        return -1;
    }


    /**
     * 查找某个位置的元素
     *
     * @param index
     * @return
     */
    public Object search(int index) throws Exception {
        if (usedSize == 0){
            return -1;
        }

        if(index < 0 || index >= usedSize){
            throw new Exception("查找位置不正确");
        }

        return arrayList[index];
    }

    /**
     * 清空顺序表
     */
    public void clear() {
        usedSize = 0;
    }


    public static void main(String[] args) throws Exception {
        SeqList list = new SeqList(10);
        list.insert(0, new Integer(1));
        list.insert(1, new Integer(2));
        list.insert(2, new Integer(3));

        list.display();

        System.out.println(list.search(2));

        list.display();
    }
}