集合及数据结构第四节————List与顺序表

系列文章目录

集合及数据结构第四节————List、ArrayList与顺序表

List、ArrayList与顺序表

1. List的介绍
2. 常见接口介绍
3. .List的使用
4. 什么是线性表
5. 顺序表接口的定义
6. MyArrayList类里面实现这些接口（）功能
7. 顺序表的优缺点

---

---

一、List的介绍

1.什么是List？

在集合框架中，List是一个接口，继承自Collection。

Collection也是一个接口，该接口中规范了后序容器中常用的一些方法，具体如下所示：

Iterable也是一个接口，表示实现该接口的类是可以逐个元素进行遍历的，具体如下：Iterable也是一个接口，表示实现该接口的类是可以逐个元素进行遍历的，具体如下：

站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作

2.常见接口介绍

List中提供了好的方法，具体如下：

虽然方法比较多，但是常用方法如下：

3.List的使用（ * * ）

注意：List是个接口，并不能直接用来实例化。
如果要使用，必须去实例化List的实现类。在集合框架中，ArrayList和LinkedList都实现了List接口

二、线性表

1.什么是线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

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

顺序表接口的定义

public interface Ilist {
    // 新增元素,默认在数组最后新增
    void add(int data);
    // 在 pos 位置新增元素
    void add(int pos, int data);
    // 判定是否包含某个元素
    boolean contains(int toFind);
    // 查找某个元素对应的位置
    int indexOf(int toFind);
    // 获取 pos 位置的元素
    int get(int pos);
    // 给 pos 位置的元素设为 value
    void set(int pos, int value);
    //删除第一次出现的关键字key
    void remove(int key);
    // 获取顺序表长度
    int size();
    // 清空顺序表
    void clear();
}

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

MyArrayList类里面实现这些接口（）功能

public class MyArrayList implements Ilist{

    @Override
    public void add(int data) {// 新增元素,默认在数组最后新增

    }

    @Override
    public void add(int pos, int data) {// 在 pos 位置新增元素

    }

    @Override
    public boolean contains(int toFind) {// 判定是否包含某个元素
        return false;
    }

    @Override
    public int indexOf(int toFind) {// 查找某个元素对应的位置
        return 0;
    }

    @Override
    public int get(int pos) {// 获取 pos 位置的元素
        return 0;
    }

    @Override
    public void set(int pos, int value) {// 给 pos 位置的元素设为 value

    }

    @Override
    public void remove(int key) {//删除第一次出现的关键字key

    }

    @Override
    public int size() {// 获取顺序表长度
        return 0;
    }

    @Override
    public void clear() {// 清空顺序表

    }
}
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

1.新增元素,默认在数组最后新增

1. 判断顺序表有没有存满（新增一个private修饰的checkCapacity方法来判断）

private void checkCapacity(){//判断顺序表有没有存满，并且自动进行扩容
                                // (不是提供给用户的，只为当前这个类服务所以用private进行封装）
         if(usedsize >= elem.length){
             Arrays.copyOf(elem,elem.length * 2);//拷贝elem数组两倍长度到一个新建的顺序表中
             //然后让elem重新指向扩容后的顺序表
        }
    }
1
2
3
4
5
6
7

2. 在数组最后新增元素

代码实现：

public void add(int data) { // 新增元素,默认在数组最后新增
        checkCapacity();
        this.elem[this.usedsize] = data;
        this.usedsize++;
    }
1
2
3
4
5

2. 在 pos 位置新增元素

1. 在数据结构当中，每次存储数据的时候，必须有一个前驱信息。所以0 <= pos <= usedsize 才合法。（新增一个private修饰的checkPosOnAdd方法来判断）

public class PosLocationIllegality extends  RuntimeException{
    public PosLocationIllegality(String message){
        super(message);
    }
}
1
2
3
4
5

private void checkPosOnAdd(int pos) throws  PosLocationIllegality{//判断输入的pos位置是否合法，如果不合法就抛出一个异常。
        if(pos < 0 || pos > usedsize){
            throw new PosLocationIllegality("pos位置不合法" + pos );
        }
    }
1
2
3
4
5

2. 检查顺序表有没有存满

3. 开始新增元素

• 从最后一个有效的数据开始往后移动（i >= pos 时）
• 当i < pos 时就结束
• 存放元素到 pos 位置
• usedSize++；

代码实现：

