摘要：数组中有一个很重要的概念叫做索引，也就是数组元素的编号，编号从开始的，所以最后一个元素的索引为数组的长度即，可以通过数组名索引来访问数组中的元素。
前言
【从蛋壳到满天飞】JAVA 数据结构解析和算法实现，全部文章大概的内容如下：
Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜索树)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(优先队列)、SegmentTree(线段树)、Trie(字典树)、UnionFind(并查集)、AVLTree(AVL 平衡树)、RedBlackTree(红黑平衡树)、HashTable(哈希表)
源代码有三个：ES6（单个单个的 class 类型的 js 文件） | JS + HTML（一个 js 配合一个 html）| JAVA (一个一个的工程)
全部源代码已上传 github，点击我吧，光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。
本文章适合 对数据结构想了解并且感兴趣的人群，文章风格一如既往如此，就觉得手机上看起来比较方便，这样显得比较有条理，整理这些笔记加源码，时间跨度也算将近半年时间了，希望对想学习数据结构的人或者正在学习数据结构的人群有帮助。
java 中的数组 数组基础
把数据码成一排进行存放
强语言中数据的类型是确认的，
弱语言中数据的类型是不确认的，
但是也有方法可以进行确认。
数组就是把一个一个的数据近挨着排成一排。
可以给一个数组起一个名字，起名字要有语义化。
数组中有一个很重要的概念叫做索引，
也就是数组元素的编号，编号从 0 开始的，
所以最后一个元素的索引为数组的长度-1 即 n-1，
可以通过数组名[索引]来访问数组中的元素。
java 中的数组是有局限性的。
public class Main {
public static void main(String[] args) {
// 输出
System.out.println("Array");
// 定义数组
int[] arr = new int[10];
// 循环赋值
for (int i = 0; i < arr.length; i++) {
arr[i] = i;
}
// 定义数组
int[] scores = new int[]{100, 99, 88};
// for循环遍历 数组
for (int i = 0; i < scores.length ; i++) {
System.out.println(scores[i]);
}
// 修改数组中某个元素
scores[0] = 60;
// foreach 遍历数组
for (int score: scores) {
System.out.println(score);
}
}
}
二次封装数组
数组的索引可以有语意也可以没有语意。
如 scores[2] 代表一个班级中第三个学生。
数组的最大优点
快速查询，如 scores[2]
数组最好应用于“索引有语意”的情况。
如果索引没有语意的话，
那么使用别的数据结构那会是一个更好的选择。
计算机处理的问题有千千万万个
有很多场景即使能给索引定义出来语意，
但是它有可能不适用于数组。
比如身份证号可以设计为一个数组，
用来存储相应的工资情况，
如果想索引到不同的人，
那么使用身份证号就是一个很好的方式，
但是身份证号不能作为一个数组的索引，
因为这个身份证号太大了，
如果想要使用身份证号作为一个数组的索引，
那么开辟的空间会非常的大，
例如arr[110103198512112312]，
对于一般的计算机来说开辟这样的一块儿空间，
是非常不值当的，甚至是不可能的，
而且大部分空间都是浪费的，
比如你就想考察 100 个人的工资情况，
你却开辟了 1000 兆倍的空间。
数组也可以处理“索引没有语意”的情况。
在索引有语意的情况下使用数组非常简单，
直接就可以查到相应的数据。
在索引没有语义的情况下使用数组，
那么就会产生很多新的问题。
因为这个时候数组只是一个待存
放那些要考察的数据的空间，
例如你开辟了 8 个元素的空间，
但是你只考察 2 个元素，
此时就有问题了，剩下的空间都没有元素，
可能访问剩下的空间就是非法的，
因为从用户的角度上来看是没有那么多元素的，
只有两个元素。
索引没有语意，如何表示没有元素？
如何添加元素？如何删除元素？
等等更多问题，
例如添加元素时，
因为数组创建的时候数组的大小就固定了。
在 java 中数组没有这些功能，
所以需要基于 Java 的数组，
二次封装属于我们自己的数组类。
也就是将原本的静态数据变成动态的数组。
将数组封装成自己的数组
将原本 Java 中的数组封装到一个类中，
从而封装一个属于自己的数组，这个类就叫做 MyArray，
在这个类中封装一个 java 的数组，这个数组叫做 data，
对这个数组进行增删改插等等的功能。
数据结构的本质也是存储数据，
之后再进行高效的对这些数据进行操作，
只不过你设计的数据结构会把这些数据存储在内存中，
所以针对这些数据结构的所添加的操作在大的类别的划分上，
也是增删改查。
针对不同的数据结构，
对应的增删改查的方式是截然不同的，
甚至某些数据结构会忽略掉增删改查中的某一个操作，
但是增删改查可以作为研究某一个数据结构的相应的脉络，
数组本身是静态的，必须在创建的时候指定他的大小，
可以把这个容量叫做 capacity，
也就是数组空间最多可以装多少个元素，
数组空间最多可以装多少个元素与
数组中实际装多少个元素是没有关系的，
因为这是两回事儿，
数组中实际能够装多少个元素可以叫做 size，
通过它来控制，在初始化的时候，
数组中一个元素都没有，所以 size 为 0，
这个 size 相当于数组中第一个没有盛放元素的相应索引，
增加数组元素和删除数组元素的时候就要维护这个 size。
代码示例(class: MyArray)
public class MyArray {
private int [] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public MyArray (int capacity) {
data = new int[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public MyArray () {
// this( capacity: 10);
this(10);
}
// 获取数组中的元素实际个数
public int getSize () {
return size;
}
// 获取数组的总容量
public int getCapacity () {
return data.length;
}
// 返回数组是否为空
public boolean isEmpty () {
return size == 0;
}
}
对自己的数组进行添加操作
向数组添加元素最简单的形式
就是在数组的末尾添加一个元素，
size 这个变量其实就是指向数组中的末尾，
添加完元素之后其实也需要维护这个 size，
因为数组中的元素多了一个，所以要让它加加。
如果是给元素进行插入的操作
那么要先判数组的容量是否已经装满了，
然后再判断索引是否小于 0 或者大于 size，
都没有问题了，就可以根据索引来进行插入了，
插入的原理就是那个索引位置及其后的元素，
全都都往后移动一位，所以循环是从后往前的，
最后让该索引处的旧元素被新元素覆盖，
但旧元素并没消失，而是位置往后移动了一位，
最后要记得维护 size。
向数组中添加元素可以复用向数组中插入元素的方法，
因为插入元素的方法也是在给数组添加元素，
并且插入元素的方法可以在任何位置插入新元素，
那么就可以扩展两个方法，
一个插入到数组最前面（插入到索引为 0 的位置），
一个是插入到数组最后面
（插入到索引为 数组最后一个元素的索引+1 的位置）。
给数组添加元素的时候如果元素为数字（添加时可排序可不排序）
那么每一次添加操作时可以给数组中的元素进行排序，
排序方式是按照从小到大来进行排序。
先判断添加的这个元素大于数组中哪一个元素，
然后将那个元素及其后面的所有元素往后移一位，
最后将添加的这个元素插入到那个元素后面。
先要对数组中的容量进行判断，
如果超过了就不添加，并且报错，
每次添加之前要判断一下插入的位置，
它后面还有没有元素或者这个数组是否为空。
记住每次添加操作都要维护 size 这个变量。
代码示例(class: MyArray) public class MyArray {
private int [] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public MyArray (int capacity) {
data = new int[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public MyArray () {
// this( capacity: 10);
this(10);
}
// 获取数组中的元素实际个数
public int getSize () {
return size;
}
// 获取数组的总容量
public int getCapacity () {
return data.length;
}
// 返回数组是否为空
public boolean isEmpty () {
return size == 0;
}
// 给数组添加一个新元素
public void add (int e) {
if (size == data.length) {
throw new IllegalArgumentException("add error. Array is full.");
}
data[size] = e;
size++;
}
// 向所有元素后添加一个新元素 （与 add方法功能一样） push
public void addLast (int e) {
// 复用插入元素的方法
insert(size, e);
}
// 在所有元素前添加一个新元素 unshift
public void addFirst (int e) {
insert(0, e);
}
// 在index索引的位置插入一个新元素e
public void insert (int index, int e) {
if (size == data.length) {
throw new IllegalArgumentException("add error. Array is full.");
}
if (index < 0 || index > size) {
throw new IllegalArgumentException(
"insert error. require index < 0 or index > size"
);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
}
对自己的数组进行查询和修改操作
如果你要覆盖父类中的方法，记得要加备注
如 // @Override: 方法名 日期-开发人员
获取自定义数组中指定索引位置的元素
首先要判断索引是否小于 0 或者
大于等于 实际元素的个数，都没有问题时，
就可以返回索引位置的元素了。
用户没有办法去访问那些没有使用的数组空间。
修改自动数组中指定索引位置的元素
和获取是一样的，要先判断，
只能设置已有存在的元素索引位置的元素，
用户没有办法去修改那些没有使用的数组空间。
代码示例(class: MyArray, class: Main)
MyArray
public class MyArray {
private int [] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public MyArray (int capacity) {
data = new int[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public MyArray () {
// this( capacity: 10);
this(10);
}
// 获取数组中的元素实际个数
public int getSize () {
return size;
}
// 获取数组的总容量
public int getCapacity () {
return data.length;
}
// 返回数组是否为空
public boolean isEmpty () {
return size == 0;
}
// 给数组添加一个新元素
public void add (int e) {
if (size == data.length) {
throw new IllegalArgumentException("add error. Array is full.");
}
data[size] = e;
size++;
}
// 向所有元素后添加一个新元素 （与 add方法功能一样）push
public void addLast (int e) {
// 复用插入元素的方法
insert(size, e);
}
// 在所有元素前添加一个新元素 unshift
public void addFirst (int e) {
insert(0, e);
}
// 在index索引的位置插入一个新元素e
public void insert (int index, int e) {
if (size == data.length) {
throw new IllegalArgumentException("add error. Array is full.");
}
if (index < 0 || index > size) {
throw new IllegalArgumentException("insert error. require index < 0 or index > size");
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
// 获取index索引位置的元素
public int get (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
return data[index];
}
// 修改index索引位置的元素为e
public void set (int index, int e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
data[index] = e;
}
@Override
// @Override: 方法名 日期-开发人员
public String toString () {
StringBuilder sb = new StringBuilder();
String arrInfo = "Array: size = %d，capacity = %d
";
sb.append(String.format(arrInfo, size, data.length));
sb.append("[");
for (int i = 0; i < size - 1; i ++) {
sb.append(data[i]);
sb.append(",");
}
if(!isEmpty()) {
sb.append(data[size - 1]);
}
sb.append("]");
return sb.toString();
}
}
Main
public class Main {
public static void main(String[] args) {
// write your code here
MyArray ma = new MyArray(20);
for (int i = 1; i <= 10 ; i++) {
ma.add(i);
}
System.out.println(ma);
ma.insert(1, 200);
System.out.println(ma);
ma.addFirst(-1);
System.out.println(ma);
ma.addLast(9999);
System.out.println(ma);
ma.set(5, 8888);
System.out.println(ma.get(5));
}
}
对自己的数组进行包含、查找、和删除操作
继续对自定义的数组增加新功能
包含、搜索、删除这三个功能。
包含：
判断数组中 是否存在这个元素，
不存在返回 false。
搜索：
根据这个元素来进行 索引的获取，
找不到返回 非法索引 -1。
删除：
首先要判断索引的合法性，
其次这个操作与插入的操作其实原理类似，
只不过是一个反向的过程，
指定索引位置的元素其后面的元素的位置
全部往前一位，循环时 初始索引为 指定的这个索引，
从前往后的不断向前移动，这样被删除的元素就被覆盖了，
覆盖之前要保存一下指定索引的元素的值，
这个值要作为返回值来进行返回，
然后让 size 减减，因为覆盖掉这个元素，
由于数组访问会有索引合法性的判断
一定要小于 size，于是用户是访问不到 size 位置的元素了，
所以 size 位置的元素可以不用去处理它，
但你也可以手动的将这个元素值设置为默认值。
有了指定索引删除某个元素并返回被删除的这个元素的操作
那么就可以扩展出两个方法，
和使用插入方法来进行扩展的那两个方法类似，
分别是 删除第一个元素和删除最后一个元素，
并且返回被删除的元素，
删除数组元素时会判断数组索引的合法性，
如果数组为空，那么合法性验证就无法通过。
根据元素来删除数组中的某个元素
首先通过 包含 的那个方法来判断这个元素是否存在，
如果元素不存在那就不进行删除操作，也可以报一个异常，
如果元素存在，那就根据 搜索 的那个方法来获取这个元素的索引，
最后根据 获取到合法索引 来进行元素的删除。
其实你可以使用通过 搜索 的那个方法直接返回元素的索引，
如果索引合法你就直接删除，
如果索引不合法那就不删除然后也可以报一个异常。
可以对那些方法进行扩展
如 删除数组中所有的指定元素
如 找到数组中所有的指定元素的索引
关于自定义的数组已经实现了很多功能，
但是这个自定义数组还有很多的局限性，
在后面会慢慢解决这些局限性，
如 这个数组能存放的数据类型不能是任意的数据类型，
如果 这个数组的容量是一开始就固定好的，超出就报异常。
代码示例(class: MyArray, class: Main)
MyArray
public class MyArray {
private int [] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public MyArray (int capacity) {
data = new int[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public MyArray () {
// this( capacity: 10);
this(10);
}
// 获取数组中的元素实际个数
public int getSize () {
return size;
}
// 获取数组的总容量
public int getCapacity () {
return data.length;
}
// 返回数组是否为空
public boolean isEmpty () {
return size == 0;
}
// 给数组添加一个新元素
public void add (int e) {
if (size == data.length) {
throw new IllegalArgumentException("add error. Array is full.");
}
data[size] = e;
size++;
}
// 向所有元素后添加一个新元素 （与 add方法功能一样） push
public void addLast (int e) {
// 复用插入元素的方法
insert(size, e);
}
// 在所有元素前添加一个新元素 unshift
public void addFirst (int e) {
insert(0, e);
}
// 在index索引的位置插入一个新元素e
public void insert (int index, int e) {
if (size == data.length) {
throw new IllegalArgumentException("add error. Array is full.");
}
if (index < 0 || index > size) {
throw new IllegalArgumentException("insert error. require index < 0 or index > size");
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
// 获取index索引位置的元素
public int get (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
return data[index];
}
// 修改index索引位置的元素为e
public void set (int index, int e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contain (int e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return true;
}
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find (int e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return i;
}
}
return -1;
}
// 查找数组中所有元素e所在的索引，最后返回存放 所有索引值的 自定义数组
public MyArray findAll (int e) {
MyArray ma = new MyArray(20);
for (int i = 0; i < size; i++) {
if (data[i] == e) {
ma.add(i);
}
}
return ma;
// int[] result = new int[ma.getSize()];
// for (int i = 0; i < ma.getSize(); i++) {
// result[i] = ma.get(i);
// }
//
// return result;
}
// 从数组中删除第一个元素, 返回删除的元素
public int removeFirst () {
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public int removeLast () {
return remove(size - 1);
}
// 从数组中删除第一个元素e
public void removeElement (int e) {
int index = find(e);
if (index != -1) {
remove(index);
}
// if (contain(e)) {
// int index = find(e);
// remove(index);
// }
}
// 从数组中删除所有元素e
public void removeAllElement (int e) {
int index = find(e);
while (index != -1) {
remove(index);
index = find(e);
}
// while (contain(e)) {
// removeElement(e);
// }
}
// 从数组中删除index位置的元素, 返回删除的元素
public int remove (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
int temp = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
// for (int i = index + 1; i < size; i++) {
// data[i - 1] = data[i];
// }
size --;
data[size] = 0;
return temp;
}
@Override
// @Override: 方法名 日期-开发人员
public String toString () {
StringBuilder sb = new StringBuilder();
String arrInfo = "Array: size = %d，capacity = %d
";
sb.append(String.format(arrInfo, size, data.length));
sb.append("[");
for (int i = 0; i < size - 1; i ++) {
sb.append(data[i]);
sb.append(",");
}
if(!isEmpty()) {
sb.append(data[size - 1]);
}
sb.append("]");
return sb.toString();
}
}
Main
public class Main {
public static void main(String[] args) {
// 创建一个自定义的数组对象
MyArray ma = new MyArray(20);
for (int i = 1; i <= 10 ; i++) {
ma.add(i);
}
/*
* Array: size = 10，capacity = 20
*/
System.out.println(ma);
ma.insert(1, 200);
/*
* Array: size = 11，capacity = 20
* [1,200,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.addFirst(-1);
/*
* Array: size = 12，capacity = 20
* [-1,1,200,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.addLast(9999);
/*
* Array: size = 13，capacity = 20
* [-1,1,200,2,3,4,5,6,7,8,9,10,9999]
*/
System.out.println(ma);
ma.set(5, 8888);
/*
* 8888
*/
System.out.println(ma.get(5));
/*
* Array: size = 13，capacity = 20
* [-1,1,200,2,3,8888,5,6,7,8,9,10,9999]
* true
* 6
*/
System.out.println(ma);
System.out.println(ma.contain(5));
System.out.println(ma.find(5));
ma.remove(ma.find(5));
/*
* Array: size = 12，capacity = 20
* [-1,1,200,2,3,8888,6,7,8,9,10,9999]
*/
System.out.println(ma);
/*
* -1
* 9999
* Array: size = 10，capacity = 20
* [1,200,2,3,8888,6,7,8,9,10]
*/
System.out.println(ma.removeFirst());
System.out.println(ma.removeLast());
System.out.println(ma);
ma.removeElement(8888);
/*
* Array: size = 9，capacity = 20
* [1,200,2,3,6,7,8,9,10]
*/
System.out.println(ma);
ma.add(123456);
ma.add(123456);
ma.add(123456);
/*
* Array: size = 3，capacity = 20
* [9,10,11]
* Array: size = 12，capacity = 20
* [1,200,2,3,6,7,8,9,10,123456,123456,123456]
*/
System.out.println(ma.findAll(123456));
System.out.println(ma);
ma.removeAllElement(123456);
/*
* Array: size = 9，capacity = 20
* [1,200,2,3,6,7,8,9,10]
*/
System.out.println(ma);
}
}
## 让自己的数组可存放任何数据类类型 1. 泛型技术可以让数据结构放置“任何”数据类型 2. 在 Java 中泛型的类型不可以是基本数据类型 1. 只能是类类型，也就是说只能存放对象， 2. 不可以存放基本数据类型的值。 3. 在 java 语言中有八种数据基本数据类型 1. boolean、byte、char、short、 2. int、long、float、double。 4. 每个基本数据类型都有对应的包装类 1. 这样就把不是类对象这样的数据变成类对象， 2. Boolean、Byte、Char、Short、 3. Int、Long、Float、Double， 4. 名字完全一样，只不过首字母进行了大写， 5. 这些包装类与他们对应的基本数据类型之间可以无缝的进行转换 1. 这个自动的转换过程就叫作自动的加包或者解包， 2. 也就是基本类型在需要的时候会自动转换为他所对应的包装类， 3. 而这些包装类也会在他们需要的时候自动的转换为 4. 他们所对的基本类型，这样一来就可以将一个数组变成 5. 一个可以放置任何数据类型的泛型数组。 6. 通过在自定义的数组类型后面加上`` 1. E 表示一个任意的类型， 2. 而`<>`表示这个类型拥有了泛型的能力， 3. 在你具体使用的时候可以将`<>`中的 E 4. 改成你想要存放的数据的类型。 7. 泛型这个能力并不是 Java 一开始就有的， 1. 是从 Java1.5 才开始支持的， 2. 在如果在定义的类中使用这个任意类型 E， 3. 需要绕一个弯子，将使用到 E 的地方改成 Object， 4. Object 类是任意类的父类， 5. 然后再对这个类的对象进行强制类型的转换， 6. 如`(E[])new Object[capacity]`， 7. 这样的语法是合法的，这样就相当于在这个类中 8. new 出来一个还没有指定类型的 E 类型的数组， 9. 当你在使用这个类的时候，那么 E 可以变成任意的类型。 8. 比较泛型 E 类型的对象时不能再用`==` 1. 值比较 用 `==`， 2. 引用比较 用 `equals()` 9. 在删除操作时 1. java 中有一个垃圾回收机制， 2. 但是如果引用一直存在的话， 3. 就不会回收，所以可以在删除操作时， 4. 给这个数组 size 位置的元素赋值为 null， 5. 这样相当于就给元素设置默认值 null 了。 10. loitering objects != memory leak 11. 闲置的对象并不等于内存泄漏， 12. 只不过是这个对象没有用了， 13. 还是在这个程序中游荡， 14. 也没有办法被垃圾回收机制回收掉， 15. 但是为了程序优化， 16. 可以手动的把这个闲置的对象去除掉那就更好。 17. 泛型可以存放所有的数据类型 18. 非常的方便，原理还是编译时的代码检查， 19. 最终会编译成具体的数据类型， 20. 或者原理是泛型中存放的数据类型会被编译成新的类型。 ### 代码示例`(class: MyArray, class: Main, class: Student)` 1. Myarray
public class MyArray{ private E [] data; private int size; // 构造函数，传入数组的容量capacity构造Array public MyArray (int capacity) { data = (E[])new Object[capacity]; size = 0; } // 无参数的构造函数，默认数组的容量capacity=10 public MyArray () { // this( capacity: 10); this(10); } // 获取数组中的元素实际个数 public int getSize () { return size; } // 获取数组的总容量 public int getCapacity () { return data.length; } // 返回数组是否为空 public boolean isEmpty () { return size == 0; } // 给数组添加一个新元素 public void add (E e) { if (size == data.length) { throw new IllegalArgumentException("add error. Array is full."); } data[size] = e; size++; } // 向所有元素后添加一个新元素 （与 add方法功能一样） push public void addLast (E e) { // 复用插入元素的方法 insert(size, e); } // 在所有元素前添加一个新元素 unshift public void addFirst (E e) { insert(0, e); } // 在index索引的位置插入一个新元素e public void insert (int index, E e) { if (size == data.length) { throw new IllegalArgumentException("add error. Array is full."); } if (index < 0 || index > size) { throw new IllegalArgumentException("insert error. require index < 0 or index > size"); } for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = e; size++; } // 获取index索引位置的元素 public E get (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } return data[index]; } // 修改index索引位置的元素为e public void set (int index, E e) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } data[index] = e; } // 查找数组中是否有元素e public boolean contain (E e) { for (int i = 0; i < size; i++) { // if (data[i] == e) { // 值比较 用 == if (data[i].equals(e)) { // 引用比较 用 equals() return true; } } return false; } // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1 public int find (E e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { return i; } } return -1; } // 查找数组中所有元素e所在的索引，最后返回存放 所有索引值的 自定义数组 public MyArray findAll (E e) { MyArray ma = new MyArray(20); for (int i = 0; i < size; i++) { if (data[i].equals(e)) { ma.add(i); } } return ma; // int[] result = new int[ma.getSize()]; // for (int i = 0; i < ma.getSize(); i++) { // result[i] = ma.get(i); // } // // return result; } // 从数组中删除第一个元素, 返回删除的元素 public E removeFirst () { return remove(0); } // 从数组中删除最后一个元素, 返回删除的元素 public E removeLast () { return remove(size - 1); } // 从数组中删除第一个元素e public void removeElement (E e) { int index = find(e); if (index != -1) { remove(index); } // if (contain(e)) { // int index = find(e); // remove(index); // } } // 从数组中删除所有元素e public void removeAllElement (E e) { int index = find(e); while (index != -1) { remove(index); index = find(e); } // while (contain(e)) { // removeElement(e); // } } // 从数组中删除index位置的元素, 返回删除的元素 public E remove (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } E temp = data[index]; for (int i = index; i < size - 1; i++) { data[i] = data[i + 1]; } // for (int i = index + 1; i < size; i++) { // data[i - 1] = data[i]; // } size --; // data[size] = 0; data[size] = null; return temp; } @Override // @Override: 方法名 日期-开发人员 public String toString () { StringBuilder sb = new StringBuilder(); String arrInfo = "Array: size = %d，capacity = %d "; sb.append(String.format(arrInfo, size, data.length)); sb.append("["); for (int i = 0; i < size - 1; i ++) { sb.append(data[i]); sb.append(","); } if(!isEmpty()) { sb.append(data[size - 1]); } sb.append("]"); return sb.toString(); } }
2. Main
public class Main {
public static void main(String[] args) {
// 创建一个自定义的数组对象
MyArray ma = new MyArray(20);
for (int i = 1; i <= 10 ; i++) {
ma.add(i);
}
/*
* Array: size = 10，capacity = 20
* [1,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.insert(1, 200);
/*
* Array: size = 11，capacity = 20
* [1,200,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.addFirst(-1);
/*
* Array: size = 12，capacity = 20
* [-1,1,200,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.addLast(9999);
/*
* Array: size = 13，capacity = 20
* [-1,1,200,2,3,4,5,6,7,8,9,10,9999]
*/
System.out.println(ma);
ma.set(5, 8888);
/*
* 8888
*/
System.out.println(ma.get(5));
/*
* Array: size = 13，capacity = 20
* [-1,1,200,2,3,8888,5,6,7,8,9,10,9999]
* true
* 6
*/
System.out.println(ma);
System.out.println(ma.contain(5));
System.out.println(ma.find(5));
ma.remove(ma.find(5));
/*
* Array: size = 12，capacity = 20
* [-1,1,200,2,3,8888,6,7,8,9,10,9999]
*/
System.out.println(ma);
/*
* -1
* 9999
* Array: size = 10，capacity = 20
* [1,200,2,3,8888,6,7,8,9,10]
*/
System.out.println(ma.removeFirst());
System.out.println(ma.removeLast());
System.out.println(ma);
ma.removeElement(8888);
/*
* Array: size = 9，capacity = 20
* [1,200,2,3,6,7,8,9,10]
*/
System.out.println(ma);
ma.add(123456);
ma.add(123456);
ma.add(123456);
/*
* Array: size = 3，capacity = 20
* [9,10,11]
* Array: size = 12，capacity = 20
* [1,200,2,3,6,7,8,9,10,123456,123456,123456]
*/
System.out.println(ma.findAll(123456));
System.out.println(ma);
ma.removeAllElement(123456);
/*
* Array: size = 9，capacity = 20
* [1,200,2,3,6,7,8,9,10]
*/
System.out.println(ma);
}
}
3. Student
public class Student {
private String name;
private int score;
public Student(String studentName, int studentScore){
name = studentName;
score = studentScore;
}
@Override
// @Override 方法名 日期-开发人员
public String toString(){
return String.format("Student(name: %s, score: %d)", name, score);
}
// 增加入口方法，就可以直接执行代码了
public static void main(String[] args) {
MyArray arr = new MyArray();
arr.addLast(new Student("Alice", 100));
arr.addLast(new Student("Bob", 66));
arr.addLast(new Student("Charlie", 88));
System.out.println(arr);
}
}
## 让自己的数组成为动态数组 1. 自定义数组的局限性还有容量为固定的大小， 1. 因为内部还是使用的 java 的静态数组， 2. 静态数组的容量从定义开始就是固定的， 3. 如果一开始就把容量开的太大了， 4. 那么就会浪费很多的空间， 5. 如果容量开的太小了， 6. 那就可能存放的空间不够用。 2. 使用一种解决方案，让自定义数据的容量可伸缩 1. 让自定义数组变成一个动态的数组， 2. 当自定义数组中的空间已经满了， 3. 那就创建一个新的数组， 4. 这个数组的容量定义为原来的容量的两倍， 5. 然后将旧数组中的元素全部放到新数组中， 6. 以循环的方式放入新数组中。 3. 让新数组替代掉旧数组， 1. 当`size == capcity`时创建新数组，容量翻倍， 2. 当`size == capcity / 2`时创建新数组，容量缩小一倍， 3. 最终都会让新数组替代掉旧数组。 4. 使用这种方式会让整体性能上很有优势。 5. 在 Java 的动态数组中选择是扩容倍数是 1.5， 6. 然后无论是 1.5 还是 2 或者 3 都是可以的， 7. 只不过是一个参数的选择， 8. 你可以根据使用场景来进行扩容。 4. 自定义数组的这些操作及性能需要分析。 1. 也就是要进行一个时间复杂度的分析。 ### 代码示例`(class: MyArray, class: Main)` 1. Myarray
public class MyArray{ private E [] data; private int size; // 构造函数，传入数组的容量capacity构造Array public MyArray (int capacity) { data = (E[])new Object[capacity]; size = 0; } // 无参数的构造函数，默认数组的容量capacity=10 public MyArray () { // this( capacity: 10); this(10); } // 获取数组中的元素实际个数 public int getSize () { return size; } // 获取数组的总容量 public int getCapacity () { return data.length; } // 返回数组是否为空 public boolean isEmpty () { return size == 0; } // 重新给数组扩容 private void resize (int newCapacity) { E[] newData = (E[])new Object[newCapacity]; int index = size - 1; while (index > -1) { newData[index] = get(index); index --; } data = newData; } // 给数组添加一个新元素 public void add (E e) { if (size == data.length) { // throw new IllegalArgumentException("add error. Array is full."); resize(2 * data.length); } data[size] = e; size++; } // 向所有元素后添加一个新元素 （与 add方法功能一样） push public void addLast (E e) { // 复用插入元素的方法 insert(size, e); } // 在所有元素前添加一个新元素 unshift public void addFirst (E e) { insert(0, e); } // 在index索引的位置插入一个新元素e public void insert (int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("insert error. require index < 0 or index > size"); } if (size == data.length) { // throw new IllegalArgumentException("add error. Array is full."); resize(2 * data.length); } for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = e; size++; } // 获取index索引位置的元素 public E get (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } return data[index]; } // 修改index索引位置的元素为e public void set (int index, E e) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } data[index] = e; } // 查找数组中是否有元素e public boolean contain (E e) { for (int i = 0; i < size; i++) { // if (data[i] == e) { // 值比较 用 == if (data[i].equals(e)) { // 引用比较 用 equals() return true; } } return false; } // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1 public int find (E e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { return i; } } return -1; } // 查找数组中所有元素e所在的索引，最后返回存放 所有索引值的 自定义数组 public MyArray findAll (E e) { MyArray ma = new MyArray(20); for (int i = 0; i < size; i++) { if (data[i].equals(e)) { ma.add(i); } } return ma; // int[] result = new int[ma.getSize()]; // for (int i = 0; i < ma.getSize(); i++) { // result[i] = ma.get(i); // } // // return result; } // 从数组中删除第一个元素, 返回删除的元素 public E removeFirst () { return remove(0); } // 从数组中删除最后一个元素, 返回删除的元素 public E removeLast () { return remove(size - 1); } // 从数组中删除第一个元素e public void removeElement (E e) { int index = find(e); if (index != -1) { remove(index); } // if (contain(e)) { // int index = find(e); // remove(index); // } } // 从数组中删除所有元素e public void removeAllElement (E e) { int index = find(e); while (index != -1) { remove(index); index = find(e); } // while (contain(e)) { // removeElement(e); // } } // 从数组中删除index位置的元素, 返回删除的元素 public E remove (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } E temp = data[index]; for (int i = index; i < size - 1; i++) { data[i] = data[i + 1]; } // for (int i = index + 1; i < size; i++) { // data[i - 1] = data[i]; // } size --; // data[size] = 0; data[size] = null; if(size == data.length / 2) { resize(data.length / 2); } return temp; } @Override // @Override: 方法名 日期-开发人员 public String toString () { StringBuilder sb = new StringBuilder(); String arrInfo = "Array: size = %d，capacity = %d "; sb.append(String.format(arrInfo, size, data.length)); sb.append("["); for (int i = 0; i < size - 1; i ++) { sb.append(data[i]); sb.append(","); } if(!isEmpty()) { sb.append(data[size - 1]); } sb.append("]"); return sb.toString(); } }
2. Main
public class Main {
public static void main(String[] args) {
// 创建一个自定义的数组对象
MyArray ma = new MyArray();
for (int i = 1; i <= 10 ; i++) {
ma.add(i);
}
/*
* Array: size = 10，capacity = 10
* [1,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.insert(8, 99999);
/*
* Array: size = 10，capacity = 20
* [1,2,3,4,5,6,7,8,99999,9,10]
*/
System.out.println(ma);
ma.remove(8);
/*
* Array: size = 10，capacity = 10
* [1,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
}
}
## 简单的时间复杂度分析 1. 在算法和数据结构领域有一个非常重要的内容 1. 使用复杂度分析的方式来查看代码相应的性能好不好， 2. 时间复杂度分析是一个理论化的领域， 3. 如果非要非常严谨的去研究它， 4. 那就会涉及到很多数学方面的内容以及很多新概念， 5. 所以只需要对时间复杂度有一个简单的认识即可。 2. 常见的算法的时间复杂度 1. `O(1)、O(n)、O(lgn)、O(nlogn)、O(n^2)`等等 3. 这个大 O 简单的来说描述的是 1. 算法的运行时间和输入数据之间的关系。 2. 如最简单的求和，使用 for 循环来进行求和 3. 他的时间复杂度就是 `O(n)`， 4. 这个 n 表示的是求和 for 循环遍历的次数， 5. 这个算法运行的时间和 for 循环遍历的次数成线性关系， 6. 算法和 n 呈线性关系就是`O(n)`。 4. 为什么要用大 O，为什么要叫做`O(n)`？ 1. 因为忽略掉了很多的常数， 2. 实际时间用线性方程来表示：`T = c1*n + c2`， 3. 其中的 c1 表示循环遍历的每一次的时间， 4. 遍历的次数就为 n， 5. c2 表示遍历之前和之后的代码执行时间， 6. 也就是其它地方的代码执行消耗的时间 7. 如 你要初始化一个变量 sum， 8. 如果你写的是一个方法，你要返回最终结果 sum
public static int calcSum (int[] nums) {
int sum = 0;
for (int num: nums) {sum += num;}
return sum;
}
5. 如果在具体分析算法的时候把 c1 和 c2 也都具体的分析出来，
1. 其实那样没有什么必要，并且在有些情况下也不可能做到，
2. 例如不同的语言实现，执行的时间是不等的，
3. 因为转换为机器码后的指令数也是不一样的，
4. 就算指令都一样，还有不同系统 cpu 执行的操作也是不一样的，
5. 很难判断出来 c1 是几条指令、c2 又是几条指令，
6. 正因为如此所以在分析时间复杂度的时候，
7. 是一定要忽略掉这些常数的，
8. 忽略掉这些常数之后，
9. 算法一：`T = 2*n + 2`、算法二：`T = 2000*n + 10000`，
10. 他们的时候复杂度都是 `O(n)`，
11. 换句话来说他们都是线性时间的算法，
12. 这些算法消耗的时间和输入数据的规模是成一个线性关系。
6. 如果有一个算法三：`T = 1*n*n + 0`
1. 不要认为这个 1 很小、0 也很小，
2. 但是它依然是一个`O(n^2)`级别的一个算法，
3. 也就是说这个算法消耗的时间和这个数据的规模成一个平方关系的，
4. `O(n^2)`要比`O(n)`性能差很多，因为前者是 N 的平方级别的，
5. 虽然第二个算法的常数 2000 和 10000 特别的大，
6. 而第三个算法的常数 1 和 0 特别的小，
7. 的确如此，假设这个 n 为 10，
8. 那么第三个算法消耗的时间会比第二个算法消耗的时间要长，
9. 但是那并不能证明第三个算法比第二个算法性能就要差，
10. 因为这个本来就要分具体情况，常数会影响到执行的时间，
11. 但是计算时间复杂度就是要忽略掉常数的，
12. 因为你实际使用没有办法控制所有常数。
7. 这个 O 其实表示的一个`渐进的时间复杂度`
1. 这个渐进 描述的是当 n 趋近于无穷大的时候，
2. 例如第二个算法与第三个算法中的 n 为 3000，
3. 那么很明显第三个算法肯定要比第二个算法执行时间长，
4. 当这个 n 比 3000 还要大的时候，
5. 那么`O(n^2)`要比`O(n)`的执行时间差的越来越大，
6. 所以当 n 越大，一个低阶算法的性能就越能体现出来，
7. 也就是 n 越大就越能看出来`O(n^2)`要比`O(n)`快。
8. 在实际使用时可能会用到高阶算法
1. 当 n 比较小的时候有可能因为他的常数比较低，
2. 反而可能会快于一个低阶算法，
3. 例如 高阶的排序算法 归并排序、快速排序，
4. 这些高阶排序法都可以对于比较小的数组转而使用插入排序这种方式，
5. 可以很好的进行优化，通常这种优化能获得百分之 10 到百分之 15 性能提升，
6. 它的眼里实际上是插入排序算法的常数要比归并排序、快速排序算法的常数小一些，
7. 这样低阶的算法执行时间要比高阶的算法执行时间要快一些。
9. 大 O 描述的是一个算法或者操作的一个渐进式的时间复杂度，
1. 也就是在说这个算法操作所消耗的时间和输入数据的规模之间的关系
2. 由于大 O 描述的是 n 趋近于无穷大的情况下这个算法的时间复杂度，
3. 所以当出现这种算法时`T = 2*n*n + 300n + 10`，
4. 他的时间复杂度还是`O(n^2)`，
5. 如果这个算法的时间和 n 成 2 次方关系的话，
6. 相应这个算法的时间和 n 成 1 次方的关系会被忽略掉，
7. 因为在这种情况下 低阶项会被忽略掉，
8. 因为当 n 趋近于无穷的时候 低阶项起到的作用太小了，
9. 所以当 n 无穷大的时候低阶项的大小是可以忽略不计的，
10. 所以`T = 2*n*n + 300n + 10`的时间复杂度还是`O(n^2)`。
### 分析动态数组的时间复杂度
1. 增：O(n)
2. 删：O(n)
3. 改：已知索引 O(1)，未知索引 O(n)
4. 查找：已知索引 O(1)，未知索引 O(n)
5. 其它
1. 未知索引的删除，需要先查后删：O(n^2)
2. 未知索引的删除全部，需要先遍历再查再删：O(n^3)
3. 未置索引的查找全部，需要先遍历：O(n)
6. 所以在使用数组的时候
1. 索引要具有一定语意，
2. 这样就可以直接通过索引来进行操作，
3. 如果索引没有语意，
4. 那么修改和查找会让性能大幅度降低。
7. 增和删如果只对最后一个元素进行操作
1. 那么时间复杂度就为`O(1)`，
2. 但是动态数组要有 resize 伸缩容量的功能，
3. 所以增和删的时间复杂度依然是`O(n)`。
8. 一旦要 resize 了，就需要把整个元素全都复制一遍
1. 复制给一片新的空间，
2. 虽然说 resize 好像是一个性能很差的操作，
3. 但是实际上并不是这样的，
4. 完全使用最坏情况的时间复杂度来分析 resize 是不合理的，
5. 应该使用均摊时间复杂度分析来分析 resize，
6. 其实 resize 所消耗的性能在整体上没有那么的糟糕。
#### 添加操作：时间复杂度为 O(n)
1. `addLast(e)`：向数组末尾添加一个元素
1. 非常简单，只是简单的给`data[size]`赋值，
2. 所以它的时间复杂度为 `O(1)`
3. `O(1)`的时间复杂度表示这个操作所消耗的时间
4. 与 数据的规模是没有关系的，
5. 在分析数组的时间复杂度的时候，
6. 那个时间复杂度与这个数组有多少个元素有关系，
7. 由于你要遍历数组中每一个元素，
8. 那么这个时间复杂度就为`O(n)`（操作 n 个元素），
9. addLast 都能在常数时间内完成，
10. 所以他的时间复杂度就为`O(1)`（操作 1 个元素）。
2. `addFirst(e)`：向数组头部添加一个元素
1. 需要把数组中的元素都往后移动一个位置，
2. 所以这涉及到遍历数组中每一个元素，
3. 那么这个时间复杂度就为`O(n)`（操作 n 个元素），
4. 虽然最后也有`O(1)`（操作 1 个元素）的操作 ，
5. 但是在有`O(n)`情况时，
6. 更低阶项`O(1)`会被忽略掉。
3. `insert(index, e)`：在 index 索引这个位置插入一个元素
1. 当 index 为 0 的时候就和`addFirst(e)`一样要向后移动 n 个元素，
2. 当 index 为 size(数组中实际元素个数)的时候就和`addLast(e)`一样
3. 只是简单的给`data[size]`赋值，
4. 由于这个 index 可以取 0 到 size 中任何一个值，有那么多种可能性，
5. 那么就可以进行假设在具体操作的时候取到每一个值的概率都是一样的，
6. 在这种情况下进行操作时它所消耗的时间的期望，
7. 有些情况 index 会小一些，那么向后移动位置的元素会多一些，
8. 有些情况 index 会大一些，那么向后移动位置的元素会少一些，
9. 平均而言这个算法的时间复杂度为`O(n/2)`，
10. 但是这个 2 是一个常数，需要忽略常数，
11. 所以忽略常数后这个算法的时间复杂度为`O(n)`
12. 所以最好的情况下时间复杂就为`O(1)`，
13. 最坏的情况下时间复杂度就为`O(n)`，
14. 中等的情况下时间复杂度就为`O(n/2)`。
4. 添加操作综合来看是一个`O(n)`级别的算法
1. `addLast(e)`：`O(1)`，
2. `addFirst(e)`：`O(n)`，
3. `insert(index, e)`：`O(n/2)=O(n)`。
4. 严格计算就需要一些概率论上的知识，
5. 所以在算法复杂度分析上，
6. 通常关注的是某个算法时间复杂度的最坏情况、最糟糕的情况，
7. 也会有一些特例，但是在现实生活中你不能按照最好的情况去解决问题。
8. 例如 你去上班，公司距离你家的位置最快只需要 5 分钟，
9. 然后你每次去上班只留五分钟的时间从家里出来到公司去，
10. 你这样做就是很高概率的让每次上班都会迟到。
11. 例如 在考试时，考试最好的情况是考满分，
12. 然后你每次都考试都以为自己能考满分的蒙题而不去准备，
13. 你这样做的就是很高概率的让每次考试都会不及格。
14. 在大多数情况下去考虑最好的情况是没有多大意义的，
15. 在算法分析的领域通常会比较严格一些去考察最坏的情况。
5. 在添加操作时，自定义的动态数组容量已满
1. 就会进行 resize 操作，这个 resize 操作显然是`O(n)`，
2. 以为因为要给新数组重新赋值一遍。
#### 删除操作：时间复杂度为 O(n)
1. `removeLast()`：在数组末尾删除一个元素
1. 给末尾的数组元素设置默认值，然后`size--`，
2. 所以它的时间复杂度为 `O(1)`
3. `O(1)`的时间复杂度表示这个操作所消耗的时间
4. 与 数据的规模是没有关系的，
5. 他每次只是操作一个数组元素。
2. `removeFirst()`：在数组头部删除一个元素
1. 需要把数组中的元素都往前移动一个位置，
2. 所以这涉及到遍历数组中每一个元素，
3. 那么这个时间复杂度就为`O(n)`（操作 n 个元素），
4. 虽然最后也有`O(1)`（操作 1 个元素）的操作 ，
5. 给末尾的数组元素设置默认值，然后`size--`，
6. 但是在有`O(n)`情况时，
7. 更低阶项`O(1)`会被忽略掉。
3. `remove(index)`：删除指定索引位置处的元素并返回
1. 所以最好的情况下时间复杂就为`O(1)`，
2. 最坏的情况下时间复杂度就为`O(n)`，
3. 中等的情况下时间复杂度就为`O(n/2)`，
4. 忽略常数后这个算法的时间复杂度为`O(n)`。
4. 删除操作综合来看是一个`O(n)`级别的算法
1. `removeLast()`：`O(1)`，
2. `removeFirst()`：`O(n)`，
3. `remove(index)`：`O(n/2)=O(n)`。
5. 在删除操作时，自定义的动态数组中实际元素个数为其容量的一半时，
1. 就会进行 resize 操作，这个 resize 操作显然是`O(n)`，
2. 以为因为要给新数组重新赋值一遍。
#### 修改操作：时间复杂度为 O(1)
1. `set(index, e)`：指定索引修改一个元素的值
1. 简单的赋值操作，时间复杂度为`O(1)`。
2. 数组最大的优势就是支持随机访问，
3. 访问到对应索引的值后就可以修改对应索引的值了，
4. 性能超级好。
#### 查询操作：时间复杂度为 O(n)
1. `get(index)`：指定索引查找一个元素的值
1. 简单的获取操作，时间复杂度为`O(1)`。
2. 数组最大的优势就是支持随机访问，
3. 只要知道我要访问的索引是那个数字，
4. 就能够一下子访问到对应索引的值，
5. 性能超级好。
2. `contains(e)`：指定元素来查找，判断元素是否存在
1. 复杂的获取操作，时间复杂度为`O(n)`。
2. 需要遍历整个数组从而找到相同的元素，
3. 这个元素在数组中可能找的到也可能找不到，
4. 所以最好的情况下时间复杂就为`O(1)`，第一个，
5. 最坏的情况下时间复杂度就为`O(n)`，最后一个或者没找到，
6. 中等的情况下时间复杂度就为`O(n/2)`，在中间，
7. 忽略常数后这个算法的时间复杂度为`O(n)`，
8. 分析算法要关注最坏的情况。
3. `find(e)`：指定元素来查找，返回该元素对应的索引
1. 复杂的获取操作，时间复杂度为`O(n)`。
2. 需要遍历整个数组从而找到相同的元素，
3. 这个元素在数组中可能找的到也可能找不到，
4. 所以最好的情况下时间复杂就为`O(1)`，第一个，
5. 最坏的情况下时间复杂度就为`O(n)`，最后一个或者没找到，
6. 中等的情况下时间复杂度就为`O(n/2)`，在中间，
7. 忽略常数后这个算法的时间复杂度为`O(n)`，
8. 分析算法要关注最坏的情况。
#### 其它扩展操作
1. `removeElement(e)`：根据指定元素来进行删除第一相同的元素
1. 首先要进行遍历操作，然后找到指定元素的索引，
2. 最后根据索引来进行删除操作，删除操作中又会进行元素位置移动
3. 于是就有两轮循环了，所以时间复杂度为`O(n^2)`。
2. `removeAll(e)`：：根据指定元素来进行删除所有相同的元素
1. 首先要进行遍历操作，找到一个元素后就删除这个元素，
2. 会复用到`removeElement(e)`，于是有三轮循环了，
3. 所以这个操作是`O(n^3)`。
3. `findAll(e)`：根据指定元素来进行查找，找到所有的元素
1. 首先要进行遍历操作，找到一个元素后就将元素的索引存起来，
2.
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/73804.html
摘要：栈的实现栈这种数据结构非常有用但其实是非常简单的。其实栈顶元素反映了在嵌套的层级关系中，最新的需要匹配的元素。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现，全部文章大概的内容如下：Arrays(数组)、Stacks(栈)...
摘要：栈的实现栈这种数据结构非常有用但其实是非常简单的。其实栈顶元素反映了在嵌套的层级关系中，最新的需要匹配的元素。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现，全部文章大概的内容如下：Arrays(数组)、Stacks(栈)...
摘要：链表与递归已经从底层完整实现了一个单链表这样的数据结构，并且也依托链表这样的数据结构实现了栈和队列，在实现队列的时候对链表进行了一些改进。计算这个区间内的所有数字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现，全部文...
摘要：链表与递归已经从底层完整实现了一个单链表这样的数据结构，并且也依托链表这样的数据结构实现了栈和队列，在实现队列的时候对链表进行了一些改进。计算这个区间内的所有数字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现，全部文...
摘要：链表链表是最基础的动态数据结构链表是非常重要的线性数据结构以下三种，底层都是依托静态数组，靠解决固定容量问题。要清楚什么时候使用数组这样的静态数据结构，什么时候使用链表这类的动态数据结构。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【从蛋壳到满天飞】JAVA 数据结构解...
阅读 2114·2023-04-26 03:06
阅读 3525·2023-04-26 01:51
阅读 2050·2021-11-24 09:38
阅读 2423·2021-11-17 17:00
阅读 2283·2021-09-28 09:36
阅读 920·2021-09-24 09:47
阅读 2566·2019-08-30 15:54
阅读 1531·2019-08-30 15:44
