【数据结构】链表

一、单链表

1、单链表概述

1. 链表是以节点的方式来存储,是链式存储
2. 每个节点包含data域， next 域：指向下一个节点.
3. 链表的各个节点不一定是连续存储
4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确

2、面试题

1）有效节点个数

/**
 * 有效节点个数（遍历+计数）
 */
public int usedNode() {
   
    int ans = 0;
    heroNode temp = head;
    while (temp.next != null) {
   
        ans++;
        temp = temp.next;
    }
    return ans;
}

2）倒数第K个节点数据

/**
 * 反向输出第k个节点
 */
public void oppoShow(int k) {
   
    int all = usedNode();
    heroNode temp = head.next;
    if (all < k) {
   
        System.out.printf("没有第%d个节点\n", k);
        return;
    }
    int i = 1;
    while (temp != null) {
   
        if (i == (all - k + 1)) {
   
            System.out.println(temp.toString());
            break;
        }
        temp = temp.next;
        i++;
    }
}

3）反向遍历——迭代

/**
 * 反向遍历
 */
public void oppoShow() {
   
    if (head.next == null) {
   
        System.out.println("链表为空");
        return;
    }
    int all = usedNode();
    for (int i = all; i >= 0; i--) {
   
        int j = 1;
        heroNode temp = head.next;
        while (temp != null) {
   
            if (j == i) {
   
                System.out.println(temp.toString());
                break;
            }
            j++;
            temp = temp.next;
        }
    }
}

4）反向遍历——栈

class nodeStact {
   
    int maxSize;
    heroNode[] hn;
    int top;

    /**
     * 栈的构造器
     * 
     * @param maxSize 栈的大小
     */
    nodeStact(int maxSize) {
   
        this.maxSize = maxSize;
        hn = new heroNode[maxSize];
        top = -1;
    }

    /**
     * 判空
     */
    public boolean isEmpty() {
   
        return top == -1;
    }

    /**
     * 判满
     */
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    /**
     * 弹出
     */
    public heroNode pop() {
   
        if (isEmpty()) {
   
            System.out.println("栈空");
            return null;
        }
        return hn[top--];
    }

    /**
     * 压栈
     */
    public void push(heroNode _hn) {
   
        if (isFull()) {
   
            System.out.println("栈满");
        } else {
   
            hn[++top] = _hn;
        }
    }
}

/**
 * 反向遍历——通过栈实现
 */
public void showByStack() {
   
    if(head.next == null) {
   
        System.out.println("链表为空");
        return;
    }
    nodeStact ns = new nodeStact(usedNode());
    heroNode temp = head.next;
    while(temp != null) {
   
        ns.push(temp);
        temp = temp.next;
    }
    while(!ns.isEmpty()) {
   
        System.out.println(ns.pop().toString());
    }
}

5）合并单链表

/**
 * 与demo合并
 */
public void mesh() {
   
    singleLinkedList demo = new singleLinkedList();
    demo.add(new heroNode(-1, "小明", "王哥"));
    demo.add(new heroNode(0, "芭芭拉", "芭芭拉冲鸭"));
    heroNode temp = demo.head.next;
    while(temp != null) {
   
        addByNo(new heroNode(temp.getNo(), temp.getName(), temp.getNickName()));
        temp = temp.next;
    }

}

3、代码实现

package work.rexhao.linkedlist;

import java.util.Scanner;

public class singleLinkedListDemo {
   

