java刷题 各种数据结构_java笔试数据结构

一、链表节点

java IDE是没有ListNode，ListNode类是力扣题目给你提供的自定义的节点类，LinkedList是java原生的双向链表类，节点类Node存在于内部，从外部访问不到。
区别是节点类提供next或/和pre字段访问前后节点，而链表类是把节点类封装起来了，给你提供获取节点的方法，比如你调用get(n),链表类就帮你从头节点挨个next到这个节点给你返回。链表类基于节点类实现。

public class ListNode{
   
	public int val;
	public ListNode next;
	public ListNode(int val){
   
		this.val=val;
	}
}
1
2
3
4
5
6
7
8
9

用哨兵节点简化链表插入操作

public ListNode append(ListNode head,int val){
   
	ListNode dummy=new ListNode(0);//建立哨兵节点
	dummy.next=head;//在哨兵节点后面添加head
	ListNode newNode=new ListNode(val);
	ListNode node=dummy;
	while(node.next!=null){
   
		node=node.next;
	}
	node.next=newNode;
	return dummy.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

用哨兵节点简化链表删除操作（哨兵节点的好处是也可以删除头结点）

public static ListNode delete(ListNode head,int value){
   
	ListNode dummy=new ListNode(0);
	dummy.next=head;//将head插到dummy后面

	ListNode node=dummy;
	while(node.next!=null){
   
		if(node.next.value==value){
   
			node.next=node.next.next;
			break;//找到删除节点就删除了，不再继续循环下去
		}
		node=node.next;
	}
	return dummy.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二、哈希表

在java中，哈希表有两个对应的类型，即HashSet和HashMap。如果每个元素都只有一个值，则用HashSet，HashSet在图搜索时经常用来存储已经搜索过的节点。如果每个元素都存在一个值到另一个值的映射，那么用HashMap。例如：如果不仅要存储一个文档中的所有单词，同时还关心每个单词在文档中出现的位置，则可以考虑用HashMap。

HashSet常用函数

HashMap常用函数

不一定都要用哈希表解决问题。如果对数据集中的元素排序能够有助于解决问题，那么用TreeSet或TreeMap更合适。如果需要知道一个动态数据集中的最大值和最小值，那么堆的效率可能更好。如果希望能够根据前缀进行单词查找，如查找字典中所有以“ex”开头的单词，那么应该用前缀树作为实现字典的数据结构。

三、栈

Stack<Integer> times=new Stack<>();
1

四、队列