【Java数据结构】ArrayList顺序表_arraylist 顺序

Java数据结构 & ArrayList顺序表

• 我们平时很喜欢使用的数组，就是顺序表！
• 下面我们将以 “模拟ArrayList” 的视角来盘一盘顺序表吧！
• 

1. ArrayList的模拟

• 首先，这个类的功能如下：
  • 能够完成增删改查基础操作
  • 能够自动扩容（隐性，让这个顺序表能够存储足够多的数据）
  • 在一个类中放数据，这样可以给类加上一些方法，那么这个类的功能就更加丰富且有针对性，就像包装起来的一组东西（包括数组整体）
    • 在后面的链表集合类LinkedList中，虽然链表可用链表头结点表示（代表），但是这个类就是节点类吗，节点只是存储的方式，而集合类是包装起来的一组东西，即对象，通过这个对象，使用丰富的属性（包括这个链表整体）和方法

1.1 ArrayList的基础模板

• 总的模板如下（具体个别方法在后面）

public class MyArrayList {

    public int[] elem;
    public int usedSize;//0
    //默认容量
    private static final int DEFAULT_SIZE = 10;

    public MyArrayList() {
        this.elem = new int[DEFAULT_SIZE];
    }

    public MyArrayList(int size) {
        if (size <= 0) {
            throw new IndexException("MyArraylist");
        }
        this.elem = new int[size];
    }

    /**
     * 打印顺序表:
     * 根据usedSize判断即可
     */
    public void display() {
        
    }

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

    public boolean isFull() {
        
    }

    /**
     * 判断当前的顺序表是不是满的！
     *
     * @return true:满   false代表空
     */

    private boolean checkPosInAdd(int pos) {
        
    }

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

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

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

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

    private boolean isEmpty() {
        
    }

    // 给 pos 位置的元素设为【更新为】 value
    public void set(int pos, int value) {
        
    }

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

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

    // 清空顺序表
    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
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

1.1 属性

public int[] elem;
public int usedSize;//0
//默认容量
private static final int DEFAULT_SIZE = 10;
1
2
3
4

• elem 顺序表“本体”
• usedSize 顺序表已添加的有效数据
• DEFAULT_SIZE（不带参数的构造方法，在构造数组时的默认容量）

1.2 方法

1.2.1 构造方法

• 非正常操作的异常

public class IndexException extends RuntimeException{
    public IndexException() {
        
    }

    public IndexException(String message) {
        super(message);
    }
}
1
2
3
4
5
6
7
8
9

public MyArrayList() {
    this.elem = new int[DEFAULT_SIZE];
}

public MyArrayList(int size) {
    if (size <= 0) {
        throw new IndexException("MyArraylist");
    }
    this.elem = new int[size];
}
1
2
3
4
5
6
7
8
9
10

• 不带参数的构造方法
  • 以默认值构造数组
• 带参数的构造方法
  • 以传入的值作为起始容量

1.2.2 遍历方法

• 这个没啥好说的

