数据结构-ArrayLIst-一起探索顺序表的底层实现
各位看官早安午安晚安呀假如您以为这篇文章对您有帮助的话
欢迎您一键三连，小编尽尽力做到更好
欢迎您分享给更多人哦
https://i-blog.csdnimg.cn/direct/151c4f80248f4633bb12f6fb03384638.png
大家好，我们本日来学习java数据结构的第一章ArrayList（顺序表）
1.ArrayList的概念
那小伙伴就要问了线性表到底是什么呢？ 线性表 （ linear list ） 是 n 个具有雷同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...（我们后续都会进行讲授） 线性表起首是一个序列，也就是说，元素之间是有顺序的，假如元素存在多个，那么第一个元素无前驱。末了一个元素无后驱。其他每个元素都必须有一个前驱和后驱。 例如： https://i-blog.csdnimg.cn/direct/bbb0069c34ed4c2eb2d9940848d3fa82.png usedSize这个变量黑白常紧张的，我们的增删查改都要用到 1.2ArrayList的模拟实现
import java.util.Arrays;
public class MyArrayList {
private int []elem;//用来存放数据
private int usedSize;//非常重要，代表当前顺序表当中的有效数据个数
private static final int DEFAULT_SIZE = 2;
public MyArrayList() {
this.elem = new int;
}
public MyArrayList(int initCapacity){
this.elem = new int;
}
// 新增元素,默认在数组最后新增
public void add(int data) {
if(elem.length == usedSize){
elem = Arrays.copyOf(elem,elem.length*2);
}
elem = data;
this.usedSize++;//一定不要忘记加
}
// 在 pos 位置新增元素
public void add(int pos, int data) {//只要带pos的都要进行检查
if(checkPos(pos) ==false ){
return;
}
if (elem.length == usedSize) {
elem = Arrays.copyOf(elem, elem.length * 2);
}
//下面这种写法就错误了，导致pos后面的值都是pos位置的值
/*for (int i = pos; i < usedSize -1; i++) {
elem = elem;
}*/
//应该从后往前
for (int i = usedSize-1 ; i >= pos; i--) {
elem = elem;
}
elem = data;
usedSize++;
}
/*public void delete(int pos){
if(checkPos(pos) == false)
if(this.usedSize == 0){
System.out.println("数组里面没有元素了");
return;
}
for (int i = 0; i < usedSize - 1; i++) {
elem = elem;
}
}
*/
// 判定是否包含某个元素
public boolean contains(int toFind) {//啥意思
for (int i = 0; i < usedSize; i++) {
if(elem == toFind ) //这里是int类型，所以你能够直接比较，其他类型的话，要重写equals方法
return true;
}
return false;
}
// 查找某个元素对应的位置
public int indexOf(int toFind) {
for (int i = 0; i < usedSize; i++) {
if(elem == toFind)
return i;
}
System.out.println("没有你要找的值");
return -1;
}
public boolean checkPos(int pos){
if( pos < 0 || pos >= usedSize){
System.out.println("下标错误");
return false;
}
return true;
}
// 获取 pos 位置的元素
public int get(int pos) {
if(checkPos(pos) == false){
return -1;
}
return elem;
}
// 给 pos 位置的元素设为 value
public void set(int pos, int value) {
if(checkPos(pos) == false){
return;
}
elem = value;
}
//删除第一次出现的关键字key
public void remove(int data) {
int index = this.indexOf(data);
if(index == -1){
System.out.println("没有这个数据");
return;
}
for (int i = data; i < usedSize - 1; i++) {
elem = elem;
}
//如果是引用类型的话： elem = null;
this.usedSize--;
}
// 获取顺序表长度
public int size() {
return this.usedSize;
}
// 清空顺序表
public void clear() {
this.usedSize = 0;
//但是如果是引用类型的话
/*
for (int i = 0; i < usedSize; i++) {
elem = null;
记得全部置为空
引用类型的话，删除也要置为null
}
*/
}
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
public void display() {
for (int i = 0; i < usedSize; i++) {
System.out.print(this.elem + " ");
}
}
}
目前我们自己实现了顺序表这种结构，以后用到的时间，Java已经为我们提供好了
ArrayList（就是一个平凡的类实现了List接口）
（自己看一下方法）（ArrayLIst内里的方法，底层方法）（我们可以看出来ArrsyList底层的数组我们在实例化对象时也是默认长度为我们的常量值，有效元素个数非常紧张，我们增加删除元素等方法都要用的）
https://i-blog.csdnimg.cn/direct/2d9c1a8da09f476db381fbb5cd8da35b.png
2：构造方法
我们要了解一个类起首要了解他的构造方法
ArrayList<E>中的E就表现列表中存储的元素的类型
ArrayList
https://i-blog.csdnimg.cn/direct/ca46b698449842d98b2b446b949f05ab.png
2.1:构造方法一，三
ArrayList<Integer> list = new ArrayList<>(); 这种能用的方法更多
List<Integer> list = new ArrayList<>(); 一般我们用这一种，向上转型，动态绑定的等等，你俩用哪个主要看自己业务场景
ArrayList<Integer> list = new ArrayList<>(15) 我们可以看到默认数组长度是10，前面源码图解上有
2.2:构造方法二
https://i-blog.csdnimg.cn/direct/e1bf7cac077f4586b5825b841507655e.png
https://i-blog.csdnimg.cn/direct/17864d74b90b435ab4b4dd9a03b0184f.png
然后我把list1指定的类型换成Integer就解决问题了！
https://i-blog.csdnimg.cn/direct/acb2057fb4b44df5b960f092a9d7b019.png
https://i-blog.csdnimg.cn/direct/235d48318dde439f9c51b23931db9ab3.png
大家也可以看到我显着对于list3只add了一次但是，打印出来的值却把list1数组内里的内容也拷贝过来了（拷贝在外面构造方法那一步就完成了）
2.3:ArrayList常见利用
https://i-blog.csdnimg.cn/direct/ef76657dc39c475c9c27d42bf9e0bf66.png
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(1,4);
System.out.println(list);//到这里是【1,4,2，3】
list.remove(1);//这两个老是搞混，这个是删除1小标的值
list.remove(new Integer(1));//要删除1这个元素的值一定要用这种方法，因为这个参数是Object类型的
System.out.println(list);//到这里是【2,3】
// list.get(2);//这里会报一个数组越界异常，就是用来和UsedSize比较
list.add(99);
list.add(100);
list.add(101);
boolean isFalse = list.contains(new Integer(100));//这里最好用Integer类型的
System.out.println(isFalse);//true
List<Integer> list1 = list.subList(1,4);//左闭右开
System.out.println(list1);
list.set(1,200);
System.out.println(list);
System.out.println(list1);
//list1得到的是从list数组里面的引用，只要改变其中一个元素的值，另一个也会改变
list.clear();
System.out.println(list);
//全部清除
} 2.4:ArrayList的三种遍历
ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
// 使用下标+for遍历
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
// 借助foreach遍历
for (Integer integer : list) {
System.out.print(integer + " ");
}
System.out.println();
//迭代器
Iterator<Integer> it = list.listIterator();
//ListIterator<Integer> it = list.listIterator();也可以
//ListIterator是Iterator的子类
while(it.hasNext()){
System.out.print(it.next() + " ");
}
System.out.println();
} 注意： 1. ArrayList 最长使用的遍历方式是： for 循环 + 下标 以及 foreach 2. 迭代器是设计模式的一种，后续博客我会继续讲授 2.5：ArrayList的扩容机制的缺陷
ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式 【 总结 】 1. 检测是否真正必要扩容，假如是调用 grow 准备扩容 2. 预估必要库容的大小 初步预估按照 1.5 倍大小扩容 ，假如用户所需大小超过预估1.5 倍大小，则按照用户所需大小扩容 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败 3. 使用 copyOf 进行扩容 3：杨辉三角
力扣杨辉三角
实现：
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Test {
public static void main(String[] args) {
int num = 5;
List<Integer> row = new ArrayList<>();
List<List<Integer>> ret = new ArrayList<>();
row.add(1);
ret.add(row);
for (int i = 1; i < num; i++) {
List<Integer> curRow1 = new ArrayList<>();
curRow1.add(1);//每行的第一个元素都是1
List<Integer> previousRow = ret.get(i - 1);
for (int j = 1; j < i; j++) {
Integer x = previousRow.get(j) + previousRow.get(j - 1);
curRow1.add(x);
}
curRow1.add(1);//每行的最后一个元素也都是1
ret.add(curRow1);//把这一行的数组加进去
}
for (List<Integer>list:ret //遍历数组
) {
System.out.println(list);
}
System.out.println("============================");
Iterator<List <Integer>> it = ret.listIterator();//使用迭代器遍历数组
//ListIterator<Integer> it = list.listIterator();也可以
//ListIterator是Iterator的子类
while(it.hasNext()){
System.out.print(it.next() + " ");
System.out.println();
}
}
}
https://i-blog.csdnimg.cn/direct/c1c6ccfdd8254dd28f608c76548852b8.png
上述就是数据结构-ArrayLIst-数组的深入包装 的全部内容了，能看到这里相信您肯定对小编的文章有了肯定的认可，数据结构的出现让我们对于数据的组织的使用有了更加方便的使用~~
有什么问题欢迎各位大佬指出
欢迎各位大佬评论区留言修正
https://i-blog.csdnimg.cn/direct/5def8730f07040478b2dc56b9fc7b7a8.pnghttps://i-blog.csdnimg.cn/direct/2d8b40093abe47c7b347cdd7c906e87f.gif
您的支持就是我最大的动力！！！！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]