Java数据结构基础：线性表

简介

线性表是指数据元素之间存在线性关系的数据结构，即数据元素之间有前后直接关系，且第一个元素没有前驱，最后一个元素没有后继。线性表可以用数组或者链表两种方式实现。

数组实现线性表

线性表的数组实现即为将线性表中的元素放在一个一维数组中，使用数组下标表示元素的位置。由于数组随机访问元素的时间复杂度为O(1)，因此在随机访问比较多的情况下，使用数组实现线性表会更加高效。

Java代码示例：

public class ArrayLinearList<T> implements LinearList<T> {
    private int maxLength; //数组最大长度
    private int length; //线性表当前长度
    private Object[] element; //线性表存储元素的数组

    public ArrayLinearList(int maxLength) {
        this.maxLength = maxLength;
        element = new Object[maxLength];
        length = 0;
    }

    // 获取线性表长度
    @Override
    public int size() {
        return length;
    }

    // 判断线性表是否为空
    @Override
    public boolean isEmpty() {
        return length == 0;
    }

    // 在线性表的第i个位置插入元素
    @Override
    public void insert(int i, T t) throws Exception {
        if (length == maxLength) {
            throw new Exception("线性表已满，无法插入元素！");
        }
        if (i < 1 || i > length + 1) {
            throw new Exception("插入位置不合法！");
        }
        // 将元素依次向后移动一位
        for (int j = length; j >= i; j--) {
            element[j] = element[j - 1];
        }
        element[i - 1] = t;
        length++;
    }

    // 删除线性表中第i个元素
    @Override
    public void delete(int i) throws Exception {
        if (isEmpty()) {
            throw new Exception("线性表为空，无法删除元素！");
        }
        if (i < 1 || i > length) {
            throw new Exception("删除位置不合法！");
        }
        // 将元素依次向前移动一位
        for (int j = i - 1; j < length - 1; j++) {
            element[j] = element[j + 1];
        }
        element[length - 1] = null;
        length--;
    }

    // 获取线性表中第i个元素的值
    @Override
    public T get(int i) throws Exception {
        if (i < 1 || i > length) {
            throw new Exception("获取位置不合法！");
        }
        return (T) element[i - 1];
    }
}

链表实现线性表

链表实现线性表即为将线性表中的元素分别存储在不同的结点中，并通过指针将这些结点相连组成链表。由于链表需要遍历到目标元素的前一个结点才能对目标元素进行插入、删除、修改等操作，因此在插入、删除、修改等频繁操作的场景中，使用链表实现线性表会更加高效。

Java代码示例：

public class LinkedLinearList<T> implements LinearList<T> {
    // 结点类
    private class Node {
        private T data; // 结点存储的数据
        private Node next; // 下一个结点

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node head; // 头结点
    private int length; // 线性表长度

    public LinkedLinearList() {
        head = new Node(null, null);
        length = 0;
    }

    // 获取线性表长度
    @Override
    public int size() {
        return length;
    }

    // 判断线性表是否为空
    @Override
    public boolean isEmpty() {
        return length == 0;
    }

    // 在线性表的第i个位置插入元素
    @Override
    public void insert(int i, T t) throws Exception {
        if (i < 1 || i > length + 1) {
            throw new Exception("插入位置不合法！");
        }
        Node p = head;
        // 寻找插入位置的前一个结点
        for (int j = 1; j < i; j++) {
            p = p.next;
        }
        Node newNode = new Node(t, p.next);
        p.next = newNode;
        length++;
    }

    // 删除线性表中第i个元素
    @Override
    public void delete(int i) throws Exception {
        if (isEmpty()) {
            throw new Exception("线性表为空，无法删除元素！");
        }
        if (i < 1 || i > length) {
            throw new Exception("删除位置不合法！");
        }
        Node p = head;
        // 寻找删除位置的前一个结点
        for (int j = 1; j < i; j++) {
            p = p.next;
        }
        p.next = p.next.next;
        length--;
    }

    // 获取线性表中第i个元素的值
    @Override
    public T get(int i) throws Exception {
        if (i < 1 || i > length) {
            throw new Exception("获取位置不合法！");
        }
        Node p = head.next;
        // 寻找第i个结点
        for (int j = 1; j < i; j++) {
            p = p.next;
        }
        return p.data;
    }
}

两种实现方式各有优缺点，可以根据具体的需求来选择合适的实现方式。