    /**
     * 打印顺序表:
     * 根据usedSize判断即可
     */
    public void display() {
        if(isEmpty()) {
            System.out.println("[]");
        }
        else{
            System.out.print("[ ");
            for (int i = 0; i < this.usedSize; i++) {
                if(i == usedSize - 1) {
                    System.out.print(this.elem[i] + " ]");
                }else {
                    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

1.2.3 增加元素方法以及判断是否满方法

• 我们只需要在elem[usedSize] = data即可

  • 然后usedSize++，这样就刚好添加到数组的末尾

  • 但是，如果数组满了的话怎么办？

    • 那就要扩容一下了

    • 

      • copyOf()这个方法可以动态调整数组的大小，对比于C语言，这个方法更加全能

      • elem	2 * usedSize
        被拷贝的数组	新数组的大小（我这里扩大两倍）

// 新增元素,默认在数组最后新增
public void add(int data) {
    if (isFull()) {
        //满了即扩容
        elem = Arrays.copyOf(elem, 2 * usedSize);
    }
    elem[usedSize] = data;
    usedSize++;
}

//is...() 这种命名一般返回boolean类型，起判断作用
public boolean isFull() {
    if (usedSize == elem.length) {
        return true;
    } else {
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 我们还可以在指定位置进行插入（需要检验下标是否合理）
• 我们需要将对应位置以及后面的元素都向后挪动，腾出一个位置给待插入的元素（检验是否需要扩容）
  • 从尾挪动
  • 

//检验下标是否合理的方法
private boolean checkPosInAdd(int pos) {
    if (pos < 0 || pos > this.usedSize) {
        return false;
    }
    return true;//合法
}

// 在 pos 位置新增元素，构成重载
//pos刚好在末尾，是允许的
public void add(int pos, int data) {
    if (this.isFull()) {
        elem = Arrays.copyOf(elem, 2 * usedSize);
    }
    if (checkPosInAdd(pos)) {
        usedSize++;
        for (int i = usedSize; i > pos; i--) {
            elem[i] = elem[i - 1];
        }
        elem[pos] = data;
    }else {
        throw new IndexException("add");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.2.4 查找方法

• 第一个查找-> 找得到返回true 否则false
• 第二个查找-> 找得到返回对象下标，找不到返回-1（-1下标在java中完全用不了）
  • C语言中，访问下标arr[-1] = (arr - 1);

// 判定是否包含某个元素
public boolean contains(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if (elem[i] == toFind) {
            return true;
        }
    }
    return false;
}

// 查找某个元素对应的位置
public int indexOf(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if (elem[i] == toFind) {
            return i;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.2.5 获取下标元素方法

// 获取 pos 位置的元素
public int get(int pos) {
    if (checkPosInAdd(pos)) {
        if (pos == usedSize) {
            //下标不合理就会抛异常
            throw new IndexException("get");
        } else {
            //返回对应元素的值
            return elem[pos];
        }
    } else {
        //下标不合理就会抛异常
        throw new IndexException("get");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.2.6 更新下标对应元素方法

// 给 pos 位置的元素设为【更新为】 value
// 即使pos刚好对应末尾，只要是“空的”就不能够设置
public void set(int pos, int value) {
    if (checkPosInAdd(pos)) {
        if (pos == usedSize) {
            throw new IndexException("set");
        } else {
            this.elem[pos] = value;
        }
    } else {
        throw new IndexException("set");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.2.7 是否空以及获取顺序表元素个数方法

private boolean isEmpty() {
    return usedSize == 0;
}
1
2
3

// 获取顺序表长度
public int size() {
    return usedSize;
}
1
2
3
4

1.2.8 删除元素方法

• 对于第一次出现的key值，进行删除
  • 后面的所有元素要把这个空位补上去（也就是一个个挪动过去）
    • 从头挪动
    • 

/**
 * 删除第一次出现的关键字key
 *
 * @param key
 */
public void remove(int key) {
    int index = indexOf(key);
    if (index == -1) {
        System.out.println("Can‘t find");
    } else {
        for (int i = index; i < usedSize - 1; i++) {
            this.elem[i] = this.elem[i + 1];
        }
        usedSize--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 清空顺序表的方法：

  • // 清空顺序表
    public void clear() {
        this.elem = new int[DEFAULT_SIZE];
        this.usedSize = 0;
    }
    1
    2
    3
    4
    5

1.3 测试

public class Test {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList(5);
        myArrayList.display();
        myArrayList.add(1);
        myArrayList.add(2);
        myArrayList.add(3);
        myArrayList.display();
        System.out.println(myArrayList.indexOf(3));
        System.out.println(myArrayList.contains(3));
        System.out.println(myArrayList.indexOf(4));
        System.out.println(myArrayList.contains(4));
        myArrayList.add(4);
        myArrayList.add(5);
        myArrayList.add(6);
        myArrayList.display();
        myArrayList.add(2, 99);
        System.out.println(myArrayList.get(2));
        myArrayList.display();
        myArrayList.set(3, 99);
        myArrayList.display();
        myArrayList.remove(4);
        myArrayList.display();
        System.out.println(myArrayList.size());
        myArrayList.clear();
        myArrayList.display();
    }
}
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

• 测试结果正常！

2. ArrayList的使用以及系统源码的一些细节

• 

• E 是一个泛型类（不能用基本数据类型）

• List<Integer> list = new ArrayList<>();
  1

  • 这个是最常用的使用方式， 一般实例化List接口，这样功能更加具体

• 如果是自定义类的话，一定要重写equals()方法，因为在查找的时候，判断是否相同尤为重要

  • 重写compareTo()方法更好，在用工具类Collections去排序的时候要用到

2.1 属性

• 重点：
• 默认数组大小，DEFAULT_CAPACITY
• 本体数组，elementData[]
• 有效元素个数，size

2.2.1 构造方法

1. 带参数int的构造方法

   • 提供自定义数组大小，非法下标则抛异常

   • 

   • 等于0的情况，则给一个空数组

2. 不带参数的构造方法

   • 以默认的数组大小构造数组
   • 

3. 提供一整个集合类对象作为参数的构造方法

   • 即直接将这个集合类对象的所有元素，拷贝一份下来整合成顺序表返回

   • 

   • 但是这个集合类对象的泛型类型必须是E的子类或者E本身

2.2.2 常用方法

• 高亮即重点

• 使用这些方法的方式更上一部分相似

2.3 顺序表的遍历

2.3.1 for-each循环(不是foreach方法)

for(Integer i : list) {
    System.out.print(i + " ");
}
1
2
3

2.3.2 for循环

for(int i = 0; i < list.size(); i++) {
    System.out.print(list.get(i) + " ");
}
1
2
3

2.3.3 listIterator() =》Iterator 迭代器实现

• 了解即可

Iterator<Integer> iterator = list.listIterator();
while(iterator.hasNext()) {
    System.out.print(iterator.next() + " ");
}
1
2
3
4

2.3.4 直接sout（快捷）打印

• 前提是知道泛型类型的打印方法！！！
  • 所以我们的自定义类型就必须重写toString() 方法

System.out.print(list);
1

• 不难发现，List，ArrayList两个类都没有重写toString方法
• 那么这个类的对象是怎么打印的那？
  • 其实可以在这之前已经重写好了
  • 

2.4 toArray() 方法

1. 不带参数的构造方法，直接返回对应的数组，数据类型为Object[] 需要强制类型转化为对应的类型，（由于此时的Object是对应的类型实例化的，所以不会有问题）

   • System.out.println(list.toArray()[0] instanceof Integer);
   • 

2. 带参数，即直接对提供的数组进行修改，返回值跟上面一样

   • 注意：不能用基本数据类型的数组，且基本数据类型数组与对象数组之间不能进行拆箱装箱

2.5 ArrayList扩容机制

• 简单的来说就是
  • 满了扩容
  • 用copyOf()1.5倍扩容(位操作符速度快)
  • 超过最大容量报错

3. 实例

• 到这里，ArrayList的基本使用与原理知识已经讲解完了，
• 下面是一个小项目，可以去提高自己对顺序表的理解
• 大家可以通过我写的博客去理解和完成

3.1 扑克牌系统-斗牛

(21条消息) JavaProject & 洗牌斗牛系统_Carefree_State的博客-CSDN博客

3.2 拓展：八皇后问题（非必要方法，只是结合ArrayList去解决罢了）

(21条消息) 《八皇后问题》& Java数据结构 & JavaProject & JavaOJ题集_Carefree_State的博客-CSDN博客

3.3 杨辉三角

• 二维顺序表的表示（解题类似二维数组）
• 

class Solution {
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList();
        for(int i = 0; i < numRows; i++) {
            list.add((List<Integer>)new ArrayList());
            for(int j = 0; j < i + 1; j++) {
                if(j == 0 || i == j) {
                    list.get(i).add(1);
                }else if(i > 1 && j > 0 && j < i) {
                    list.get(i).add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));
                }
            }
        }
        return list;
    }
}
public class Test {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int scan = scanner.nextInt();
        List list = Solution.generate(scan);
        System.out.println(list);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

文章到此结束！谢谢观看
可以叫我 小马，我可能写的不好或者有错误，但是一起加油鸭

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/500727