    public static void main(String[] args) {
   
        singleLinkedList sll = new singleLinkedList();
        boolean loop = true;
        while (loop) {
   
            System.out.println("--------");
            System.out.println("1.在尾部添加");
            System.out.println("2.按编号添加");
            System.out.println("3.遍历单链表");
            System.out.println("4.修改节点");
            System.out.println("5.删除节点");
            System.out.println("6.有效节点个数");
            System.out.println("7.反向输出");
            System.out.println("8.反向遍历");
            System.out.println("0.退出");
            System.out.println("--------");
            Scanner sc = new Scanner(System.in);
            int key = sc.nextInt();
            if (key == 1) {
   
                System.out.println("请输入英雄编号：");
                int no = sc.nextInt();
                System.out.println("请输入英雄姓名：");
                Scanner sc1 = new Scanner(System.in);
                String name = sc1.nextLine();
                System.out.println("请输入英雄昵称：");
                Scanner sc2 = new Scanner(System.in);
                String nickName = sc2.nextLine();
                sll.add(new heroNode(no, name, nickName));
                System.out.println("添加成功！");
            } else if (key == 2) {
   
                System.out.println("请输入英雄编号：");
                int no = sc.nextInt();
                System.out.println("请输入英雄姓名：");
                Scanner sc1 = new Scanner(System.in);
                String name = sc1.nextLine();
                System.out.println("请输入英雄昵称：");
                Scanner sc2 = new Scanner(System.in);
                String nickName = sc2.nextLine();
                sll.addByNo(new heroNode(no, name, nickName));
                System.out.println("添加成功！");
            } else if (key == 3) {
   
                try {
   
                    sll.show();
                } catch (Exception e) {
   
                    System.out.println(e.getMessage());
                }
            } else if (key == 4) {
   
                System.out.println("请输入英雄编号：");
                int no = sc.nextInt();
                System.out.println("请输入英雄新的姓名：");
                Scanner sc1 = new Scanner(System.in);
                String name = sc1.nextLine();
                System.out.println("请输入英雄新的昵称：");
                Scanner sc2 = new Scanner(System.in);
                String nickName = sc2.nextLine();
                sll.change(no, name, nickName);
            } else if (key == 5) {
   
                System.out.println("请输入英雄编号：");
                int no = sc.nextInt();
                sll.delete(no);
            } else if (key == 6) {
   
                System.out.println("有效节点个数：" + sll.usedNode());
            } else if (key == 7) {
   
                int k = sc.nextInt();
                sll.oppoShow(k);
            } else if (key == 8) {
   
                System.out.println("通过反向遍历实现：");
                sll.oppoShow();
                System.out.println("通过栈实现：");
                sll.showByStack();
            } else if (key == 9) {
   
                System.out.println("与demo链表合并");
                sll.mesh();
            } else if (key == 0) {
   
                loop = false;
            } else {
   
                System.out.println("输入有误！");
            }
        }
    }
}

/**
 * 管理英雄
 */
class singleLinkedList {
   
    /**
     * 定义一个头结点
     */
    private heroNode head = new heroNode(0, "", "");

    /**
     * 添加节点的方法(尾插法) 将最后的next域指向新的node
     */
    public void add(heroNode hn) {
   
        // 需要一个辅助变量
        heroNode temp = head;
        // 遍历单链表
        while (temp.next != null) {
   
            temp = temp.next;
        }
        // 退出循环时，temp指向最后
        temp.next = hn;
    }

    /**
     * 按照编号大小添加
     * 
     * @param hn
     */
    public void addByNo(heroNode hn) {
   
        /**
         * 空链表：直接放后面
         */
        if (head.next == null) {
   
            head.next = hn;
            return;
        }
        heroNode temp = head.next;
        /**
         * 如果只有一个节点，且大于hn
         */
        if (hn.getNo() < temp.getNo()) {
   
            head.next = hn;
            hn.next = temp;
            return;
        }
        while (true) {
   
            /**
             * 如果no相等：报错
             */

            if (hn.getNo() == temp.getNo()) {
   
                throw new RuntimeException("编号重复！");
            }
            if (temp.next != null) {
   
                if (hn.getNo() == temp.next.getNo()) {
   
                    throw new RuntimeException("编号重复！");
                }
            }

            /**
             * 找到：大于前一个节点且（小于后一个节点或者后一个节点为null）的节点
             */
            if (hn.getNo() > temp.getNo() && (temp.next == null || hn.getNo() < temp.next.getNo())) {
   
                hn.next = temp.next;
                temp.next = hn;
                break;
            }
            if (temp.next != null) {
   
                temp = temp.next;
            } else {
   
                break;
            }
        }
    }

