【数据结构】线性表与顺序表

⭐ 作者：小胡_不糊涂
🌱 作者主页：小胡_不糊涂的个人主页
📀 收录专栏：浅谈数据结构
💖 持续更文，关注博主少走弯路，谢谢大家支持 💖

1. 线性表

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

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

2. 顺序表

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

2.1 接口的实现

实现顺序表的插入、删除、修改、查找工作：

import java.util.Arrays;
public class MyArrayList {
    public int[] elem ;//定义一个数组
    public int usedSize;//0，用来记录元素个数
    //顺序表的 默认大小
    public static final int DEFAULT_SIZE = 10;
    public MyArrayList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    public MyArrayList(int capacity) {
        this.elem = new int[capacity];
    }

    //顺序表尾部插入元素
    public void add(int data) {
        checkCapacity();
        this.elem[this.usedSize] = data;
        this.usedSize++;
    }

    //判断顺序表是否为空
    public boolean isFull() {
        /*if(usedSize == elem.length) {
            return true;
        }
        return false;*/
        return usedSize == elem.length;
    }

    //指定pos位置添加元素data
    public void add(int pos, int data) {
        try {
            checkPosOnAdd(pos);
        }catch (PosIllegality e) {
            e.printStackTrace();
        }
        checkCapacity();
        //1、从最后一个有效的数据开始往后移动 //2、当i < pos 就结束
        for (int i = usedSize-1; i >= pos; i--) {
            elem[i+1] = elem[i];
        }
        //3、存放元素到pos 位置
        elem[pos] = data;
        //4、usedSize++;
        usedSize++;
    }

    //检查插入位置pos的合法性
    private void checkPosOnAdd(int pos) throws PosIllegality{
        if(pos < 0 || pos > usedSize) {
            System.out.println("不符合法！");
            throw new PosIllegality("插入元素下标异常: "+pos);
        }
    }

    private void checkCapacity() {
        if(isFull()) {
            //扩容
            elem = Arrays.copyOf(elem,elem.length*2);
        }
    }

    //判定是否包含某一元素
    public boolean contains(int toFind) {
        if(isEmpty()) {
            return false;
        }
        for (int i = 0; i < usedSize; i++) {
            //如果是查找引用数据类型 一定记住 重写方法
            if(elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

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

    //查找某个元素对应位置
    public int indexOf(int toFind) {
        if(isEmpty()) {
            return -1;
        }
        for (int i = 0; i < usedSize; i++) {
            //如果是查找引用数据类型 一定记住 重写方法
            if(elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    //获取pos位置元素
    public int get(int pos) throws MyArrayListEmpty{
        checkPosOnGetAndSet(pos);
        if(isEmpty()) {
            throw new MyArrayListEmpty("获取指定下标元素时" +
                    "顺序表为空！");
        }
        return elem[pos];
    }

    private void checkPosOnGetAndSet(int pos) throws PosIllegality{
        if(pos < 0 || pos >= usedSize) {
            System.out.println("不符合法！");
            throw new PosIllegality("获取指定下标的元素异常: "+pos);
        }
    }

    //给pos位置设为元素value
    public void set(int pos, int value) {
        checkPosOnGetAndSet(pos);
        elem[pos] = value;
    }

    //删除第一次出现的这个数字
    public void remove(int toRemove) {
        int index = indexOf(toRemove);//获取元素下标
        if(index == -1) {
            System.out.println("没有这个数字！");
            return;
        }
        for(int i = index; i < usedSize-1;i++) {
            elem[i] = elem[i+1];
        }
        usedSize--;
    }

    //获取顺序表长度
    public int size() {
        return this.usedSize;
    }

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

    //打印顺序表中元素
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }

}
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

测试类：

public class TestMAL{
    public static void main(String[] arg) {
        MyArrayList arr = new MyArrayList();
        arr.add(1);
        arr.add(2);
        arr.add(3);
        arr.add(4);
        arr.add(5);
       arr.display();
       System.out.println("-------");
       arr.add(1);
        arr.display();
        System.out.println("-------");
        arr.add(6,2);
        arr.display();
        System.out.println("-------");
        System.out.println(arr.indexOf(3));
        arr.display();
        System.out.println("-------");
        arr.get(9);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3. ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：

【说明】

1. ArrayList是以泛型方式实现的，使用时必须要先实例化
2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

4. ArrayList使用

4.1 ArrayList构造

ArrayList的创建：

public static void main(String[] arg){
    // ArrayList创建，推荐写法
    // 构造一个空的列表
        List<Integer> list1 = new ArrayList<>();
    // 构造一个具有10个容量的列表
        List<Integer> list2 = new ArrayList<>(10);
        list2.add(1);
        list2.add(2);
        list2.add(3);
    // list2.add("hello"); // 编译失败，List已经限定了，list2中只能存储整形元素
    // list3构造好之后，与list中的元素一致
        ArrayList<Integer> list3 = new ArrayList<>(list2);
    // 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难
        List list4 = new ArrayList();
        list4.add("111");
        list4.add(100);
        System.out.println(list4);//[111,100]
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4.2 ArrayList常见操作

ArrayList操作方法的使用：

 public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("JavaSE");
        list.add("JavaWeb");
        list.add("JavaEE");
        list.add("JVM");
        list.add("测试课程");
        System.out.println(list);
// 获取list中有效元素个数
        System.out.println(list.size());
// 获取和设置index位置上的元素，注意index必须介于[0, size)间
        System.out.println(list.get(1));
        list.set(1, "JavaWEB");
        System.out.println(list.get(1));
// 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置
        list.add(1, "Java数据结构");
        System.out.println(list);
// 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置
        list.remove("JVM");
        System.out.println(list);
// 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常
        list.remove(list.size()-1);
        System.out.println(list);
        // 检测list中是否包含指定元素，包含返回true，否则返回false
        if(list.contains("测试课程")){
            list.add("测试课程");
        }
// 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
        list.add("JavaSE");
        System.out.println(list.indexOf("JavaSE"));
        System.out.println(list.lastIndexOf("JavaSE"));
// 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组
        List<String> ret = list.subList(0, 4);
        System.out.println(ret);
        list.clear();
        System.out.println(list.size());
    }
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

4.3 ArrayList的遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
    // 使用下标+for遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
    // 借助foreach遍历
        for (Integer integer : list) {
            System.out.print(integer + " ");
        }
        System.out.println();
     //使用迭代器
        Iterator<Integer> it = list.listIterator();
        while(it.hasNext()){
            System.out.print(it.next() + " ");
        }
        System.out.println();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24