常用数据结构与算法实现
以下博客根据B站罗召勇老师视频：数据结构与算法基础-Java版（罗召勇）写的详细笔记
数据结构与算法基础：
数据结构与算法之基础概述
数据结构：
（一）数据结构与算法之数组
（二）数组结构与算法之栈
（三）数据结构与算法之队列
（四）数据结构与算法之链表
（五）数据结构与算法之树结构基础
（六）数据结构与算法之二叉树大全
（七）数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)
（八）数据结构与算法之多路查找树（2-3树、2-3-4树、B树、B+树）
（九）数据结构与算法之图结构
十大经典算法：
（一）数据结构与算法之冒泡排序（含改进版）
（二）数据结构与算法之选择排序（含改进版）
（三）数据结构与算法之插入排序（含改进版）
（四）数据结构与算法之希尔排序
（五）数据结构与算法之归并排序
（六）数据结构与算法之快速排序
（七）数据结构与算法之堆排序
（八）数据结构与算法之计数排序
（九）数据结构与算法之桶排序
（十）数据结构与算法之基数排序
单链表
概念
单链表也叫单向链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
表元素域data用来存放具体的数据。
链接域next用来存放下一个节点的位置
单链表操作
is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在
实现类：
//一个节点 public class Node { //节点内容 int data; //下一个节点 Node next; public Node(int data) { this.data = data; } //为节点追加节点 public Node append(Node node) { //当前节点 Node currentNode = this; //循环向后找 while (true) { //取出下一个节点 Node nextNode = currentNode.next(); //如果下一个节点为null，当前节点已经是最后一个节点 if (nextNode == null) { break; } //赋给当前节点，无线向后找 currentNode = nextNode; } //把需要追加的节点，追加为找到的当前节点（最后一个节点）的下一个节点 currentNode.next = node; return this; } //显示所有节点信息 public void show() { Node currentNode = this; while (true) { System.out.print(currentNode.data + " "); //取出下一个节点 currentNode = currentNode.next; //如果是最后一个节点 if (currentNode == null) { break; } } System.out.println(); } //插入一个节点作为当前节点的下一个节点 public void after(Node node) { //取出下一个节点，作为下下一个节点 Node nextNext = next; //把新节点作为当前节点的下一个节点 this.next = node; //把下下一个节点设置为新节点的下一个节点 node.next = nextNext; } //删除下一个节点 public void removeNode() { //取出下下一个节点 Node newNext = next.next; //把下下一个节点设置为当前节点的下一个节点 this.next = newNext; } //获取下一个节点 public Node next() { return this.next; } //获取节点中的数据 public int getData() { return this.data; } //判断节点是否为最后一个节点 public boolean isLast() { return next == null; } }
测试类：
public class Demo { public static void main(String[] args) { //创建节点 Node n1 = new Node(1); Node n2 = new Node(2); Node n3 = new Node(3); //追加节点 n1.append(n2).append(n3); //取出下一个节点数据 System.out.println(n1.next().next().getData()); //3 //判断节点是否为最后一个节点 System.out.println(n1.isLast()); //false System.out.println(n1.next().next().isLast()); //true //显示所有节点信息 n1.show(); //1 2 3 //删除一个节点 // n1.next.removeNode(); // n1.show(); //1 2 //插入一个新节点 n1.next.after(new Node(0)); n1.show(); //1 2 0 3 } }
循环链表
概念
单链表的一个变形是单向循环链表，链表中最后一个节点的 next 域不再为 None，而是指向链表的头节点。
循环链表操作
实现类：
//表示一个节点 public class LoopNode { //节点内容 int data; //下一个节点 LoopNode next = this; //与单链表的区别，追加了一个this，当只有一个节点时指向自己 public LoopNode(int data) { this.data = data; } //插入一个节点 public void after(LoopNode node) { LoopNode afterNode = this.next; this.next = node; node.next = afterNode; } //删除一个节点 public void removeNext() { LoopNode newNode = this.next.next; this.next = newNode; } //获取下一个节点 public LoopNode next() { return this.next; } //获取节点中的数据 public int getData() { return this.data; } }
测试类：
public class Demo { public static void main(String[] args) { //创建节点 LoopNode n1 = new LoopNode(1); LoopNode n2 = new LoopNode(2); LoopNode n3 = new LoopNode(3); LoopNode n4 = new LoopNode(4); //增加节点 n1.after(n2); n2.after(n3); n3.after(n4); System.out.println(n1.next().getData()); //2 System.out.println(n2.next().getData()); //3 System.out.println(n3.next().getData()); //4 System.out.println(n4.next().getData()); //1 } }
双向循环链表
概念
在双向链表中有两个指针域，一个是指向前驱结点的prev，一个是指向后继结点的next指针
双向循环链表操作
实现类：
public class DoubleNode { //上一个节点 DoubleNode pre = this; //下一个节点 DoubleNode next = this; //节点数据 int data; public DoubleNode(int data) { this.data = data; } //增加节点 public void after(DoubleNode node) { //原来的下一个节点 DoubleNode nextNext = next; //新节点作为当前节点的下一个节点 this.next = node; //当前节点作为新节点的前一个节点 node.pre = this; //原来的下一个节点作为新节点的下一个节点 node.next = nextNext; //原来的下一个节点的上一个节点为新节点 nextNext.pre = node; } //获取下一个节点 public DoubleNode getNext() { return this.next; } //获取上一个节点 public DoubleNode getPre() { return this.pre; } //获取数据 public int getData() { return this.data; } }
测试类：
public class Demo { public static void main(String[] args) { //创建节点 DoubleNode n1 = new DoubleNode(1); DoubleNode n2 = new DoubleNode(2); DoubleNode n3 = new DoubleNode(3); //追加节点 n1.after(n2); n2.after(n3); //查看上一个，自己，下一个节点内容 System.out.println(n2.getPre().getData()); //1 System.out.println(n2.getData()); //2 System.out.println(n2.getNext().getData()); //3 System.out.println(n1.getPre().getData()); //3 System.out.println(n3.getNext().getData()); //1 } }
