---

前言

顺序表是一种常见的线性表，线性表是具有相同特性的数据元素的有限集合，是一种用途广泛的数据结构。

---

线性表

常见的线性表有：顺序表、链表、栈、队列等；
线性表在逻辑上是连续的，即一条直线；但是在物理地址上不一定连续；

顺序表

顺序表的底层实现可以认为是一个数组，即物理地址上一块连续的存储空间；

模拟实现顺序表

import java.lang.reflect.Array;
import java.util.Arrays;


public class MyArrayList {

    private static int capacity=10;    //定义数组的最大容量，可以随时修改
    int [] array=new int[capacity];     //数组

    int usedSize=0;     //当前数组中有效元素的个数

    //判断数组是否已满
    private boolean isFull(){
        return this.usedSize==this.array.length;
    }

    //判断当前数组是否为空

    private boolean empty(){
        if(usedSize==0){
            return true;
        }
        return false;
    }

    //判断下标的合法性
    private boolean checkPosLegal(int pos){
        if(pos<0||pos>usedSize-1){
            System.out.println("下标位置不合法");
            return false;
        }
        return true;
    }
    // 打印顺序表
    public void display() {
        for(int i=0;i<usedSize;i++){
            System.out.print(array[i]+" ");
        }
    }
    // 新增元素,默认在数组最后新增
    public void add(int data) {
        if(isFull()){
            this.array= Arrays.copyOf(array,2*array.length);    //数组已满，对其扩容
        }
        array[usedSize]=data;
        usedSize++;

    }
    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        if(isFull()){
            this.array=Arrays.copyOf(array,2*array.length);
        }
        for(int i=usedSize-1;i>=pos;i--){
            array[i+1]=array[i];
        }
        array[pos]=data;
        usedSize++;


    }

    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for(int i=0;i<usedSize;i++){
            if(array[i]!=toFind){
                return false;
            }
        }
        return true;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(array[i]==toFind){
                return i;
            }
        }
        return -1;
    }
    // 获取 pos 位置的元素
    public int get(int pos) {
        if(checkPosLegal(pos)){
            for (int i = 0; i <usedSize ; i++) {
                if(i==pos){
                    return array[i];
                }
            }
        }

        return -1;
    }
    // 给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        if (checkPosLegal(pos)){
            for (int i=0;i<usedSize;i++){
                if (i==pos){
                    array[i]=value;
                }
            }
        }
        return;

    }
    //删除第一次出现的关键字key
    public void remove(int toRemove) {
        if(empty()) {
            System.out.println("顺序表为空，无法删除");;
        }
        int index = indexOf(toRemove);
        if(index == -1) {
            System.out.println("不存在你要删除的数据");
            return;
        }

        for (int i = index; i < this.usedSize-1; i++) {
            this.array[i] = this.array[i+1];
        }
        //删除完成
        this.usedSize--;


    }
    // 获取顺序表长度
    public int size() {

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

    }
}



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

ArrayList

ArrayList是Java提供给我们的一个顺序表结构，是一个实现了List接口的类。

构造ArrayList

常见的构造ArrayList的方法：

		//没有参数的构造方法
        List<Integer> list=new ArrayList<>();
        //指定顺序表的初始容量
        List<Integer> list1=new ArrayList(5);
1
2
3
4

两种构造方法的区别主要就在于是否有参数的传递，如果这个参数是顺序表的初始容量，那么我们可能会有这样的疑问：当调用没有参数的构造方法时，它的默认初始容量是多少呢？

观察源码：

这里说，构造一个初始容量为10的空列表，但实际通过源码可以看出如果只是调用了这个没有参数的构造方法，其底层依然是一个大小为0的空数组，至于为什么又说其初始容量为10，其实是指在顺序表第一次调用add函数时，这个数组发生膨胀，容量变为10；

ArrayList的常见操作

		List<Integer> list=new ArrayList<>();
       
        List<Integer> list1=new ArrayList(5);

        //boolean add(E e) 尾插
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        list1.add(9);
        list1.add(8);
        list1.add(7);
        list1.add(6);
        list1.add(5);

        //void add(int index, E element) 将 e 插入到 index 位置
        list.add(0,5);
        //boolean addAll(Collection c) 尾插 c 中的元素
        list.addAll(list1);
        //E remove(int index) 删除index位置的元素
        System.out.println(list.remove(0));
        //boolean remove(Object o) 删除遇到的第一个o
        //这种情况必须要使用下面的这种写法，否则编译器会将参数默认为顺序表下标处理
        System.out.println(list.remove(new Integer(4)));
        // get(int index) 获取下标 index 位置元素
        System.out.println(list.get(3));
        //set(int index, E element) 将下标 index 位置元素设置为 element
        list.set(4,8);
        //void clear() 清空顺序表
        list.clear();
        //boolean contains(Object o) 判断 o 是否在线性表中
        list.contains(5);
        //int indexOf(Object o) 返回第一个 o 所在下标
        list.indexOf(2);
        //int lastIndexOf(Object o) 返回最后一个 o 的下标
        list.lastIndexOf(4);
        //List subList(int fromIndex, int toIndex) 截取部分 list
        list.subList(1,3);//左闭右开

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

ArrayList的遍历方法

        //使用for循环利用下标遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        

        //使用for-each遍历
        for (Integer t:list ) {
            System.out.print(t+" ");
        }
        

        //使用迭代器遍历
        Iterator<Integer> t=list.iterator();
        while (t.hasNext()){
            System.out.print(t.next()+" ");
        }
        //迭代器遍历
        Iterator<Integer> t1=list.listIterator();
        while (t1.hasNext()){
            System.out.print(t1.next()+" ");
        }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

ArrayList的扩容机制

ArrayList的扩容函数是grow( )函数；

观察源码：

可以看到原来的容量是数组的长度，而新的容量是用来的容量加上原来容量的一半，即ArrayList的扩容是1.5倍扩容；

顺序表的简单了解就到这里啦，over！