一、链表概念介绍
链表（Linked List）和数组类似，是一种线性的数据结构，而线性结构又分为顺序存储结构和链式存储结构，因链表虽然逻辑上是连续的，但是在物理存储上是非连续、非顺序的，故又称之为链式存储结构。
链表是以节点来存储数据的，节点包含数据域、指向域；节点后面的节点称为后继节点，节点前面的节点称为前置节点。
- 有无头节点优缺点：
作用：头节点作用：头节点是为了对链表建立、删除、逆向的时候操作更统一，不用专门对第一个元素或最后一个元素进行单独处理。
优点：在于链表有头节点虽然浪费空间，但易理解，边界好处理，不易出错，代码简单；
缺点：相反无头节点，省空间，难理解，边界不易处理，代码稍复杂。
image.png
常用的链表种类有：单链表、双向链表、循环链表、双向循环链表
二 、单链表（single linked list）
单链表顾名思义，每个节点都是单向联系的，第一个节点链接第二个节点，第二个节点链接第三个节点.....，以此形成一个单链表。
单链表缺点：查找方向只能是从头节点开始。当删除某一个节点时需要靠辅助节点，不能自我删除。
链表实现思路：创建一个Node类作为链表中的节点，类中声明一个value变量（数据域），作用是存放数据；再将Node类声明为next成员变量（指针域），作用是存放下一个节点的引用。当Node节点实例化之后，每个节点将会散列在内存中，刚好可以利用Node类中的next变量来将一个个散列的节点连接起来。
单链表节点类：
package linkedlist;
public class HeroNode {
//数据域，存放数据
public String value;
// 指针域，指向下一个节点
public HeroNode next;
public HeroNode() {}
public HeroNode(String value) {
this.value = value;
}
@Override
public String toString() {
return "HeroNode{" +
"value='" + value +
'}';
}
}
【1】last节点新增
思路：循环遍历链表节点，找到尾部节点，将尾部节点的指向域指向新插入的节点。
//添加节点到单向链表
public void add(HeroNode heroNode) {
// 1.循环遍历链表，因为遍历链表是需要从头节点一个一个往后遍历的，
//所以需要一个临时变量用于存放下一次要遍历的节点。
HeroNode temp = headNode;
while (true) {
//2.因为尾部节点是最后一个节点，所以它的指向域将会是null，
//那么可以通过判断尾部节点的指向域是否为null，如果为null，则表示遍历结束。
if (temp.next == null) {
break;
}
// 3.每遍历一次将下一个节点的指向域赋给零时变量,循环遍历完成后，temp将会获得尾节点
temp = temp.next;
}
//4.尾部节点的指向域指向新插入的节点。
temp.next = heroNode;
}
【2】节点修改
思路：循环遍历链表节点，找到需要修改的节点，然后修改即可。
// 节点修改
public void update(String oldValue,String newValue){
//判断链表是否为空
if (headNode.next == null) {
System.out.println("链表为空！");
return;
}
HeroNode temp=headNode;
boolean flag=false;
while (true) {
//当到达最后一个元素或者找到需要修改的元素都终止遍历
if (temp.next == null) {
break;
}
// 判断当前遍历的节点是否是需要修改的节点
if (oldValue.equals( temp.value)){
flag=true;
break;
}
temp = temp.next;
}
if (flag) {
temp.value = newValue;
}else {
System.out.println("未找到需要修改的元素！");
}
}
【3】节点删除
image.png
思路：元素删除的思路和新增有点相似；从头节点开始遍历，判断后继节点是否为200节点，如果是200则将200节点的指向域取出来，赋给200节点的前置节点的指向域。
// 删除节点
public void remove(String value){
HeroNode temp = headNode;
boolean delFlag=false;
// 1. 遍历链表中所有节点
while (true) {
// 2. 如果下一个指向域为空，则表示链表遍历结束
if (temp.next == null) {
break;
}
// 3. 判断下一个节点是否是需要删除的节点
if (value.equals(temp.next.value)) {
delFlag=true;
break;
}
//4. 遍历一个之后，移动指针
temp = temp.next;
}
//5. 删除节点
if (delFlag) {
// 将被删除节点的下一个节点和被删除节点的上一个节点的指针域挂钩
temp.next=temp.next.next;
}else {
System.out.println("需要删除的元素未找到，删除失败！");
}
}
【4】节点遍历
//遍历链表
public void list() {
//判断链表是否为空
if (headNode.next == null) {
System.out.println("链表为空！");
return;
}
HeroNode temp = headNode;
// 遍历链表中所有节点
while (true) {
// 如果下一个指向域为空，则表示链表遍历结束
if (temp == null) {
break;
}
System.out.println(temp);
//遍历一个之后，移动指针
temp = temp.next;
}
}
【5】获取链表有效节点个数
// 获取链表有效节点个数
public int getLength(){
//判断链表是否为空
if (headNode.next == null) {
System.out.println("链表为空！");
return 0;
}
// 统计有效节点个数
int size=0;
// 头节点不是有效节点，所以从头节点的后继节点开始遍历
HeroNode temp = headNode.next;
// 遍历链表中所有节点
while (temp!=null) {
size++;
//遍历一个之后，移动指针
temp=temp.next;
}
return size;
}
【6】获取链表倒数第i个节点
查找倒数第i个元素的公式：length-index=i
// 获取链表倒数的第i个节点
public HeroNode findLastIndexNode(int index) {
//判断链表是否为空
if (headNode.next == null) {
return null;
}
// 获取链表长度
int length = getLength();
//如果小于0，或者大于链表的长度则不存在这个索引
if (index <= 0 || index > length) {
return null;
}
// 头节点不是有效节点，不遍历，headNode.next是跳过头节点
HeroNode temp = headNode.next;
// 从末尾取节点的公式：length-index=i
// 循环i次，当循环走完后，temp将会存放i节点的后继节点，最后return temp；
for (int i = 0; i < length-index; i++) {
temp=temp.next;
}
return temp;
}
【7】链表反转
链表反转过后链表的数据结构也将发生变化。
思路：
- 遍历需要反转的链表，用新的链表将需要反转的节点链接，
- 每次遍历时让新节点的指向域指向新链表头节点的指向域，新链表的头节点指向域每次循环都会变。第二次遍历的关系指向： 200(新节点)--》100(新链表头节点指向域)，
-
新链表的头节点指向新节点。第二次遍历结束关系的关系指向：头节点--》200--》100
image.png
// 使用头插法反转单链表
public void reversal() {
//如果链表为空，或者只有一个节点都不需要反转
if (headNode.next == null || headNode.next.next == null) {
return;
}
//1. 需要准备的变量：oldNode旧的链表、newNode新的链表、next一个临时节点变量
HeroNode oldNode = headNode.next;
HeroNode next = null;
HeroNode newNode = new HeroNode();
while (oldNode != null) {
//2. 循环遍历旧链表的节点，oldNode.next移动节点时不要直接覆盖，赋给next保存起来。
next = oldNode.next;
//3. 这时oldNode.next的指向域是空的，再把newNode.next链表的指向域赋给oldNode.next临时保存
//将newNode.next节点赋给oldNode.next的指向域，这样每次新插入的节点就和之前已经插入的节点衔接，
//然后就是第4步：将oldNode.next赋给newNode.next的指向域，反转完成
oldNode.next = newNode.next;
//4.这时newNode.next的指向域是空的，将当前节点赋给newNode.next
newNode.next = oldNode;
//temp往后移
oldNode = next;
}
// 修改headNode节点的指向域，将reversalHead节点的指向域付给headNode节点的指向域
headNode.next = newNode.next;
}
二 、双向链表
【1】双向链表介绍
双向链表与单向链表不同的是单向链表每个节点只能指向后继节点，而双向链表的节点不仅指向后继节点还指向前置节点，形成一个双向的关系。
双向链表共有三部分：一个数据域，一个pre指向域，一个next指向域。
image.png
【2】双向链表完整实现代码
大部分功能的实现思路和单向链表没有区别。
package linkedlist;
// 双向链表
public class DoubleLinkedList {
class Node {
public String value;
// 指向下一个节点
public Node next;
//指向上一个节点
public Node pre;
public Node() {
}
public Node(String value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value='" + value + '\'' +
'}';
}
}
//头节点
Node headNode = new Node();
//遍历链表
public void list() {
//判断链表是否为空
if (headNode.next == null) {
System.out.println("链表为空！");
return;
}
Node temp = headNode.next;
// 遍历链表中所有节点
while (temp != null) {
System.out.println(temp);
//遍历一个之后，移动指针
temp = temp.next;
}
}
// 节点修改
public void update(String oldValue, String newValue) {
System.out.println();
//判断链表是否为空
if (headNode.next == null) {
System.out.println("链表为空！");
return;
}
// 从头节点之后开始遍历
Node temp = headNode;
boolean flag = false;
//当到达最后一个元素或者找到需要修改的元素都终止遍历
while (temp != null) {
// 判断当前遍历的节点是否是需要修改的节点
if (oldValue.equals(temp.value)) {
flag = true;
break;
}
temp = temp.next;
}
// 修改属性
if (flag) {
temp.value = newValue;
} else {
System.out.println("未找到需要修改的元素！");
}
}
// 测试双向链表功能
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.add("一石二鸟");
doubleLinkedList.add("二话不说");
doubleLinkedList.add("七七八八");
doubleLinkedList.add("四舍五入");
doubleLinkedList.list();
doubleLinkedList.update("七七八八", "三心二意");
doubleLinkedList.list();
System.out.println();
doubleLinkedList.remove("四舍五入");
doubleLinkedList.list();
}
}
【3】新增节点思路
双向链表和单项链表的节点新增不同之处在于双向链表还多了一个pre指向域，所以当链表新增节点时，既旧节点的next域要指向新节点，新节点的pre域也要指向上一个节点。
// 链表节点新增
public void add(String str) {
Node newNode = new Node(str);
// 因为头节点不能动，所以需要一个临时变量
Node temp = headNode;
//遍历链表的每一个节点，当next等于null时表示链表已经遍历到了最后一个节点
while (temp.next != null) {
// 每遍历一次将下一个节点的指向域赋给零时变量,while变量完之后，temp将会获得尾节点
temp = temp.next;
}
// 每遍历一次将下一个节点的指向域赋给零时变量,while变量完之后，temp将会获得尾节点
temp.next = newNode;
// 将链表末尾节点赋给新节点的pre指向域
newNode.pre = temp;
}
【4】删除节点思路
单向链表删除节点时的做法：判断当前节点的下一个节点是否为需要删除的节点，如果是则改变当前节点的next指向域为被被删除节点的下一节点，单向链表只需要修改next指向域。
双向链表删除节点时的做法：判断当前节点是否为需要删除的节点，如果是那我们既要修改上一个节点的next指向域，还要修改下一个节点的pre指向域，因为当前节点链接了上一个节点和下一个节点，所以我们可以直接修改上一个节点next的指向域为被删除节点的next指向域；可以直接修改下一个节点的pre指向域为被删除节点的pre指向域。
// 删除节点
public void remove(String value) {
Node temp = headNode;
boolean delFlag = false;
// 遍历链表中所有节点
while (true) {
if (temp==null) {
break;
}
// 判断下一个节点是否是需要删除的节点
if (value.equals(temp.value)) {
delFlag = true;
break;
}
//遍历一个之后，移动指针
temp = temp.next;
}
if (delFlag) {
// 修改被删除节点的上一个节点的next指向域为当前节点的next域
temp.pre.next = temp.next;
// 避免空指针异常
if (temp.next != null) {
// 修改被删除节下一个节点的pre指向域为当前节点的pre域
temp.next.pre = temp.pre;
}
} else {
System.out.println("需要删除的元素未找到，删除失败！");
}
}
三、单向环形链表（Circular LinkedList）
【1】循环链表/环形链表
循环链表( Circular LinkedList)是另一种形式的链式存储结构其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
package linkedlist;
public class Josepfu {
public static void main(String[] args) {
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.add(5);
circleSingleLinkedList.show();
}
}
//创建一个环形单链表
class CircleSingleLinkedList {
//创建一个first节点，当前没有编号
private Node first = null;
//添加元素，形成一个环形链表
public void add(int nums) {
if (nums < 1) {
System.out.println("nums值不正确！");
return;
}
//辅助指针，帮助构建环形链表，临时保存每一次的最后一个节点
Node curNode = null;
// 循环创建节点
for (int i = 1; i <= nums; i++) {
// 每次循环创建一个node对象
Node node = new Node(i);
if (i == 1) {
// node是第一个节点，将第一个节点赋给first
first = node;
// 设置首节点的指向域，因为当前只有一个节点所以首节点的next域指向自己-----环形链表就此形成
first.setNext(first);
// 将first赋给curNode作为链表的最后一个元素临时保存，下一次新增则可以直接设置curNode的next指向域
curNode = first;
} else {
// 设置链表中最后一个节点的next指向域，指向新的节点
curNode.setNext(node);
//设置新节点的next指向域，指向首节点------环形链表形成
node.setNext(first);
// 刷新curNode保存的最后一个节点，下一次新增则可以直接设置curNode的next指向域
curNode = node;
}
}
}
//遍历元素
public void show() {
if (first == null) {
System.out.println("链表中没有元素，遍历失败！");
return;
}
Node curNode = first;
while (true) {
System.out.printf("小孩的编号%d\n", curNode.getNo());
// 环形链表判断链表遍历结束的条件有所不同，结束条件为：因为环形链表首尾相接，
// 所以我们需要判断遍历的下一个节点是不是首节点，如果是则表示遍历完成，否则继续遍历
if (curNode.getNext() == first) {
break;
}
// 获取下一个节点
curNode = curNode.getNext();
}
}
}
//单向链表
class Node {
private int no;
private Node next;
public Node(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
【2】约瑟夫问题
约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。
/*
* 根据用户的输入，计算出小孩（节点）出圈顺序
* startNo:表示从第几个节点开始数数
* count：表示数几下
* nums：表示最初环形链表中最开始有几个节点
*/
public void josephRing(int startNo, int count, int nums) {
//先对数据进行校验
if (first == null || startNo < 1 || startNo > nums) {
System.out.println("参数有误，请重新输入");
return;
}
//创建一个辅助指针helper（指向最后一个节点）
Node helper = first;
// 这个while循环为了获取尾部节点
while (true) {
if (helper.next == first) { //说明helper指向了最后一个节点
break;
}
helper = helper.next;
}
//报数之前，先让first和helper移动k-1次(不一定是从第一个人开始报数的，可能是从第k个人开始报数的)
for (int i = 0; i < startNo - 1; i++) {
first = first.next;
helper = helper.next;
}
//当小孩报数时，让first 和helper指针同时的移动count-1次
//进行循环，直到只剩下一个节点
while (true) {
if (helper == first) { //只剩最后一个节点
break;
}
//让first 和helper指针同时的移动count -1次
for (int i = 0; i < count - 1; i++) {
first = first.next;
helper = helper.next;
}
//此时first指向的节点即为出圈的节点
System.out.printf("小孩%d出圈 \n", first.no);
first = first.next;
helper.next = first;//一直循环
}
System.out.printf("显示最后在圈中的小孩编号%d\n", first.no);
}