public void add(int pos, int data) {// 在 pos 位置新增元素
        try {
            checkPosOnAdd(pos);//判断输入的pos位置是否合法，如果不合法就抛出一个异常。
        }catch (PosLocationIllegality e){
            e.printStackTrace();
            return;
        }

        checkCapacity();//判断数组有没有存满，并且自动进行扩容

        //1. 从最后一个有效的数据开始往后移动（i >= pos 时）
        //2.当i < pos 时就结束
        for (int i = usedsize - 1; i >= pos ; i--) {
            this.elem[i + 1] =this.elem[i];
        }
        //3. 存放元素到 pos 位置
        this.elem[pos] = data;

        //4. usedSize++；
        this.usedsize++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3. 判定是否包含某个元素

1. 判断顺序表是否为空（新增一个isEmpty方法来判断）
2. 遍历数组查找

代码实现：

public boolean isEmpty() {//判断数组是否为空
        return this.usedsize == 0;
    }
1
2
3

public boolean contains(int toFind) {// 判定是否包含某个元素
        if(isEmpty()) {
            return false;
        }
        for (int i = 0; i < this.usedsize; i++) {
            if (this.elem[i] == toFind){
                return true;
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11

4. 查找某个元素对应的位置

1. 判断数组是否为空（用isEmpty方法来判断）
2. 遍历数组查找查找成功返回下标，失败则返回-1
   代码实现：

public int indexOf(int toFind) {// 查找某个元素对应的位置
        if(isEmpty()) {
            return -1;
        }
        for (int i = 0; i < this.usedsize; i++) {
            //如果是查找引用数据类型，一定要重写equals方法
            if (this.elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12

5. 获取 pos 位置的元素

1. 在获取pos位置的元素时最后一个元素之后的坐标都不合法。所以0 <= pos <= usedsize 才合法。（新增一个private修饰的ccheckPosOnGet方法来判断）
2. 判断顺序表是否为空。如果顺序表为空则抛出一个异常，否则返回pos下标的元素

  public int get(int pos) { // 获取 pos 位置的元素
       checkPosOnGet(pos);

       if (isEmpty()){//如果顺序表为空，抛出一个异常
          throw new MyArraylistEmpty("获取指定下标元素时顺序表为空");
       }
       return elem[pos];
    }
1
2
3
4
5
6
7
8

6. 获取 pos 位置的元素

1. 在获取pos位置的元素时最后一个元素之后的坐标都不合法。所以0 <= pos <= usedsize 才合法。（新增一个private修饰的checkPosOnGetAndSet方法来判断）
2. 将value赋值给下标为pos的elem数组

代码实现：

private void checkPosOnSet(int pos) throws  PosLocationIllegality{//判断输入的pos位置是否合法，如果不合法就抛出一个异常。
        if(pos < 0 || pos >= usedsize){
            throw new PosLocationIllegality("要设定的指定下标的元素的pos位置不合法" + pos );
        }
    }
1
2
3
4
5

public void set(int pos, int value) { // 给 pos 位置的元素设为 value
        checkPosOnSet(pos);//判断要设置的元素的pos位置是否合法，如果不合法就抛出一个异常。
        this.elem[pos] = value;
    }
1
2
3
4

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

1. 找到要删除的数据，如果没有找到就抛出一个异常

public class ToRemoveWrong extends RuntimeException{
    public ToRemoveWrong(String message){
        super(message);
    }
}
1
2
3
4
5

2. 挪动数据
3. 修改usedSize

8. 获取顺序表长度

1. 判断顺序表是否为空。
   代码实现：

public int size() {// 获取顺序表长度
        if (isEmpty()){//如果顺序表为空，抛出一个异常
            throw new MyArraylistEmpty("当前顺序表为空");
        }
        return this.usedsize;
    }
1
2
3
4
5
6

9. 清空顺序表

对于当前基本类型的数据来说，只需要将usedSize置为0。但是当顺序表中存放的是引用类型的数据时，就会产生内存泄漏（JVM只会在一个对象没有被引用时自动回收）。所以清空该引用类型顺序表的方法有下面几种：

1. 直接将elem置为null（比较粗暴的方法）
2. 写一个for循环将每一个有效数据置为null（推荐使用）

 public void clear() {
        this.usedSize=0;
    }

1
2
3
4

顺序表的优缺点

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)；而插入或删除时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。当然，它的优缺点还不只这些……

优点：

1. 在给定下标要进行查找的时候，时间复杂度为O（1）

缺点：

1. 插入数据必须移动其他数据。最坏的情况下就是插入到你位置时时间的复杂度为O（N）
2. 删除数据必须移动其他数据。最坏的情况下就是删除0位置时时间的复杂度为O（N）
3. 扩容之后有可能会浪费空间

顺序表比较适合进行下标查找的场景