1.单链表的数据结构+案例
2.双链表的数据结构+案例
3.栈的数据结构(双向链表+数组实现) + 案例
4.队列的数据结构(双向链表+数组实现)
5.写一个NodeUtils工具类
6.全部的代码+测试用例gitee仓库自取
1.单链表的数据结构和案例
单向链表
/**
* 构造一个单向链表
*/
public class Node <T> {
// 该节点的值 value
public T value;
// 该节点指向的下一节点
public Node nextNode;
// 构造函数
public Node(T value){
this.value = value;
}
}
案例1：给定一个链表，如何反转链表？
/**
* @author Tara
* @implNote 给定一个单向链表，如何反转链表？
*/
public class Pra1 {
public static void main(String[] args) {
Object[] arr = {2, 4, 7, 9, 23, 21};
// 构造一个链表
Node node = NodeUtils.constructNode(arr);
// 打印链表轨迹
NodeUtils.printSingleNode(node);
// 反转链表
Node node1 = reverseLinkedList(node);
//打印链表结构
NodeUtils.printSingleNode(node1);
}
//反转链表
public static Node reverseLinkedList(Node head){
Node preNode = null;
Node nextNode = null;
while (null!=head){
nextNode = head.nextNode;
head.nextNode = preNode;
preNode = head;
head = nextNode;
}
while (null!=head){
System.out.print(head.value+" -> ");
}
return preNode;
}
}
案例2：把给定的node节点中有指定值的节点全部移除
/**
* @author Tara
* @implNote 给定一个链表，删除所有节点值为x的节点，并返回头节点
*/
public class Pra2 {
public static void main(String[] args) {
Object[] arr = {3, 2, 4, 7, 9, 3, 3, 2, 3, 23, 21};
// 构造一个链表
Node node = NodeUtils.constructNode(arr);
// 打印链表轨迹
NodeUtils.printSingleNode(node);
// 移除所有值为3的节点
Node node1 = removeValues(node,2);
//打印链表结构
NodeUtils.printSingleNode(node1);
}
//移除单向链表的值为xx的节点
private static Node removeValues(Node head, Object value) {
// 1.考虑head第一位是否存在要移除的节点
while (null != head) {
// 先排除head位置存在要移除的节点
if (head.value != value) {
// 首位没有符合条件的就停止。
break;
}
head = head.nextNode;
}
// 2.考虑 中间是否存在要移除的节点，存在就跳过去，不存在指针指向下一个
// 游标指向当前节点
Node cur = head;
Node pre = null;
while (null != cur) {
if (cur.value == value) {
pre.nextNode = cur.nextNode;
} else {
pre = cur;
}
cur = cur.nextNode;
}
return head;
}
}
2.双链表的数据结构和案例
双向链表
/**
* 构造一个双向链表
* @param <T>
*/
public class DoubleNode <T> {
//该节点的值
public T value;
// 该节点指向的上一个节点
public DoubleNode lastNode;
// 该节点指向的下一节点
public DoubleNode nextNode;
// 双向链表的构造方法
public DoubleNode(T value){
this.value = value;
}
}
案例1：给定一个双向链表，如何反转双向链表？
/**
* @author Tara
* @implNote 给定一个双向链表，如何反转双向链表？
*/
public class Pra3 {
public static void main(String[] args) {
Object[] arr = {2, 4, 7, 9, 23, 21, 8 , 43};
// 构造一个双向链表
DoubleNode node = NodeUtils.constructDoubleNode(arr);
// 打印链表轨迹
NodeUtils.printDoubleNode(node);
//打印链表结构
NodeUtils.printDoubleNode2(node);
System.out.println("=====================反转双向链表======================");
DoubleNode node1 = reverseDoubleNodeList(node);
NodeUtils.printDoubleNode(node1);
NodeUtils.printDoubleNode2(node1);
}
//反转双向链表
public static DoubleNode reverseDoubleNodeList(DoubleNode head){
DoubleNode preNode = null;
DoubleNode nextNode = null;
while (null!=head){
nextNode = head.nextNode;
head.nextNode = preNode;
head.lastNode = nextNode;
preNode = head;
head = nextNode;
}
return preNode;
}
}
案例2：给定一个双向链表，删除所有节点值为x的节点，并返回头节点head
/**
* @author Tara
* @implNote 给定一个双向链表，删除所有节点值为x的节点，并返回头节点head
*/
public class Pra4 {
public static void main(String[] args) {
Object[] arr = {3, 2, 4, 7, 9, 3, 3, 2, 3, 23, 21};
// 构造一个链表
DoubleNode node = NodeUtils.constructDoubleNode(arr);
// 打印链表轨迹
NodeUtils.printDoubleNode(node);
NodeUtils.printDoubleNode2(node);
// 移除所有值为3的节点
DoubleNode removedNode = removeValues(node, 2);
//打印链表结构
NodeUtils.printDoubleNode(removedNode);
NodeUtils.printDoubleNode2(removedNode);
}
/**
* 移除单向链表的值为xx的节点
* @param head 双链表的一个头部
* @param value 要移除节点的值value；
* @return 新头部节点newHead
*/
private static DoubleNode removeValues(DoubleNode head, Object value) {
// 1.考虑head第一位是否存在要移除的节点
while (null != head) {
// 先排除head位置存在要移除的节点
if (head.value != value) {
// 首位没有符合条件的就停止。
break;
}
head = head.nextNode;
//指针后移后，上一个指针置空；
head.lastNode = null;
}
// 2.考虑 中间是否存在要移除的节点，存在就跳过去，不存在指针指向下一个
// 游标指向当前节点
DoubleNode cur = head;
DoubleNode pre = null;
DoubleNode next = null;
while (null != cur) {
// 记录指针的下一节点
next = cur.nextNode;
if (cur.value == value) {
// 直接将当前节点指向下一节点，跳过cur；
pre.nextNode = next;
// 释放当前节点的指向
cur.nextNode = null;
cur.lastNode = null;
// 让下一个节点往回指；
next.lastNode = pre;
} else {
// 当前节点变为下一次的pre节点
pre = cur;
}
//游标后移
cur = next;
}
return head;
}
}
3.栈的数据结构(双向链表+数组实现) + 案例
双向链表实现
/**
* 使用双向队列实现栈
* @param <T>
*/
public class Stack<T> {
private DoubleEndsQueue<T> queue;
// 构造方法
public Stack(){
queue = new DoubleEndsQueue<>();
}
/**
* 压栈操作
* @param value
*/
public void push(T value){
queue.addFromHead(value);
}
// 取值
public T pop(){
return queue.popFromHead();
}
/**
* 判断栈是否为空
* @return
*/
public boolean isEmpty(){
return queue.isEmpty();
}
}
数组实现
/**
* 使用数组实现固定长度的栈
*/
public class Stack {
// 存值的数组；
private Object[] arr;
// 栈顶部的索引；
private int index;
//初始化长度；
private final int limit;
// 构造方法初始化
public Stack(int limit) {
this.arr = new Object[limit];
this.index = 0;
this.limit = limit;
}
// 压栈操作
public void push(Object value) {
if (index == limit) {
throw new RuntimeException("栈已经满了，不能再装了");
}
this.arr[index] = value;
index++;
}
// 取栈顶元素；
public Object pop() {
if (index == 0) {
throw new RuntimeException("栈已经空了，不能再取了");
}
index--;
Object temp = this.arr[index];
this.arr[index] = null;
return temp;
}
// 栈为空判断
public boolean isEmpty() {
return index == 0;
}
@Override
public String toString() {
String str = "";
for (int i = 0; i < arr.length; i++) {
str += arr[i] + ",";
}
return str;
}
}
案例1：设计一个栈StackMin来实现，向栈中加入若干个值，以最高的效率取出栈中的最小值，设计出O(l)的方案
/**
* @Author: Tara.Li(李春侣)
* @Contact Me WeChat: flyme9988
* @ReWroteBy:
* @Date: 2021-12-19 20:23:08
* @Description: 设计一个栈，无论怎么压栈，弹出，都能以最小的时间复杂度，获取栈中的最小元素。
*/
public class StackMin {
//定义一个正常存储的栈
private Stack<Integer> stackData;
// 定义一个存储最小元素的栈，
private Stack<Integer> stackMin;
//构造函数
public StackMin() {
stackData = new Stack<>();
stackMin = new Stack<>();
}
/**
* 压栈
* @param newNum 新压入栈的值
*/
public void push(int newNum){
//如果记录最小值的栈为空，，即为第一个元素，直接两个栈都进。
if (this.stackMin.isEmpty()){
stackMin.push(newNum);
// 如果新压入的元素小于stackMin元素的栈顶元素，就压入栈顶。
}else if (newNum < this.stackMin.peek()) {
stackMin.push(newNum);
// 如果新压入的元素大于等于stackMin元素，就再压一次栈顶元素。
}else if (newNum >= this.stackMin.peek()){
Integer temp = this.stackMin.peek();
this.stackMin.push(temp);
}
// 无论stackMin怎么变动，stackData都是正常push值的
stackData.push(newNum);
}
/**
* 弹出按照正常情况弹出stackData栈的数据
* @return
*/
public Object pop(){
//判断栈是不是为空
if (stackData.isEmpty()){
throw new RuntimeException("当前栈元素已经空了");
}
// 两个同步弹出，保证栈内元素一致。
stackMin.pop();
return stackData.pop();
}
/**
* 获取最小元素
* @return
*/
public Object getMin(){
//判断栈是不是为空
if (stackData.isEmpty()){
throw new RuntimeException("当前栈元素已经空了");
}
//当前栈顶永远存储的是最小元素。
return this.stackMin.peek();
}
}
测试案例1
/**
* @author Tara
* @implNote 取任意一个栈，栈中的最小元素，设计出O(l)的方案
*/
public class Pra9 {
public static void main(String[] args) {
StackMin stack = new StackMin();
// 想栈中加入最小元素
stack.push(8);
stack.push(2);
stack.push(3);
stack.push(2);
stack.push(3);
stack.push(5);
stack.push(7);
stack.push(3);
stack.push(99);
stack.push(0);
stack.push(12);
stack.push(17);
stack.push(19);
stack.push(13);
System.out.println("最小元素为："+stack.getMin());
// 当前栈中的元素为：
for (int i = 0; i < 15; i++) {
System.out.print(stack.pop()+",");
}
}
}
4.队列的数据结构(双向链表+数组实现)
双向链表实现
/**
* 使用双向链表实现队列
* @param <T>
*/
public class Queue<T> {
// 初始化一个双向链表
private DoubleEndsQueue<T> queue;
public Queue(){
queue = new DoubleEndsQueue<>();
}
/**
* 放进队列
* @param value
*/
public void push(T value){
queue.addFromHead(value);
}
/**
* 从队列中取出
* @return
*/
public T poll(){
return queue.popFromBottom();
}
/**
* 判断是否为空
* @return
*/
public boolean isEmpty(){
return queue.isEmpty();
}
}
数组实现
/**
* 使用数组实现固定 长度的队列
*/
public class Queue {
// 数组实现
private Object[] arr;
// 添加元素位置标记
private int pushi;
// 弹出元素位置标记
private int polli;
// 用于记录当前占用了几个空间，最大空间是limit
private int size;
// 队列大小
private final int limit;
//构造方法
public Queue(int limit) {
this.arr = new Object[limit];
pushi = 0;
polli = 0;
size = 0;
this.limit = limit;
}
//队列中添加值value
public void push(Object value) {
if (size == limit) {
throw new RuntimeException("队列满了，不能再push了");
}
// 占用空间+1；
size++;
// 当前位置指针存储值
arr[pushi] = value;
// 前置指针往下一个位置指；
pushi = nextIndex(pushi);
}
//取出一个队列中的值
public Object pop() {
if (size == 0) {
throw new RuntimeException("队列空了，不能再poll了");
}
//占用空间--
size--;
Object temp = arr[polli];
arr[polli] = 0; // 回收，值置空
polli = nextIndex(polli);
return temp;
}
/**
* 获取下一个位置索引
*
* @param i 遇到最大位置，直接跳到0，实现循环复用
* @return
*/
private int nextIndex(int i) {
// limit-1是最后一个元素 ，如果到了最后一个元素，下一个就返回到0，否则，继续往下索引；
return i < limit - 1 ? i + 1 : 0;
}
// 队列是否为空
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
String str = "";
for (int i = 0; i < arr.length; i++) {
str += arr[i].toString() + ",";
}
return str;
}
}
结尾：部分工具类代码
双向链表写的队列方法DoubleEndsQueue
/**
* 定义一个双头链表队列，可以从头部插入，头部移除，尾部插入，尾部移除
*
* @param <T>
*/
public class DoubleEndsQueue<T> {
//用双向链表 定义 头部，和尾部指针
public DoubleNode head;
public DoubleNode tail;
/**
* 从头部向队列中添加值
*
* @param value
*/
public void addFromHead(T value) {
// 创建一个节点存储传进来的value
DoubleNode cur = new DoubleNode(value);
// 如果当前队列为空（没有节点）,则头，尾都指向这个新节点cur
if (null == head) {
head = cur;
tail = cur;
} else {//节点不为空，往头部添加，head前移，尾部不动
cur.nextNode = head;
head.lastNode = cur;
head = cur;
}
}
/**
* 从尾部向队列中添加值
*
* @param value
*/
public void addFromBottom(T value) {
DoubleNode<T> cur = new DoubleNode(value);
if (null == head) {
head = cur;
tail = cur;
} else {
cur.lastNode = tail;
tail.nextNode = cur;
tail = cur;
}
}
/**
* 从头部取值
*
* @return
*/
public T popFromHead() {
if (null == head) {
return null;
}
DoubleNode<T> cur = head;
// 头部和尾部指向同一个节点==>只有一个节点
if (head == tail) {
head = null;
tail = null;
} else { // 有两个及以上节点
head = head.nextNode;
head.lastNode = null;
cur.nextNode = null;
}
return cur.value;
}
/**
* 从尾部取值
*
* @return
*/
public T popFromBottom() {
if (null == head) {
return null;
}
DoubleNode<T> cur = tail;
// 只有一个元素
if (head == tail) {
head = null;
tail = null;
} else { // 有两个及以上元素
tail = tail.lastNode;
tail.nextNode = null;
cur.lastNode = null;
}
// 返回底部元素；
return cur.value;
}
// 判断栈是否为空
public boolean isEmpty() {
return head == null;
}
}
