线性表与顺序表

一、线性结构：

如果一个数据元素序列满足：

（1）除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素；

（2）第一个数据元素没有前驱数据元素；

（3）最后一个数据元素没有后继数据元素。

则称这样的数据结构为线性结构。

//线性表接口
public interface List {
    // 获得线性表长度
    public int size();

    // 判断线性表是否为空
    public boolean isEmpty();

    // 插入元素
    public void insert(int index, Object obj) throws Exception;

    // 删除元素
    public void delete(int index) throws Exception;

    // 获取指定位置的元素
    public Object get(int index) throws Exception;
}

public class SequenceList implements List {

    // 默认的顺序表的最大长度
    final int defaultSize = 10;
    // 最大长度
    int maxSize;
    // 当前长度
    int size;
    // 对象数组
    Object[] listArray;

    public SequenceList() {
        init(defaultSize);
    }

    public SequenceList(int size) {
        init(size);
    }

    // 顺序表的初始化方法
    private void init(int size) {
        maxSize = size;
        this.size = 0;
        listArray = new Object[size];
    }

    @Override
    public void delete(int index) throws Exception {
        if (isEmpty()) {
            throw new Exception("顺序表为空，无法删除！");
        }
        if (index < 0 || index > size - 1) {
            throw new Exception("参数错误！");
        }
        // 移动元素
        for (int j = index; j < size - 1; j++) {
            listArray[j] = listArray[j + 1];
        }
        size--;
    }

    @Override
    public Object get(int index) throws Exception {
        if (index < 0 || index >= size) {
            throw new Exception("参数错误！");
        }
        return listArray[index];
    }

    @Override
    public void insert(int index, Object obj) throws Exception {
        // 如果当前线性表已满，那就不允许插入数据
        if (size == maxSize) {
            throw new Exception("顺序表已满，无法插入！");
        }
        // 插入位置编号是否合法
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        // 移动元素
        for (int j = size - 1; j >= index; j--) {
            listArray[j + 1] = listArray[j];
        }

        listArray[index] = obj; // 不管当前线性表的size是否为零，这句话都能正常执行，即都能正常插入
        size++;

    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

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

public class SequenceListTest {
    public static void main(String[] args) {

        SequenceList list = new SequenceList(20);

        try {
            list.insert(0, 100);
            list.insert(0, 50);
            list.insert(1, 20);

            for (int i = 0; i < list.size; i++) {
                System.out.println("第" + i + "个数为" + list.get(i));
            }

        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

测试代码输出：

第0个数为50
第1个数为20
第2个数为100