02、数据结构与算法 - 实战：链表
1、链表基本介绍
链表是有序的列表，在内存中的存储如下：
1、链表是以结点的方式来存储，是链式存储；
2、每个结点都包含data域、next域；
3、链表的每个结点在存储上不一定连续；
4、链表分带头结点和不带头结点的链表，根据实际需求而定；
带头结点的链表示意图：
2、单向链表
单向链表指的是只有一个方向。
2.1 单向链表的结点类
package cn.klb.datastructures.linkedlist;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 单向链表结点类
* @Date: Create in 2023/3/31 12:51
* @Modified By:
*/
public class SinglyNode {
public int no; // 编号
public String data; // 字符串数据
public SinglyNode next; // 指向下一个结点
/**
* 构造方法，不带next
*
* @param no
* @param data
*/
public SinglyNode(int no, String data) {
this.no = no;
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", data='" + data + '\'' +
'}';
}
}
2.2 单向链表类
package cn.klb.datastructures.linkedlist;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description:
* @Date: Create in 2023/3/30 20:13
* @Modified By:
*/
public class SinglyLinkedList {
private SinglyNode head = new SinglyNode(0, ""); // 定义头结点
public SinglyNode getHead() {
return head;
}
/**
* 添加结点
* 模式：不考虑编号顺序，直接添加到链表末尾
* 思路：找到链表的末尾结点，末尾结点的next指向新结点
*
* @param SinglyNode
*/
public void add(SinglyNode SinglyNode) {
SinglyNode temp = head; // temp理解为一个结点索引
// 从head开始，遍历链表，找到next为null的就是最后一个结点
while (true) {
if (temp.next == null) {
break;
} else {
temp = temp.next;
}
}
// 跳出while循环，表明当前temp就是最后一个结点
temp.next = SinglyNode;
}
/**
* 添加结点
* 模式：考虑编号顺序，整体链表的元素的编号从小到大排列
* 思路：找到链表的末尾结点，末尾结点的next指向新结点
*
* @param SinglyNode
*/
public void addByNo(SinglyNode SinglyNode) {
SinglyNode temp = head; // temp理解为一个结点索引
boolean existFlag = false; // 编号已存在，则不能插入
// 从head开始，遍历链表
while (true) {
// 如果temp已经是最后一个结点，则直接插入
if (temp.next == null) {
break;
}
// 如果下一个结点的编号大于要插入的结点编号，则可以插入
if (temp.next.no > SinglyNode.no) {
break;
}
// 如果找到相等编号，则不能插入
if (temp.next.no == SinglyNode.no) {
existFlag = true;
break;
}
temp = temp.next;
}
if (existFlag) {
System.out.println("编号已存在，插入失败！");
} else {
SinglyNode.next = temp.next;
temp.next = SinglyNode;
}
}
/**
* 修改结点
* 覆盖编号相同的结点的data
*
* @param SinglyNode
*/
public void update(SinglyNode SinglyNode) {
// 判断链表是否为空
if (head.next == null) {
System.out.println("链表是空的，没的修改了。");
} else {
SinglyNode temp = head;
// 找到和相同编号的结点
while (true) {
// 找到相同编号结点
if (temp.next.no == SinglyNode.no) {
temp.next.data = SinglyNode.data;
break;
}
// 遍历到最后一个还是找不到相同编号的结点，则修改失败
if (temp.next == null) {
System.out.println("找不到编号为" + SinglyNode.no + "结点，修改失败！");
break;
}
temp = temp.next;
}
}
}
/**
* 根据编号删除对应结点
*
* @param no
*/
public void delete(int no) {
SinglyNode temp = head;
while (true) {
if (temp.next == null) {
System.out.println("找不到编号为" + no + "结点，删除失败！");
break;
}
if (temp.next.no == no) {
temp.next = temp.next.next;
break;
}
temp = temp.next;
}
}
/**
* 遍历显示链表
*/
public void show() {
SinglyNode temp = head;
if (temp.next == null) {
System.out.println("空链表，有什么好显示的。");
return;
}
while (true) {
if (temp == null) {
break;
}
System.out.println(temp);
temp = temp.next;
}
}
/**
* 获取链表结点个数
*
* @return
*/
public int size() {
int size = 0;
SinglyNode temp = head.next;
while (temp != null) {
size++;
temp = temp.next;
}
return size;
}
/**
* 链表反转
*/
public void reverse() {
SinglyNode reverseHead = new SinglyNode(0, ""); // 反转后的头结点
SinglyNode cur = head.next; // 当前结点
SinglyNode next = null; // 当前结点的后结点
while (cur != null) {
next = cur.next;
cur.next = reverseHead.next;
reverseHead.next = cur;
cur = next;
}
head.next = reverseHead.next;
}
/**
* 查找倒数第 index 个结点
* 思路：找倒数第 index 个，即找第 size-index 个
*
* @param index
* @return
*/
public SinglyNode findLastIndexNode(int index) {
int size = this.size();
// 有效值判断
if (index < 0 || index > size) {
return null;
}
SinglyNode temp = head.next;
for (int i = 0; i < (size - index); i++) {
temp = temp.next;
}
return temp;
}
}
2.3 测试类
package cn.klb.test.datastructurestest;
import cn.klb.datastructures.linkedlist.SinglyLinkedList;
import cn.klb.datastructures.linkedlist.SinglyNode;
import org.junit.Test;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description:
* @Date: Create in 2023/3/31 12:49
* @Modified By:
*/
public class SinglyLinkedListTest {
/**
* 测试增删改
*/
@Test
public void singlyLinkedListTest() {
System.out.println("------list1------");
SinglyLinkedList list1 = new SinglyLinkedList();
list1.add(new SinglyNode(4, "周杰伦"));
list1.add(new SinglyNode(7, "林俊杰"));
list1.add(new SinglyNode(17, "张杰"));
list1.show();
System.out.println("------list2------");
SinglyLinkedList list2 = new SinglyLinkedList();
list2.add(new SinglyNode(4, "周杰伦"));
list2.add(new SinglyNode(17, "张杰"));
list2.add(new SinglyNode(7, "林俊杰"));
list2.show();
System.out.println("------list1 delete no:3 17------");
list1.delete(3);
list1.delete(17);
list1.show();
System.out.println("------list2 update {no=4,data=青花瓷}------");
SinglyNode SinglyNode4 = new SinglyNode(4, "青花瓷");
list2.update(SinglyNode4);
list2.show();
}
@Test
public void testSize() {
SinglyLinkedList list = new SinglyLinkedList();
list.add(new SinglyNode(4, "周杰伦"));
list.add(new SinglyNode(7, "林俊杰"));
list.add(new SinglyNode(17, "张杰"));
System.out.println("节点个数为：" + list.size());
}
@Test
public void testReverse() {
SinglyLinkedList list = new SinglyLinkedList();
list.add(new SinglyNode(4, "周杰伦"));
list.add(new SinglyNode(7, "林俊杰"));
list.add(new SinglyNode(17, "张杰"));
list.show();
System.out.println("-----链表反转------");
list.reverse();
list.show();
}
@Test
public void testfindLastIndexNode() {
SinglyLinkedList list = new SinglyLinkedList();
list.add(new SinglyNode(4, "周杰伦"));
list.add(new SinglyNode(7, "林俊杰"));
list.add(new SinglyNode(12, "张杰"));
list.add(new SinglyNode(1, "石鸣鸣"));
list.add(new SinglyNode(24, "周星驰"));
list.show();
System.out.println("倒数第2个元素为：" + list.findLastIndexNode(2));
}
}
3、双向链表
双向链表指的是每个结点都指向前和后，有两个方向。
3.1 双向链表的结点类
package cn.klb.datastructures.linkedlist;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description:
* @Date: Create in 2023/3/31 17:32
* @Modified By:
*/
public class DoubleLinkedNode {
public int no;
public String data;
public DoubleLinkedNode pre;
public DoubleLinkedNode next;
public DoubleLinkedNode(int no,String data){
this.no = no;
this.data = data;
}
@Override
public String toString() {
return "DoubleLinkedNode{" +
"no=" + no +
", data='" + data + '\'' +
'}';
}
}
3.2 双向链表类
package cn.klb.datastructures.linkedlist;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description:
* @Date: Create in 2023/3/31 17:32
* @Modified By:
*/
public class DoubleLinkedList {
private DoubleLinkedNode head = new DoubleLinkedNode(0, ""); // 定义头结点
/**
* 显示双向链表
*/
public void show() {
if (head.next == null) {
System.out.println("链表为空！");
}
// temp结点用于遍历
DoubleLinkedNode temp = head.next;
while (true) {
if (temp == null) break;
System.out.println(temp);
temp = temp.next;
}
}
/**
* 添加结点到尾端
*
* @param node
*/
public void add(DoubleLinkedNode node) {
DoubleLinkedNode temp = head;
// 找到最后一个结点
while (true) {
if (temp.next == null) break;
temp = temp.next;
}
temp.next = node;
node.pre = temp;
}
/**
* 根据结点编号来更新结点数据
*
* @param node
*/
public void update(DoubleLinkedNode node) {
// 如果链表没有结点，则直接返回
if (head.next == null) return;
// 定义临时节点来遍历找到和node相同no的结点
DoubleLinkedNode temp = head.next;
while (true) {
if (temp.no == node.no) {
temp.data = node.data; // 更新data
break; //更新完即退出循环
}
if (temp == null) {
System.out.println("要更新的结点不存在！");
break;// 找不到相同no，直接退出
}
temp = temp.next;
}
}
/**
* 删除指定no的结点
*
* @param no
*/
public void delete(int no) {
DoubleLinkedNode temp = head.next;
if (temp == null) {
System.out.println("链表为空，删除失败！");
}
while (true) {
if (temp == null) {
System.out.println("找不到要删除的结点，删除失败！");
}
if (temp.no == no){
temp.pre.next = temp.next;
// 要删除的结点不是最后一个结点
if(temp.next != null){
temp.next.pre = temp.pre;
}
break; //删除完就结束循环
}
temp = temp.next;
}
}
}
3.3 测试类
package cn.klb.test.datastructurestest;
import cn.klb.DataStructures.LinkedList.DoubleLinkedList;
import cn.klb.DataStructures.LinkedList.DoubleLinkedNode;
import org.junit.Test;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description:
* @Date: Create in 2023/3/31 17:34
* @Modified By:
*/
public class DoubleLinkedListTest {
@Test
public void testAdd(){
DoubleLinkedList list = new DoubleLinkedList();
list.add(new DoubleLinkedNode(1,"石鸣鸣"));
list.add(new DoubleLinkedNode(2,"周杰伦"));
list.add(new DoubleLinkedNode(3,"蔡依林"));
list.add(new DoubleLinkedNode(4,"蔡徐坤"));
list.show();
}
@Test
public void testUpdate(){
DoubleLinkedList list = new DoubleLinkedList();
list.add(new DoubleLinkedNode(1,"石鸣鸣"));
list.add(new DoubleLinkedNode(2,"周杰伦"));
list.add(new DoubleLinkedNode(3,"蔡依林"));
list.add(new DoubleLinkedNode(4,"蔡徐坤"));
System.out.println("-----修改前-----");
list.show();
DoubleLinkedNode node = new DoubleLinkedNode(1,"大帅哥");
System.out.println("-----修改后-----");
list.update(node);
list.show();
}
@Test
public void testDelete(){
DoubleLinkedList list = new DoubleLinkedList();
list.add(new DoubleLinkedNode(1,"石鸣鸣"));
list.add(new DoubleLinkedNode(2,"周杰伦"));
list.add(new DoubleLinkedNode(3,"蔡依林"));
list.add(new DoubleLinkedNode(4,"蔡徐坤"));
System.out.println("-----修改前-----");
list.show();
list.delete(2);
System.out.println("-----修改后-----");
list.show();
}
}