Java数据结构（1）

我以前是跟着代码随想录的卡哥刷题，卡哥讲得很好，但有时候我不能很好理解卡哥的讲解。最近同学借给我了这本书，并且强推，我就决定把这本书学一遍，争取下次面试中手撕代码更流畅。（我昨天一面手撕代码有点拉胯，简单题还做了半小时）

• • labuladong算法小抄学习——（1）`Java`语言基础
• 数组
• 字符串 `String`
• 动态数组`ArrayList`
• 小复习
• 双链表`LinkedList`
• 哈希表`HashMap`
• 哈希集合`HashSet`
• 队列`Queue`
• 堆栈`Stack`
• 总结

//初始化方法
int m=5,n=10;
//初始化一个大小为10的int数组
//其中的值默认初始化为0
int[] num=new int[n];
//初始化一个m*n的二维布尔数组
//其中的元素默认初始化为false
boolean[][] visited=new boolean[m][n]; 

Java中数组在有的题目中会以函数参数的形式传入，一般来说要在函数开头做一个非空检查，平时做题很容易漏，如果手撕代码过程中不写，面试官也会减分。

if(nums.length==0){
	return;
}
for(int i=0;i
	//访问nums[i]
}

``

Java的字符串不支持以下标的形式直接访问其中的字符，较为麻烦，而且不能直接修改，要转化为char[] 类型后才能修改，即变成字符数组后，以数组的形式修改

String s1="hello csdn";
//获取s1[2]中的字符
//切记charAt()方法返回的是字符
char c=s1.charAt(2);
//字符串转字符数组的方法
char[] chars=s1.toCharArray();
chars[1]='e';
//用构造器直接把字符数组转化为字符串
String s2=new String(chars);
//输出 “hello csdn”
System.out.println(s2);

//判断字符串是否相同一定要用equals()方法
if(s1.equals(s2)){
	//s1和s2相同
}else{
	//s1和s2不相同
}
//字符串可以用加号进行拼接
String s3=s1+"!";
//输出“hello csdn!”
System.out.println(s3);

Java的字符串不能直接修改，要用toCharArray()方法转化为char[]类型的字符数组后进行修改，然后转换为String类型
另外，虽然字符串能用+拼接，但效率太低。优秀的数据结构那么多，手撕代码中这样写，面试官可能会减分。如果需要频繁的字符串拼接，比如在for循环中大量拼接，推荐使用StringBuilder,暂时只需要知道他是线程不安全，可以修改的并且修改效率最高的字符串类型即可。
下面的toString()以及append()方法望诸君记牢

StringBuilder sb=new StringBuilder();
for(char c='a';c<='f';c++){
    sb.append(c);
}
//append方法支持拼接字符、字符串、数字等类型
sb.append('g').append('h').append(123);
String res=sb.toString();
//输出 abcdefgh123
System.out.println(res);

是很重要的一种数据类型，是普通数组的一种包装

//初始化一个存储String类型数据的动态数组
ArrayList nums=new ArrayList<>();
//初始化一个存储int类型数据的动态数组
ArrayList smun=new ArrayList<>();

常用方法如下，其中我用IDEA里面的var快捷键自动生成的等号左侧，理解意思即可

//在数组尾部添加元素
boolean add = smun.add(1);
//判断数组是否为空
boolean empty = smun.isEmpty();
//返回数组中元素的个数
int size = smun.size();
//返回索引index处的元素
Integer integer = smun.get(1);

我们上面总结了三种简单的数据结构，现在复习一下，防止混淆

数组的玩法：值得复习的只有一个二维数组创建方式 int[][] erwei=new int[2][3]
字符串玩法：toCharArray()转化为字符数组， 目的是可以根据索引读取和修改，字符串比较方法equals(),
StringBuilder是更为好用数据结构，其中有append()方法来增加元素，toString()可以将其转为字符串
动态数组ArrayList：get(),size(),isEmpty(),add();四大方法，两个需要参数，两个是无参方法

ArrayList是用列表底层实现的，而LinkedList底层是用双链表实现的，初始化方法也是类似的

//初始化一个存储int类型数据的双链表
LinkedList nums =new LinkedList<>();
//初始化一个存储String类型结构的双链表
LinkedList strings=new LinkedList<>();

我们需要掌握的几个方法如下

//判断双链表是否为空
boolean empty = nums.isEmpty();
//返回链表中元素的个数
int size = nums.size();
//判断链表中是否存在元素0；
boolean contains = nums.contains(0);
//在链表尾部添加元素 1；
boolean add = nums.add(1);
//在链表头部添加元素2
nums.addFirst(2);
//删除链表头部的第一个元素
nums.removeFirst();
//删除链表尾部的最后一个元素
nums.removeLast();

可见我们重点利用LinkedList进行头部和尾部的元素操作，因为是底层是链表，所以操作头尾元素效率更高，而contains（）函数较慢，因为要遍历整个链表才能判断元素是否存在，时间复杂度为O（N）

初始化方法：

//整数映射到字符串的哈希表
HashMap map=new HashMap<>();
//字符串映射到数组的哈希表
HashMap map1=new HashMap<>();

我们需要掌握的方法

//判断哈希表中是否有键key
boolean abc = map.containsKey(123);
//获取键key对应的值，若key不存在，则返回null
String abc1 = map.get("abc");
//将key和value放入哈希表
String abc2 = map.put(123,"abc");
//获取key值，如果key不存在，则返回defaultValue(设定好的默认值）
String dnf = map.getOrDefault(456, "dnf");
//获取哈希表中所有key
Set integers = map.keySet();

//如果key不存在，则键值对key和value存入哈希表
//如果key存在，则什么都不做
map.putIfAbsent(123,"lpl");

初始化方法

//新建一个存储String的哈希集合
HashSet set=new HashSet<>();

我们需要掌握的方法

//如果不存在此，就将其加入到哈希集合
boolean abc = set.add("abc");
//判断元素某是否存在于哈希集合中
boolean abc1 = set.contains("abc");
//如果元素某存在，则删除元素某
boolean abc2 = set.remove("abc");

Queue和前面学的不同，它是一个接口，因此它的初始化方法些许不同
初始化如下

//新建一个存储String的队列
Queue q=new LinkedList<>();

我们需要掌握的方法如下

//判断队列是否为空
boolean empty = q.isEmpty();
//返回列中元素的个数
int size = q.size();
//返回队头的元素
String peek = q.peek();
//删除并返回队头的元素
String poll = q.poll();
//将元素某插入队尾
boolean abc = q.offer("abc");

初始化方法

Stack s=new Stack<>();

需要掌握的方法

//判断栈是否为空
boolean empty = s.isEmpty();
//返回堆栈中元素的个数
int size = s.size();
//将元素压入栈顶
Integer push = s.push(123);
//返回栈顶元素
Integer peek = s.peek();
//删除并返回栈顶元素
Integer pop = s.pop();

数据结构是很重要的，我们只有了解各种数据结构的特点，才能在做题的时候准确的选择数据结构，各种方法也很重要，虽然IDEA里面都有提示，但还是记住的好