ArrayList与顺序表

线性表

线性表是n个具有相同性质的数据元素的有限序列，常见的线性表有：顺序表、链表、栈、队列……

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

这里要知道什么是物理上和逻辑上

物理上：其实就是内存上

逻辑上: 就是思维上

顺序表的定义

顺序表是一段物理地址连续的存储单元一次存储数据元素的线性结构，一般由数组来进行了存储，在数组上进行数据的增删查改。

MyArrayList 类

数据结构的知识是十分严谨的，所以在实现的时候一定要考虑得细致一点

//先写出MyArrayLis类的字段和构造方法
class MyArrayList {
    public int[] elem;
    public int usedSized;//usedSized是当前数组里面存的有效数据
    public static final int DEFAULT_CAPACITY=10;//初始数组的大小

    public  MyArrayList() {   //构造方法 1、没有返回值 2、方法名与类名一致
        this.elem = new int[DEFAULT_CAPACITY];
    }
}
1
2
3
4
5
6
7
8
9
10

打印顺序表

// 打印顺序表--只要一直打印到所有的有效数字就行了
public void display() {
    for (int i = 0; i < usedSized; i++) {
        System.out.print(this.elem[i]+" ");
    }
    System.out.println();
}
1
2
3
4
5
6
7

新增数据方法(add)

要新增数据就要考虑是否需要进行扩容，之后再进行具体实现

// 新增元素,默认在数组最后新增--必须要考虑是否数组是否会满（扩容问题）
public void add(int data) {
    if(isFull()){
        elem= Arrays.copyOf(elem, elem.length * 2);//Arrays.copyOf的返回值是数组，所以还要用elem接收一下
    }
    elem[usedSized]=data;
    usedSized++;
}

//判断数组是否满了，一定要和数组长度进行比较，不要和DEFAULT_CAPACITY比较，因为可能之后还要扩容，到时候就不能用DEFAULT_CAPACITY了，所以这里用的是elem.length
public boolean isFull() {
    return usedSized == elem.length;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

add方法实现在pos下标位置处新增一个数据

1、检查下表是否合法

2、判断数组是否已满

3、具体实现

要实现抛异常，最好可以自定义异常

package sequence_table;
/*
自定义一个异常(下标不合法的异常)
 */
public class PosIndexNotLegalException extends RuntimeException {
    public PosIndexNotLegalException() {

    }

    public PosIndexNotLegalException(String message) {
        super(message);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

具体实现新增数据

/*
checkPosAdd是为了检查一下要新增的下标是否合法，设为private是因为在类外也不会去掉用这个方法，
 */
private void checkAddPosAdd(int pos) {
    if (pos < 0 || pos > usedSized) {
      throw new PosIndexNotLegalException("pos位置不合法");//抛异常
    }
}
// 在 pos 位置新增元素--add方法实现了重载    
public void add(int pos, int data) {
    try {
        checkAddPosAdd(pos);//判断pos下表是否合理
        if (isFull()) {  //判断数组是否满了
            elem= Arrays.copyOf(elem, elem.length * 2);
        }
        for (int i = usedSized-1; i >= pos ; i--) {
            elem[i + 1] = elem[i];
        }
        elem[pos]=data;
        usedSized++;
    } catch (PosIndexNotLegalException e) {
        e.printStackTrace();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

判定是否包含某个元素

public boolean contains(int toFind) {
    for (int i = 0; i < usedSized; i++) {
        if (elem[i] == toFind) {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9

查找某个元素对应的位置

public int indexOf(int toFind) {
    for (int i = 0; i < usedSized; i++) {
        if (elem[i] == toFind) {
            return i;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9

获取 pos 位置的元素

1、判断下标的合法性

2、具体实现

/*
判断get方法的pos是否合法，与上面判断add的pos是否合法的区别就是不能取到usedSize
 */
private void checkGetPosAdd(int pos) {
    if (pos < 0 || pos >= usedSized) {
        throw new PosIndexNotLegalException("get方法的pos位置不合法");
    }
}
1
2
3
4
5
6
7
8

public int get(int pos) {
    try {
        checkGetPosAdd(pos);
        return elem[pos];
    } catch (PosIndexNotLegalException e) {
        //要是真的不合法，就要在这里处理pos不合法的问题
        e.printStackTrace();
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10

将pos 位置的元素设为 value --更新

public void set(int pos, int value) {
    try{
        checkGetPosAdd(pos);//判断下标合法性
        elem[pos] = value;
    }catch(PosIndexNotLegalException e){
        e.printStackTrace();
    }
}
1
2
3
4
5
6
7
8

删除第一次出现的关键字key

public void remove(int toRemove) {
    int pos=indexOf(toRemove);//index方法中要是找不到toRemove就返回-1
    if (pos == -1) {
        System.out.println("不存在这样的数字");
        return;
    }
    for (int i = pos; i <usedSized-1; i++) {
        elem[i] = elem[i + 1];
    }
    usedSized--;
}
1
2
3
4
5
6
7
8
9
10
11

获取顺序表长度

public int size() {
    return usedSized;
}
1
2
3

清空顺序表

public void clear() {
    //由于这里不是引用类型，所有就不用for循环了，直接将usedSize置为0即可
    /*for (int i = 0; i < usedSized; i++) {
        elem[i] = null;
    }*/
    usedSized=0;
}
1
2
3
4
5
6
7

以上就是顺序表的方法的实现

其实Java已经给我们提供了顺序表的代码了，那就是是ArrayList类

ArrayList类

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList1 = new ArrayList<>();
        arrayList1.add(0);
        arrayList1.add(1);
        arrayList1.add(2, 78);
        System.out.println(arrayList1);//打印
    }
}
1
2
3
4
5
6
7
8
9

截取数据

public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();
    list.add("JavaSE");
    list.add("JavaWeb");
    list.add("JavaEE");
    list.add("JVM");
    list.add("测试课程");
    List<String> ret = list.subList(1, 3);//截取，左闭右开
    System.out.println(ret);
}
1
2
3
4
5
6
7
8
9
10

顺序表的3种遍历方法

public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();
    list.add("JavaSE");
    list.add("JavaWeb");
    list.add("JavaEE");
    list.add("JVM");
    list.add("测试课程");
    List<String> ret = list.subList(1, 3);//截取，左闭右开
    //1、直接打印
    System.out.println(ret);
    System.out.println("==============");
    //2、for循环
    for (int i = 0; i < list.size(); i++) {
        System.out.println(list.get(i));
    }
    System.out.println("==============");
    //3、foreach
    for (String x:list) {
        System.out.println(x);
    }
}
//打印结果为：
[JavaWeb, JavaEE]
==============
JavaSE
JavaWeb
JavaEE
JVM
测试课程
==============
JavaSE
JavaWeb
JavaEE
JVM
测试课程
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

其实还有一种迭代器的方法来打印顺序表中的数据

public static void main(String[] args) {
	Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
}
1
2
3
4
5
6

顺序表的优缺点

优点：由于顺序表是将数据存储在一块连续的内存空间里面，所以空间利用率高

​ 由于顺序表是通过下标直接存储数据，所以读取速度快

缺点：

​ 顺序表的插入和删除都要遍历一遍所有的数据来移动数据

​ 分配内存不够灵活，当需要读取的数据多于顺序表的数据时，就会出现”溢出“，反之，就会出现内存空间的浪费

要是想要解决以上的问题，就要学习另一种数据结构—链表。

以上就是顺序表的理论知识以及简单的方法实现，之后我还会举几个关于顺序表的实例，希望大家多多指正。