    /**
     * 遍历
     */
    public void show() {
   
        // 判空
        if (head.next == null) {
   
            throw new RuntimeException("链表为空");
        }
        // 遍历
        heroNode temp = head.next;
        while (temp != null) {
   
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }

    /**
     * 修改节点
     */
    public void change(int no, String name, String nickName) {
   
        // 判空
        if (head.next == null) {
   
            System.out.println("链表为空");
            return;
        }
        // 遍历：找no节点
        heroNode temp = head.next;
        while (temp != null) {
   
            if (temp.getNo() == no) {
   
                temp.setName(name);
                temp.setNickName(nickName);
                System.out.println("修改成功！");
                return;
            }
            temp = temp.next;
        }
        System.out.printf("未找到编号为%d的节点\n", no);
        return;
    }

    /**
     * 删除节点
     */
    public void delete(int no) {
   
        // 判空
        if (head.next == null) {
   
            System.out.println("链表为空");
            return;
        }
        // 遍历找节点
        heroNode temp = head;
        while (temp.next != null) {
   
            if (temp.next.getNo() == no) {
   
                temp.next = temp.next.next;
                System.out.println("删除成功");
                return;
            }
            temp = temp.next;
        }
        System.out.printf("未找到编号为%d的节点\n", no);
        return;
    }

    /**
     * 有效节点个数（遍历+计数）
     */
    public int usedNode() {
   
        int ans = 0;
        heroNode temp = head;
        while (temp.next != null) {
   
            ans++;
            temp = temp.next;
        }
        return ans;
    }

    /**
     * 反向输出第k个节点
     */
    public void oppoShow(int k) {
   
        int all = usedNode();
        heroNode temp = head.next;
        if (all < k) {
   
            System.out.printf("没有第%d个节点\n", k);
            return;
        }
        int i = 1;
        while (temp != null) {
   
            if (i == (all - k + 1)) {
   
                System.out.println(temp.toString());
                break;
            }
            temp = temp.next;
            i++;
        }
        return;
    }

    /**
     * 反向遍历——翻转单链表
     */
    public void oppoShow() {
   
        if (head.next == null) {
   
            System.out.println("链表为空");
            return;
        }
        int all = usedNode();
        for (int i = all; i >= 0; i--) {
   
            int j = 1;
            heroNode temp = head.next;
            while (temp != null) {
   
                if (j == i) {
   
                    System.out.println(temp.toString());
                    break;
                }
                j++;
                temp = temp.next;
            }
        }
    }

    /**
     * 反向遍历——通过栈实现
     */
    public void showByStack() {
   
        if (head.next == null) {
   
            System.out.println("链表为空");
            return;
        }
        nodeStact ns = new nodeStact(usedNode());
        heroNode temp = head.next;
        while (temp != null) {
   
            ns.push(temp);
            temp = temp.next;
        }
        while (!ns.isEmpty()) {
   
            System.out.println(ns.pop().toString());
        }
    }

    /**
     * 与demo合并
     */
    public void mesh() {
   
        singleLinkedList demo = new singleLinkedList();
        demo.add(new heroNode(-1, "小明", "王哥"));
        demo.add(new heroNode(0, "芭芭拉", "芭芭拉冲鸭"));
        heroNode temp = demo.head.next;
        while(temp != null) {
   
            addByNo(new heroNode(temp.getNo(), temp.getName(), temp.getNickName()));
            temp = temp.next;
        }

    }
}

/**
 * 定义heroNode节点
 */
class heroNode {
   
    private int no;
    private String name;
    private String nickName;
    public heroNode next;

