链表

链表

链表是有序的列表，在内存中存储格式如下图所示：

内存地址	data	next
100	b	400
200
300	a	100
400	c	700
500	e	null
600
700	d	500

其中头指针指向内存地址 400。根据内存地址则可以还原链表 head -> a -> b -> c -> d -> e

链表的特点

• 链表是以节点的方式来存储的，是链式存储
• 每个节点包含 data数据域，next域（指向下一个节点地址）
• 链表的各个节点不一定是连续存储的
• 链表分带头节点的链表和不带头节点的链表

单链表

使用带head头节点的单链表实现用户的增删改查操作

单链表的增

在单链表中添加新的节点有两种方法，一种是直接添加到链表的尾部，一种是根据用户的id进行有序的插入添加。

直接添加的思路

• 首先创建一个head头节点，其作用是表示单链表的头
• 每次新增一个节点时，直接加入到链表的最后
• 定义一个辅助变量，其作用是遍历整个链表，定位到链表的最后一个节点

有序添加的思路

• 定义一个辅助变量，通过辅助变量来遍历链表找到新节点添加的位置，通过节点的id来判断。
• 找到新节点添加的位置后，此时辅助变量 temp 节点就是新节点 newNode 的位置
• 所以 newNode.next = temp.next
• temp.next = newNode

单链表的删除

• 通过辅助节点首先找到需要删除节点的前一个节点 temp
• 此时将前一个节点的next域指向删除节点的后一个节点即可，即 temp.next = temp.next.next
• 被删除的节点没有其他节点的指向，因此在链表中被删除了，同时会被垃圾回收机制回收

单链表的改和查

通过遍历链表来查询链表中的数据，通过指定的条件可以查询到指定的节点并对其进行修改。具体操作看如下代码

链表中节点的创建

// 定义单链表节点
public class HeroNode {
    private int no;
    private String name;
    private String nickname;
    private HeroNode next;

    public HeroNode(int no, String name, String nickname, HeroNode heroNode) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
        this.next = heroNode;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }

    // getter、setter 方法
}

单链表具体功能的实现

/**
 * 管理节点
 */
public class SingleLinkedList {

    // 初始化头节点，不存放具体数据
    private HeroNode head = new HeroNode(0,"","",null);

    public HeroNode getHead() {
        return head;
    }

    public void setHead(HeroNode head) {
        this.head = head;
    }

    /**
     * 添加节点到单链表（不考虑编号顺序）
     *      1、找到当前链表的最后节点
     *      2、将最后节点的next指向新节点
     * @param heroNode
     */
    public void add(HeroNode heroNode){
        HeroNode temp = head;   // 辅助节点 temp，用于遍历链表找到最后一个节点
        while (true){
            // 找打链表的最后，退出
            if (temp.getNext() == null){
                break;
            }
            // 没有找到最后，temp后移
            temp = temp.getNext();
        }
        // 退出while循环后，temp就指向了链表最后
        temp.setNext(heroNode);
    }

