1、单链表
public class Node {
public int val;
public Node next;
public Node(int value) {
this.val = value;
}
}
1.1、单链表反转
1.2、代码实现
点击查看代码
public class ReverseList {
/**
* 反转单链表
* a -> b -> c -> null
* c -> b -> a -> null
*
* @param head 来源单链表头
* @return 反转后的链表头
*/
public static Node reverseLinkedList(Node head) {
if (head == null) {
return null;
}
Node pre = null;
Node next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
/**
* 用于测试： 利用 ArrayList 反转单链表
*
* @param head 带反转单链表头
* @return 反转后的链表头
*/
public static Node testReverseLinkedList(Node head) {
if (head == null) {
return null;
}
List<Node> list = new ArrayList<>();
while (head != null) {
list.add(head);
head = head.next;
}
list.get(0).next = null;
int size = list.size();
for (int i = 1; i < size; i++) {
list.get(i).next = list.get(i - 1);
}
return list.get(size - 1);
}
/**
* 获取单链表的值
*
* @param head 头
* @return 值组成的列表
*/
public static List<Integer> getLinkedListValue(Node head) {
List<Integer> res = new ArrayList<>();
Node pre = head;
while (pre != null) {
res.add(pre.val);
pre = pre.next;
}
return res;
}
/**
* 校验单链表反转是否正确
*
* @param originValues 链表反转前的值
* @param head 链表反转后的头节点
* @return true / false
*/
public static boolean checkLinkedListReverse(List<Integer> originValues, Node head) {
Node pre = head;
for (int i = originValues.size() - 1; i >= 0; i--) {
if (originValues.get(i) != pre.val) {
return false;
}
pre = pre.next;
}
return true;
}
public static void main(String[] args) {
int maxLen = 20;
int maxValue = 20;
int testTimes = 20;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
Node head = CustomCollectionUtils.generateRandomLinkedList(maxLen, maxValue);
Node head1 = CustomCollectionUtils.copyLinkedList(head);
List<Integer> originValues = getLinkedListValue(head);
head = reverseLinkedList(head);
head1 = testReverseLinkedList(head1);
List<Integer> reverseValues = getLinkedListValue(head);
List<Integer> reverseValues1 = getLinkedListValue(head1);
if (!reverseValues.containsAll(reverseValues1) || !reverseValues1.containsAll(reverseValues)) {
System.out.println("出错了！");
}
if (!checkLinkedListReverse(originValues, head) || !checkLinkedListReverse(originValues, head1)) {
System.out.println("出错了！");
}
}
System.out.println("测试结束！");
}
}
2、双链表
public class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int value) {
this.value = value;
}
}
2.1、双链表反转
2.2、代码实现
点击查看代码
public class ReverseDoubleList {
/**
* 反转双链表
* a <-> b <-> c <-> null
*
* @param head 头节点
* @return 反转后的链表头节点
*/
public static DoubleNode reverseDoubleList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
head.last = next;
pre = head;
head = next;
}
return pre;
}
/**
* 双链表反转，用于测试
* @param head 待反转链表头
* @return 反转后的链表头节点
*/
public static DoubleNode testReverseDoubleList(DoubleNode head) {
if (head == null) {
return null;
}
List<DoubleNode> list = new ArrayList<>();
while (head != null) {
list.add(head);
head = head.next;
}
list.get(0).next = null;
DoubleNode pre = list.get(0);
int size = list.size();
for (int i = 1; i < size; i++) {
DoubleNode cur = list.get(i);
cur.last = null;
cur.next = pre;
pre.last = cur;
pre = cur;
}
return list.get(size - 1);
}
/**
* 校验双链表反转
*
* @param originValues 原链表的值列表
* @param head 链表头节点
* @return true / false
*/
public static boolean checkDoubleListReverse(List<Integer> originValues, DoubleNode head) {
int size = originValues.size();
// 逆向对比
DoubleNode end = null;
for (int i = size - 1; i >= 0; i--) {
if (!Objects.equals(originValues.get(i), head.value)) {
return false;
}
end = head;
head = head.next;
}
// 正向对比
for (int i = 0; i < size; i++) {
if (!Objects.equals(originValues.get(i), end.value)) {
return false;
}
end = end.last;
}
return true;
}
/**
* 获取双链表的值
*
* @param head 头
* @return 值组成的列表
*/
public static List<Integer> getDoubleListValue(DoubleNode head) {
List<Integer> res = new ArrayList<>();
DoubleNode pre = head;
while (pre != null) {
res.add(pre.value);
pre = pre.next;
}
return res;
}
public static void main(String[] args) {
int maxLen = 10;
int maxValue = 20;
int testTimes = 300;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
DoubleNode head = CustomCollectionUtils.generateRandomDoubleList(maxLen, maxValue);
DoubleNode head1 = CustomCollectionUtils.copyDoubleList(head);
List<Integer> originValues = getDoubleListValue(head);
List<Integer> originValues1 = getDoubleListValue(head1);
head = reverseDoubleList(head);
head1 = testReverseDoubleList(head1);
// System.out.println("原链表值:" + originValues);
// System.out.println("反转后值:" + getDoubleListValue(head));
if (!checkDoubleListReverse(originValues, head) || !checkDoubleListReverse(originValues1, head1)) {
System.out.println(originValues);
System.out.println("出错了！");
break;
}
}
System.out.println("测试结束！");
}
}
3、队列
队列是一种特殊的线性表，遵循先进先出、后进后出的基本原则
队列主要分为阻塞和非阻塞，有界和无界、单向链表和双向链表之分；
java队列接口继承图：
3.1、单链表实现队列
3.2、双链表实现队列
3.3、数组实现队列
3.3.1、分析
- 准备两个指针，用于入队（tail）、出队（head）
- 准备一个变量 size 记录队列当前元素个数，解耦头、尾指针
- limit 队列元素最大个数
- 环形数组
3.3.2、代码实现
点击查看代码
public class RingArray {
public static class ArrayToQueue {
private int[] arr;
/**
* 在 arr 的 i位置添加元素
* end
*/
private int pushi;
/**
* 从 arr 的 i位置弹出元素
* begin
*/
private int polli;
private int size;
/**
* 队列最大长度
*/
private final int limit;
public ArrayToQueue(int limit) {
arr = new int[limit];
this.limit = limit;
}
public void push(int value) {
if (size == limit) {
throw new RuntimeException("队列已满！");
}
size++;
arr[pushi] = value;
pushi = nextIndex(pushi);
}
public int poll() {
if (size <= 0) {
throw new RuntimeException("我已经没有数据啦！");
}
int res = arr[polli];
polli = nextIndex(polli);
size--;
return res;
}
public int peek() {
return arr[polli];
}
public boolean isEmpty() {
return size == 0;
}
/**
* 根据当前位置，返回下一个位置
* @param i 当前下标
* @return 下一个位置下标
*/
private int nextIndex(int i) {
return i < limit - 1 ? i + 1 : 0;
}
}
public static void main(String[] args) {
ArrayToQueue queue = new ArrayToQueue(3);
queue.push(2);
queue.push(1);
queue.push(3);
while (!queue.isEmpty()) {
System.out.println(queue.poll());
}
queue.push(4);
System.out.println(queue.poll());
System.out.println(queue.poll());
}
}
4、栈
4.3、数组实现栈
- 准备一个栈顶指针head，用于操作出入栈
- 变量 size记录栈中元素个数
- limit 栈最大元素个数，即数组最大长度
4.3.2、代码实现
点击查看代码
public class ArrayToStack {
public static class ArrayImplStack {
private int[] arr;
private int head;
private int size;
private final int limit;
public ArrayImplStack(int limit) {
arr = new int[limit];
this.limit = limit;
}
public void push(int value) {
if (size >= limit) {
throw new RuntimeException("栈已经满了，不能添加数据！");
}
arr[head++] = value;
size++;
}
public int pop() {
if (size <= 0) {
throw new RuntimeException("我已经没有数据了！");
}
size--;
return arr[--head];
}
/**
* 查看栈顶元素，不出栈
*
* @return 栈顶元素
*/
public Integer peek() {
if (size <= 0) {
return null;
}
return arr[head - 1];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == limit;
}
}
public static void main(String[] args) {
int testTimes = 500;
// 每次测试数据个数
int oneTestDataNum = 100;
int value = 100;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
ArrayImplStack myStack = new ArrayImplStack(oneTestDataNum);
Stack<Integer> stack = new Stack<>();
for (int j = 0; j < oneTestDataNum; j++) {
int num = (int) (Math.random() * value);
if (myStack.isEmpty()) {
myStack.push(num);
stack.push(num);
} else {
// 栈未满，1/2的概率入栈，1/2出栈
if (!myStack.isFull() && (Math.random() < 0.5)) {
myStack.push(num);
stack.push(num);
} else {
if (!Objects.equals(myStack.pop(), stack.pop())) {
System.out.println("出错了！");
}
}
}
}
while (!myStack.isEmpty()) {
if (!Objects.equals(myStack.pop(), stack.pop())) {
System.out.println("出错了！");
}
}
}
System.out.println("测试结束");
}
}