    /**
     * 构造器
     * 
     * @param no       编号
     * @param name     姓名
     * @param nickName 昵称
     */
    heroNode(int no, String name, String nickName) {
   
        this.name = name;
        this.no = no;
        this.nickName = nickName;
    }

    /**
     * 重写toString
     */
    @Override
    public String toString() {
   
        return "[no=" + no + ", name=" + name + ", nickName=" + nickName + ", next=" + next + "]";
    }

    public int getNo() {
   
        return no;
    }

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

    public String getName() {
   
        return name;
    }

    public void setName(String name) {
   
        this.name = name;
    }

    public String getNickName() {
   
        return nickName;
    }

    public void setNickName(String nickName) {
   
        this.nickName = nickName;
    }

}

class nodeStact {
   
    int maxSize;
    heroNode[] hn;
    int top;

    /**
     * 栈的构造器
     * 
     * @param maxSize 栈的大小
     */
    nodeStact(int maxSize) {
   
        this.maxSize = maxSize;
        hn = new heroNode[maxSize];
        top = -1;
    }

    /**
     * 判空
     */
    public boolean isEmpty() {
   
        return top == -1;
    }

    /**
     * 判满
     */
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    /**
     * 弹出
     */
    public heroNode pop() {
   
        if (isEmpty()) {
   
            System.out.println("栈空");
            return null;
        }
        return hn[top--];
    }

    /**
     * 压栈
     */
    public void push(heroNode _hn) {
   
        if (isFull()) {
   
            System.out.println("栈满");
        } else {
   
            hn[++top] = _hn;
        }
    }
}

二、双向链表

1、双向链表概述

1. 遍历方法和单链表一样，不仅可以向前，也可以向后查找
2. 添加（默认添加到双向链表的最后)
   1. 先找到双向链表的最后这个节点
   2. temp.next = newHeroNode
   3. newHeroNode.pre=temp;
3. 修改：思路和原来的单向链表一样
4. 删除
   1. 双向链表可以实现自我删除某个节点
   2. 直接找到要州除的这个节点，比如 temp
   3. temp.pre.next =temp.next
   4. temp.next. pre = temp.pre;

2、代码实现

package work.rexhao.linkedlist;

import java.util.Scanner;

public class doubleLinkedListDemo {
   

    public static void main(String[] args) {
   
        doubleLinkedList dll = new doubleLinkedList();
        boolean loop = true;
        while (loop) {
   
            System.out.println("--------");
            System.out.println("1.在尾部添加");
            System.out.println("2.按编号添加");
            System.out.println("3.遍历双向链表");
            System.out.println("4.修改节点");
            System.out.println("5.删除节点");
            System.out.println("6.有效节点个数");
            System.out.println("0.退出");
            System.out.println("--------");
            Scanner sc = new Scanner(System.in);
            int key = sc.nextInt();
            if (key == 1) {
   
                System.out.println("请输入学生编号：");
                int no = sc.nextInt();
                System.out.println("请输入学生姓名：");
                Scanner sc1 = new Scanner(System.in);
                String name = sc1.nextLine();
                dll.add(new stuNode(no, name));
                System.out.println("添加成功！");
            } else if (key == 2) {
   
                System.out.println("请输入学生编号：");
                int no = sc.nextInt();
                System.out.println("请输入学生姓名：");
                Scanner sc1 = new Scanner(System.in);
                String name = sc1.nextLine();
                dll.addByNo(new stuNode(no, name));
                System.out.println("添加成功！");
            } else if (key == 3) {
   
                dll.show();
            } else if (key == 4) {
   
                System.out.println("请输入学生编号：");
                int no = sc.nextInt();
                System.out.println("请输入学生新的姓名：");
                Scanner sc1 = new Scanner(System.in);
                String name = sc1.nextLine();
                dll.change(new stuNode(no, name));
            } else if (key == 5) {
   
                System.out.println("请输入学生编号：");
                int no = sc.nextInt();
                dll.delete(no);
            } else if (key == 6) {
   
                System.out.println("有效节点个数：" + dll.usedNode());
            } else if (key == 0) {
   
                loop = false;
            } else {
   
                System.out.println("输入有误！");
            }
        }
    }

}

