1. 线性表 line-list

1.1 顺序表

1.1.1. 实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * 顺序表
 */
public class SeqList {

    private static final int MAX_SIZE = 1024;
    private final int[] lis = new int[MAX_SIZE];
    private int size;

    public SeqList() {
        size = 0;
    }

    /**
     * 在指定位置插入数据
     *
     * @param data     要插入的数据
     * @param position position 要插入的位置
     */
    public boolean insert(int data, int position) {
        if (position >= MAX_SIZE || position < 0) {
            System.out.println("位置参数错误");
            return false;
        }
        if (size >= MAX_SIZE) {
            System.out.println("位置已满");
            return false;
        }
        for (int i = size; i > position; i--) {
            lis[i] = lis[i - 1];
        }
        lis[position] = data;
        size++;
        return true;
    }

    /**
     * 根据位置删除数据
     *
     * @param position 删除位置
     * @return 是否删除成功
     */
    public boolean delete(int position) {
        if (position > size || position < 0) {
            System.out.println("位置参数错误");
            return false;
        }

        for (int i = position; i < size; i++) {
            lis[i] = lis[i + 1];
        }
        size--;
        return true;
    }

    /**
     * 根据位置获取数据
     * @param position 获取位置
     * @return 位置
     */
    public int get(int position) {
        if (position > size || position < 0) {
            System.out.println("位置参数错误");
            return -1;
        }
        return lis[position];
    }

}

1.1.2 效率分析

  1. 插入操作：

    • 最好情况 从position = size , 最坏情况 position = 0
    • 设元素个数为nn 插入元素的位置有n+1种情况，当插入的位置等概率时, 有pi=1n+1p_i = \frac{1}{n+1}.
    • 则需要移动元素的平均次数为 ∑i=0npi(n−i)=1n+1∑i=0n(n−i)=n2\sum^{n}_{i=0}p_i(n-i)=\frac{1}{n+1}\sum^n_{i=0}(n-i)=\frac{n}{2}

  2. 删除操作:

    • 最好情况 从position = size - 1 , 最坏情况 position = 0
    • 设元素个数为nn 删除元素的位置有n种情况，当删除的位置等概率时, 有pi=1np_i = \frac{1}{n}.
    • 则需要移动元素的平均次数为 ∑i=0npi(n−i)=1n∑i=0n(n−i)=n−12\sum^{n}_{i=0}p_i(n-i)=\frac{1}{n}\sum^n_{i=0}(n-i)=\frac{n-1}{2}

  3. 综上， 无论删除或添加元素时间复杂度都为 O(n)O(n)