    /**
     * 添加节点到单链表（考虑编号顺序）
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;   // 辅助节点 temp，用于遍历链表找到最后一个节点
        boolean flag = false;   // 标志添加的节点是否已存在
        while (true){
            // 找打链表的最后，退出
            if (temp.getNext() == null){
                break;
            }
            // 位置找到，就在temp的后面插入
            if (temp.getNext().getNo() > heroNode.getNo()){
                break;
            }
            // 添加的节点已存在
            if (temp.getNext().getNo() == heroNode.getNo()){
                flag = true;
                break;
            }
            // 没有找到最后，temp后移
            temp = temp.getNext();
        }
        if (flag){
            System.out.println("添加的节点已存在，不能加入，新添加的节点编号为：" + heroNode.getNo());
        }else{
            heroNode.setNext(temp.getNext());
            temp.setNext(heroNode);
        }
    }

    // 遍历链表
    public void show(){
        // 判断链表是否为空
        if (head.getNext() == null){
            System.out.println("链表为空");
        }
        // 辅助变量来遍历链表
        HeroNode temp = head.getNext();
        while (true){
            // 判断是否到链表最后
            if (temp == null){
                break;
            }
            System.out.println(temp);
            // 将temp节点后移
            temp = temp.getNext();
        }
    }

    // 修改节点
    public void update(HeroNode newNode){
        HeroNode temp = head.getNext();
        // 判断链表是否为空
        if (temp == null){
            System.out.println("链表为空，没有可修改的节点");
            return;
        }
        boolean flag = false;
        while (true){
            // 遍历完列表
            if (temp == null){
                break;
            }
            if (temp.getNo() == newNode.getNo()){
                flag = true;
                break;
            }
            temp = temp.getNext();
        }
        if (flag){
            temp.setName(newNode.getName());
            temp.setNickname(newNode.getNickname());
        }else {
            System.out.println("没有找到节点");
        }
    }

    // 删除节点
    public void deleteNode(HeroNode heroNode){
        if (head.getNext() == null){
            System.out.println("链表为空，没有可删除节点！！！");
        }
        HeroNode temp = head;
        while (true){
            // 遍历结束
            if (temp.getNext() == null){
                break;
            }
            if (temp.getNext().getNo() == heroNode.getNo()){
                temp.setNext(temp.getNext().getNext());
                break;
            }
            temp = temp.getNext();
        }
    }

    // 统计节点个数(有头节点的不算)
    public int getLength(HeroNode head){
        if (head.getNext() == null){
            System.out.println("链表为空");
        }
        HeroNode temp = head;
        int length =0;
        while (temp.getNext() != null){
            length++;
            temp = temp.getNext();
        }
        return length;
    }

    // 查找单链表中的倒数第k个节点
    public HeroNode getDesc(HeroNode head, int node){
        if (head.getNext() == null){
            System.out.println("链表为空");
        }
        int size = getLength(head);
        if (node < 1 || node > size){
            System.out.println("输入节点数错误");
            return null;
        }
        HeroNode temp = head.getNext();
        // 查找倒数第k个节点
        for (int i = 0; i < size - node; i++){
            temp = temp.getNext();
        }
        return temp;
    }

    // 将单链表反转
    public static void reverseList(HeroNode head){
        // 当前链表为空或者只有一个节点，无需反转
        if (head.getNext() == null || head.getNext().getNext() == null){
            return;
        }
        // 定义一个辅助的指针，帮助遍历原来的链表
        HeroNode current = head.getNext();
        // 指向当前节点的下一个节点
        HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0,"","",null);
        // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        while (current != null){
            next = current.getNext();
            current.setNext(reverseHead.getNext());// 将current节点添加到反转链表中的第一个节点，将反转链表中的节点数据接入插入的第一个节点之后
            reverseHead.setNext(current);
            current = next;
        }
        // 头节点转换
        head.setNext(reverseHead.getNext());
    }

    // 逆序打印单链表：利用栈的先进后出的特点，实现逆序打印
    public static void reversePrint(HeroNode head){
        if (head.getNext() == null || head.getNext().getNext() == null){
            return;
        }
        // 创建栈，将链表数据压入栈
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode temp = head.getNext();
        while (temp != null){
            stack.push(temp);
            temp = temp.getNext();
        }
        // 打印栈中数据
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }

    // 合并两个有序单链表，合并之后依然有序
}

测试单链表功能

public class TestSingleLink {
    public static void main(String[] args) {
        // 定义节点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨", null);
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟", null);
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星", null);
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头", null);

        // 创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        // 链表中加入节点
        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode3);
        singleLinkedList.addByOrder(heroNode2);

        // 查看链表
        singleLinkedList.show();

        // 修改链表中节点的数据
        System.out.println("-------修改节点数据-------");
        HeroNode heroNode5 = new HeroNode(4, "11林冲", "11豹子头", null);
        singleLinkedList.update(heroNode5);
        singleLinkedList.show();

        // 删除链表中的节点
        System.out.println("-------删除节点数据-------");
        singleLinkedList.deleteNode(heroNode1);
        singleLinkedList.deleteNode(heroNode4);
        singleLinkedList.show();
    }
}

查找链表中的倒数第 k 个节点

实现思路：

• 遍历链表，得到链表的总长度 linkLength
• 之后再次遍历链表，找到第 (linkLength - k) 个节点，即是倒数第 k 个节点
• 找到了返回该节点，否则返回null

// 查找单链表中的倒数第k个节点
public HeroNode getDesc(HeroNode head, int node){
    if (head.getNext() == null){
        System.out.println("链表为空");
    }
    int size = getLength(head);
    if (node < 1 || node > size){
        System.out.println("输入节点数错误");
        return null;
    }
    HeroNode temp = head.getNext();
    // 查找倒数第k个节点
    for (int i = 0; i < size - node; i++){
        temp = temp.getNext();
    }
    return temp;
}

单链表的反转

实现思路：

• 首先定义一个辅助头节点 tempHeadNode
• 从头开始遍历链表，每遍历一个节点，就将其取出加入到 tempHeadNode 节点之后，新加入的节点的next指向tempHeadNode的next。
• 遍历原先的链表完成后，修改头节点的指向：head.next == tempHeadNode.next

// 将单链表反转
public static void reverseList(HeroNode head){
    // 当前链表为空或者只有一个节点，无需反转
    if (head.getNext() == null || head.getNext().getNext() == null){
        return;
    }
    // 定义一个辅助的指针，帮助遍历原来的链表
    HeroNode current = head.getNext();
    // 指向当前节点的下一个节点
    HeroNode next = null;
    HeroNode reverseHead = new HeroNode(0,"","",null);
    // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
    while (current != null){
        next = current.getNext();
        current.setNext(reverseHead.getNext());// 将current节点添加到反转链表中的第一个节点，将反转链表中的节点数据接入插入的第一个节点之后
        reverseHead.setNext(current);
        current = next;
    }
    // 头节点转换
    head.setNext(reverseHead.getNext());
}

逆序打印单链表

实现思路：

• 第一种，先将单链表进行反转，在遍历打印即可，但是会破坏原先链表的结构，不建议
• 第二种，利用栈这个数据结构，将各个节点压入栈中，利用栈的先进后出的特点，实现逆序打印链表

// 逆序打印单链表：利用栈的先进后出的特点，实现逆序打印
public static void reversePrint(HeroNode head){
    if (head.getNext() == null || head.getNext().getNext() == null){
        return;
    }
    // 创建栈，将链表数据压入栈
    Stack<HeroNode> stack = new Stack<HeroNode>();
    HeroNode temp = head.getNext();
    while (temp != null){
        stack.push(temp);
        temp = temp.getNext();
    }
    // 打印栈中数据
    while (stack.size() > 0){
        System.out.println(stack.pop());
    }
}

双向链表

带head头的双向链表，即在一个节点上定义next域指向下一个节点，定义pre域指向上一个节点

单链表与双向链表的对比：
单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
单向链表不能实现自我删除，需要辅助节点，而双向链表，则可以实现自我删除。在单链表进行删除时，需要找到一个辅助节点temp，temp指向删除节点的前一个节点

双向链表的遍历和修改

遍历和修改的思路和单链表是类似的，只是双向链表的遍历可以向前也可以向后遍历

双向链表的添加

首先找到双向链表的最后一个节点，将新加入节点的pre指向最后一个节点，最后一个节点的next指向新加入的节点。
如果是有序插入，步骤和单链表是类似的，需要注意新加入节点的next域和pre域。

双向链表的删除

双向链表的删除可以不用借助辅助节点即可完成节点的删除。

• 首先找到需要删除的节点 deleteNode
• deleteNode.pre.next = deleteNode.next
• deleteNode.next.pre = deleteNode.pre

代码实现

public class DoubleLinkedListDemo {

    public static void main(String[] args) {
        // 定义节点
        HeroNodes heroNode1 = new HeroNodes(1, "宋江", "及时雨");
        HeroNodes heroNode2 = new HeroNodes(2, "卢俊义", "玉麒麟");
        HeroNodes heroNode3 = new HeroNodes(8, "吴用", "智多星");
        HeroNodes heroNode4 = new HeroNodes(6, "林冲", "豹子头");
        // 创建双向链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(heroNode1);
        doubleLinkedList.add(heroNode2);
        doubleLinkedList.add(heroNode3);
        doubleLinkedList.add(heroNode4);
        doubleLinkedList.list();

        // 顺序添加节点
        System.out.println("-------顺序添加节点-------");
        HeroNodes heroNode5 = new HeroNodes(5, "公孙胜", "入云龙");
        doubleLinkedList.addByOrder(heroNode5);
        doubleLinkedList.list();

       System.out.println("-------修改节点数据-------");
       HeroNodes heroNode5 = new HeroNodes(4, "风雪林冲", "豹子头+-+");
       doubleLinkedList.update(heroNode5);
       doubleLinkedList.list();

       System.out.println("-------删除节点数据-------");
       doubleLinkedList.del(4);
       doubleLinkedList.list();
    }
}

// 创建双向链表的类
class DoubleLinkedList{
    // 初始化头节点
    private HeroNodes head = new HeroNodes(0,"", "");

    // 返回头节点
    public HeroNodes getHead(){
        return head;
    }

    // 遍历双向链表的方法
    public void list(){
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        HeroNodes temp = head.next;
        while (temp != null){
            System.out.println(temp);
            temp = temp.next;
        }
    }

    // 双向链表最后添加节点
    public void add(HeroNodes heroNode){
        HeroNodes temp = head;
        while (temp.next != null){
            temp = temp.next;
        }
        temp.next = heroNode;
        heroNode.per = temp;
    }

    // 顺序添加节点
    public void addByOrder(HeroNodes heroNode){
        HeroNodes temp = head;
        // 链表为空时
        if (temp.next == null){
            temp.next = heroNode;
            heroNode.per = temp;
        }
        // 链表不为空
        while (true){
            // 插入
            if (temp.next != null){
                if (temp.next.no > heroNode.no){
                    heroNode.next = temp.next;
                    temp.next.per = heroNode;
                    temp.next = heroNode;
                    heroNode.per = temp;
                    break;
                }
                temp = temp.next;
            }else {
                // 循环到最后一个节点
                temp.next = heroNode;
                heroNode.per = temp;
                break;
            }
        }
    }

    // 修改双向链表的节点
    public void update(HeroNodes heroNode){
        if (head.next == null){
            System.out.println("双向链表为空");
        }
        HeroNodes temp = head.next;
        boolean flag = true;
        while (temp != null){
            if (temp.no == heroNode.no){
                temp.name = heroNode.name;
                temp.nickname = heroNode.nickname;
                flag = false;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("没有找到可修改的节点");
        }
    }

    // 删除节点
    public void del(int no){
        if (head.next == null){
            System.out.println("双向链表为空");
        }
        HeroNodes temp = head.next;
        boolean flag = false;
        while (true){
            if (temp == null){
                break;
            }
            if (temp.no == no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 删除
        if (flag){
            temp.per.next = temp.next;
            if (temp.next != null){
                temp.next.per = temp.per;
            }
        }else {
            System.out.println("删除的节点不存在");
        }
    }
}

// 定义双向链表的节点
class HeroNodes{
    public int no;
    public String name;
    public String nickname;
    public HeroNodes next;  // 指向下一个节点
    public HeroNodes per;   // 指向上一个节点

    public HeroNodes(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNodes{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

Josephu（约瑟夫、约瑟夫环）问题

Josephu问题描述：设编号为1、2、3、….、n的n个人围坐一圈，约定编号为k（1 <= k <= n）的人从 1 开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列

思路

用一个不带头节点的循环链表来处理Josephu问题，首先构成一个有n个节点的单循环链表，然后由k节点起从1开始计数，计到m时，对应节点从链表中删除，然后再从被删除节点的下一个节点又从1开始计数，直到最后一个节点从链表中删除，算法结束。

构建单向的环形链表思路

• 创建第一个节点firstNode，让第一个节点fistNode的next指向自己，形成一个环形
• 当创建一个新的节点newNode时，将新节点加入到该环形链表中，firstNode.next = newNode, newNode.next = firstNode
• 每创建一个新的节点，就加入到上一个节点之后，新节点的next域指向第一个节点firstNode

遍历单向环形链表思路

• 创建一个辅助变量temp，指向firstNode节点
• 通过while循环遍历该环形链表
• while循环结束的条件是：temp.next = firstNode

Josephu问题思路

• 定义一个报数指针first，first指向链表的第一个节点；定义一个辅助指针helper，helper指向环形链表的最后节点
• 在开始报数前，首先让两个指针移动 k-1次
• 开始报数后，让first和helper同时移动m-1次
• 此时将first指向的节点读取并删除，即将first节点指向待删节点的下一个节点，同时helper指向待删节点的上一个节点

实现代码

package com.java.linkedlist;

public class JosephusProblem {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        // 添加节点
        circleSingleLinkedList.addBoy(5);
        // 遍历节点
        circleSingleLinkedList.list();

        // 出圈
        circleSingleLinkedList.countBoy(1, 2, 5);
    }
}

// 创建环形单向链表
class CircleSingleLinkedList{

    // 创建first节点
    private Boy first = null;

    // 添加节点，构建成一个环形的链表
    public void addBoy(int nums){
        if (nums < 1){
            System.out.println("添加节点的数值不对");
        }
        Boy curBoy = null;  // 辅助指针，帮助构建环形链表
        // 使用for创建环形链表
        for (int i = 1; i <= nums; i++){
            // 根据编号创建节点
            Boy boy = new Boy(i);
            if (i == 1){
                first = boy;
                first.setNext(first);
                curBoy = first;
            } else {
                 curBoy.setNext(boy);
                 boy.setNext(first);
                 curBoy = boy;
            }
        }
    }

    // 遍历环形链表
    public void list(){
        if (first == null){
            System.out.println("链表为空");
            return;
        }
        // first不能动，使用辅助指针完成遍历
        Boy curBoy = first;
        while (true){
            System.out.println("节点：" + curBoy.getNo());
            if (curBoy.getNext() == first){
                // 遍历完毕
                break;
            }
            curBoy = curBoy.getNext();
        }
    }

    /**
     * 根据输入，计算出出圈的顺序
     * @param startNo   表示从第几个节点开始数数
     * @param countNum  表示数几下
     * @param nums      表示最初有多少节点在圈中参与
     */
    public void countBoy(int startNo, int countNum, int nums){
        if (first == null || startNo < 1 || startNo > nums){
            System.out.println("参数有误");
            return;
        }
        // 创建辅助指针，指向最后一个节点
        Boy helper = first;
        while (true){
            if (helper.getNext() == first){
                break;
            }
            helper = helper.getNext();
        }

        // 出圈前，让节点到第k个节点位置
        for (int i = 0; i < startNo - 1; i++){
            first = first.getNext();
            helper = helper.getNext();
        }

        // 出圈
        while (true){
            if (helper == first){
                // 最后一个节点
                System.out.println("出圈节点：" + first.getNo());
                break;
            }
            // 让节点移动至下一次报数的位置
            for (int i = 0; i < countNum - 1; i++){
                first = first.getNext();
                helper = helper.getNext();
            }
            // 报数节点出圈
            System.out.println("出圈节点：" + first.getNo());
            first = first.getNext();
            helper.setNext(first);
        }
    }
}


// 创建boy类，表示节点
class Boy{
    private int no;
    private Boy next;

    public Boy(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}

可以构造双向循环链表实现此算法