/**
 * 双向链表
 */
class doubleLinkedList {
   
    private stuNode head = new stuNode(0, "wmh");

    /**
     * 有效节点数
     */
    public int usedNode() {
   
        int ans = 0;
        stuNode temp = head.next;
        while (temp != null) {
   
            ans++;
            temp = temp.next;
        }
        return ans;
    }

    /**
     * 插入
     */
    public void add(stuNode sn) {
   
        if (head.next == null) {
   
            head.next = sn;
            sn.pre = head;
            return;
        }
        stuNode temp = head.next;
        while (true) {
   
            if (temp.next == null) {
   
                break;
            }
            temp = temp.next;
        }
        temp.next = sn;
        sn.pre = temp;

    }

    /**
     * 遍历
     */
    public void show() {
   
        if (head.next == null) {
   
            System.out.println("单链表为空");
            return;
        }
        stuNode temp = head.next;
        while (temp != null) {
   
            System.out.println(temp);
            temp = temp.next;
        }
    }

    /**
     * 修改
     */
    public void change(stuNode sn) {
   
        if (head.next == null) {
   
            System.out.println("单链表为空");
            return;
        }
        stuNode temp = head.next;
        while (temp != null) {
   
            if (temp.getNo() == sn.getNo()) {
   
                temp.setName(sn.getName());
                temp.setNo(sn.getNo());
                return;
            }
            temp = temp.next;
        }
        System.out.printf("未找到no=%d的节点\n", sn.getNo());
    }

    /**
     * 自我删除
     */
    public void delete(int no) {
   
        if (head.next == null) {
   
            System.out.println("链表为空");
            return;
        }
        stuNode temp = head.next;
        while (temp != null) {
   
            if (temp.getNo() == no) {
   
                /*
                 * 找到了
                 */
                temp.pre.next = temp.next;
                if (temp.next != null) {
   
                    temp.next.pre = temp.pre;
                }
                return;
            }
            temp = temp.next;
        }
        System.out.printf("未找到no=%d的节点\n", no);
    }

    /**
     * 按照编号添加
     */
    public void addByNo(stuNode sn) {
   
        /*
         * 判空
         */
        if (head.next == null) {
   
            head.next = sn;
            sn.pre = head;
            return;
        }
        /*
         * 判同
         */
        stuNode temp = head.next;
        while (temp != null) {
   
            if (temp.getNo() == sn.getNo()) {
   
                System.out.println("编号相同");
                return;
            }
            temp = temp.next;
        }
        /*
         * 找位置添加——第一个位置
         */
        if (sn.getNo() < head.next.getNo()) {
   
            sn.next = head.next;
            head.next = sn;
            sn.pre = head;
            sn.next.pre = sn;
            return;
        }
        /*
         * 找位置添加——不是第一个位置
         */
        temp = head.next;
        while (temp != null) {
   
            if (temp.next == null) {
   
                temp.next = sn;
                sn.pre = temp;
                return;
            }
            if (temp.getNo() < sn.getNo() && temp.next.getNo() > sn.getNo()) {
   
                sn.next = temp.next;
                temp.next = sn;
                sn.pre = head;
                sn.next.pre = sn;
                return;
            }
            temp = temp.next;
        }
    }
}

/**
 * 定义stuNode节点
 */
class stuNode {
   
    private int no;
    private String name;
    public stuNode next;
    public stuNode pre;

    /**
     * 构造器
     * 
     * @param no   编号
     * @param name 姓名
     */
    stuNode(int no, String name) {
   
        this.name = name;
        this.no = no;
    }

    public int getNo() {
   
        return no;
    }

    /**
     * 重写toString
     */
    @Override
    public String toString() {
   
        return "[no=" + no + ", name=" + name + "]";
        // 使用双向链表，不能打印next和pre
    }

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

    public String getName() {
   
        return name;
    }

    public void setName(String name) {
   
        this.name = name;
    }
}

三、单项循环链表与Josepfu问题

1、约瑟夫环概述

设编号为1,2,⋯n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

2、解决思想

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

3、代码实现

package work.rexhao.linkedlist;

import java.util.Scanner;

public class JosepfuDemo {
   

    public static void main(String[] args) {
   
        Scanner sc = new Scanner(System.in);
        System.out.print("总人数:");
        int n = sc.nextInt();
        System.out.print("报号数:");
        int k = sc.nextInt();
        Josepfu(n, k);
    }

    /**
     * Josepfu问题
     * 
     * @param n 人数
     * @param k 报号数
     */
    public static void Josepfu(int n, int k) {
   
        circleSingleLinkedList csll = new circleSingleLinkedList();
        for(int i = 1; i <= n; i++) {
   
            csll.add(new Node(i));
        }
        Node temp = csll.head;
        int j = 1;
        while(csll.usedNode() != 1) {
   
            if(j == k) {
   
                csll.delete(temp.getNum());
                j = 1;
                temp = temp.next;
                continue;
            }
            j++;
            temp = temp.next;
        }
        csll.show();
    }
}

class circleSingleLinkedList {
   
    public Node head = null;

    /**
     * 添加节点
     */
    public void add(Node n) {
   
        /*
         * 空链表，直接放后面
         */
        if (head == null) {
   
            head = n;
            n.next = head;
            return;
        }
        /*
         * 非空，遍历加在后面
         */
        Node temp = head;
        while (temp.next != head) {
   
            temp = temp.next;
        }
        temp.next = n;
        n.next = head;

    }

    /**
     * 遍历
     */
    public void show() {
   
        Node temp = head;
        boolean loop = true;
        while (loop) {
   
            System.out.println(temp);
            temp = temp.next;
            if (temp == head) {
   
                loop = false;
            }
        }
    }

    /**
     * 有效元素
     */
    public int usedNode() {
   
        if (head == null) {
   
            return 0;
        }
        if (head.next == head) {
   
            return 1;
        }
        Node temp = head;
        int ans = 1;
        while (temp.next != head) {
   
            temp = temp.next;
            ans++;
        }
        return ans;
    }

    /**
     * 删除节点
     */
    public void delete(int num) {
   
        /*
         * 判空
         */
        if (head == null) {
   
            System.out.println("链表为空");
            return;
        }
        /*
         * 删除head节点
         */
        if (head.getNum() == num) {
   
            if (head.next == head) {
   
                /*
                 * 只有一个head
                 */
                head = null;
            } else {
   
                /*
                 * 还有其他节点
                 */
                // 1.改最后的next
                Node temp = head;
                while (true) {
   
                    if (temp.next == head) {
   
                        temp.next = head.next;
                        break;
                    }
                    temp = temp.next;
                }
                // 2.改head
                head = head.next;
            }
            return;
        }
        /*
         * 删除其他的节点
         */

        Node temp = head.next;
        while (true) {
   
            if (temp.next.getNum() == num) {
   
                temp.next = temp.next.next;
                return;
            }
            temp = temp.next;
        }
    }
}

class Node {
   
    private int num;
    public Node next;

    Node(int num, Node next) {
   
        this.num = num;
        this.next = next;
    }

    Node(int num) {
   
        this.num = num;
        this.next = null;
    }

    @Override
    public String toString() {
   
        return "Node[num=" + num + "]";
    }

    public int getNum() {
   
        return num;
    }

    public void setNum(int num) {
   
        this.num = num;
    }

}