2020-03-09

Data Structure LinkedList

Linked List is a sequence of links which contains items. Each link contains a connection to another link.

前言

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

单向链表

小结:

1)链表是以节点的方式来存储,是链式存储

2)每个节点包含 data 域， next 域：指向下一个节点.

3)如图：发现链表的各个节点不一定是连续存储.

4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

链表图解：

单向链表代码：

import java.util.Stack;

/**
 * @Auther: Arsenal
 * @Date: 2020-03-08 10:28
 * @Description: 链表
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(3, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(5, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(7, "公孙胜", "入云龙");

        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        HeroNode heroNode5 = new HeroNode(2, "唐僧", "唐三藏");
        HeroNode heroNode6 = new HeroNode(4, "孙悟空", "齐天大圣");
        HeroNode heroNode7 = new HeroNode(6, "猪八戒", "天蓬元帅");
        HeroNode heroNode8 = new HeroNode(8, "沙僧", "卷帘大将");

        // singleLinkedList.addHeroNode(heroNode3);
        // singleLinkedList.addHeroNode(heroNode2);
        // singleLinkedList.addHeroNode(heroNode4);
        // singleLinkedList.addHeroNode(heroNode1);
        // singleLinkedList.list();


        //合并两个有序的单链表，合并之后的链表依然有序【课后练习.】
        singleLinkedList.addHeroNodeByOrder(heroNode4);
        singleLinkedList.addHeroNodeByOrder(heroNode3);
        singleLinkedList.addHeroNodeByOrder(heroNode2);
        singleLinkedList.addHeroNodeByOrder(heroNode1);
        singleLinkedList.list();

        singleLinkedList1.addHeroNodeByOrder(heroNode8);
        singleLinkedList1.addHeroNodeByOrder(heroNode7);
        singleLinkedList1.addHeroNodeByOrder(heroNode6);
        singleLinkedList1.addHeroNodeByOrder(heroNode5);
        singleLinkedList1.list();
        System.out.println("================合并两个有序的单链表，合并之后的链表依然有序================");
        HeroNode mergeTwoLinkedList = SingleLinkedList.mergeTwoLinkedList(singleLinkedList.getHead(), singleLinkedList1.getHead());
        singleLinkedList1.list(mergeTwoLinkedList);

        //从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
        // System.out.println("================从尾到头打印单链表================");
        // SingleLinkedList.printReverseLinkedList(singleLinkedList.getHead());

        //单链表的反转【腾讯面试题，有点难度】
        // System.out.println("================反转链表================");
        // SingleLinkedList.reverseLinkedList(singleLinkedList.getHead());
        // singleLinkedList.list();


        // singleLinkedList.addHeroNodeByOrder(heroNode4);
        // singleLinkedList.addHeroNodeByOrder(heroNode3);
        // singleLinkedList.addHeroNodeByOrder(heroNode2);
        // singleLinkedList.addHeroNodeByOrder(heroNode1);
        // singleLinkedList.list();
        //
        // System.out.println("================修改后链表信息================");
        // HeroNode newHeroNode = new HeroNode(3, "老王", "隔壁老王");
        // singleLinkedList.updateHeroNode(newHeroNode);
        // singleLinkedList.list();
        //
        // System.out.println("================删除后链表信息================");
        // singleLinkedList.delHeroNode(1);
        // singleLinkedList.delHeroNode(4);
        // singleLinkedList.list();
        //
        // System.out.println("================链表有效节点个数================");
        // System.out.println(SingleLinkedList.getLinkedLength(singleLinkedList.getHead()));
        //
        // //查找单链表中的倒数第k个结点 【新浪面试题】
        // System.out.println("================单链表中的倒数第k个结点================");
        // System.out.println("result=" + SingleLinkedList.getLastIndexHeroNode(singleLinkedList.getHead(), 0));

    }
}

/**
 * 单向链表
 */
class SingleLinkedList {

    private HeroNode head = new HeroNode(0, "", "");

    /**
     * 获得头节点
     * @return
     */
    public HeroNode getHead() {
        return head;
    }

    /**
     * 添加节点
     * @param heroNode 节点
     */
    public void addHeroNode(HeroNode heroNode) {
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    /**
     * 按顺序添加节点
     * @param heroNode 节点
     */
    public void addHeroNodeByOrder(HeroNode heroNode) {
        HeroNode temp = head;
        boolean flag = false; //是否找到该节点的标志
        while (true) {
            if (temp.next == null) {
                break;
            } else if (temp.next.no > heroNode.no) {
                break; //找到了要插入的节点
            } else if (temp.next.no == heroNode.no) {
                flag = true; //已有存在该编号节点，不能插入
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            System.out.printf("已有存在%d编号节点，不能插入\n", heroNode.no);
        } else {
            //插入节点
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    /**
     * 更新节点
     * @param newHeroNode 新节点
     */
    public void updateHeroNode(HeroNode newHeroNode) {
        HeroNode temp = head;
        boolean flag = false; //是否找到该节点的标志
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.no == newHeroNode.no) {
                flag = true; //找到了要修改的节点
                break;
            }
            temp = temp.next;
        }

        if (temp.next == null) {
            System.out.println("链表为空");
        }

        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        } else {
            System.out.printf("没有编号%d节点\n", newHeroNode.no);
        }
    }

    /**
     * 删除节点
     * @param no 要删除的节点编号
     */
    public void delHeroNode(int no) {
        HeroNode temp = head;
        boolean flag = false; //是否找到该节点的标志
        while (true) {
            if (temp.next == null) {
                break;
            }

            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的%d节点不存在\n", no);
        }
    }

    /**
     * 遍历展示节点信息
     */
    public void list() {

        HeroNode temp = head;
        if (temp.next == null) {
            System.out.println("链表为空");
            return;
        }

        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
            System.out.println(temp);
        }
    }

    public void list(HeroNode head) {
        HeroNode temp = head;
        if (temp.next == null) {
            System.out.println("链表为空");
            return;
        }

        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
            System.out.println(temp);
        }
    }

    /**
     * 单链表中有效节点的个数
     * @param head 头节点
     * @return 个数
     */
    public static int getLinkedLength(HeroNode head) {
        if (head.next == null) {
            return 0;
        }

        HeroNode cur = head.next;
        int length = 0;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        return length;
    }

    /**
     * 查找单链表中的倒数第k个结点 【新浪面试题】
     * @param head  头节点
     * @param index 倒数index个
     * @return 倒数第index个结点
     */
    public static HeroNode getLastIndexHeroNode(HeroNode head, int index) {
        if (head.next == null) {
            return null;
        }

        int size = getLinkedLength(head);

        if (index <= 0 || index > size) {
            return null;
        }

        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 单链表的反转【腾讯面试题，有点难度】
     * @param head 头节点
     */
    public static void reverseLinkedList(HeroNode head) {
        if (head.next == null || head.next.next == null) {
            return; //空链表和单个元素链表无需反转
        }
        HeroNode reverseHead = new HeroNode(0, "", "");
        HeroNode cur = head.next; //用来遍历链表
        HeroNode next = null; //临时保存cur指向的下一个节点
        while (cur != null) {
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }
        //实现head反转
        head.next = reverseHead.next;
    }

    /**
     * 从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
     * @param head 头节点
     */
    public static void printReverseLinkedList(HeroNode head) {
        if (head.next == null) {
            System.out.println("队列为空");
            return;
        }
        Stack<HeroNode> heroNodeStack = new Stack<>();
        //压栈
        HeroNode cur = head.next;
        while (cur != null) {
            heroNodeStack.push(cur);
            cur = cur.next;
        }

        //弹栈，打印
        cur = head.next;
        while (cur != null) {
            System.out.println(heroNodeStack.pop());
            cur = cur.next;
        }
    }

    /**
     * 合并两个有序的单链表，合并之后的链表依然有序【课后练习.】
     * @param head1 头节点1
     * @param head2 头节点2
     * @return 合并后链表头节点
     */
    public static HeroNode mergeTwoLinkedList(HeroNode head1, HeroNode head2) {
        if (head1.next == null) {
            return head2;
        }

        if (head2.next == null) {
            return head1;
        }

        HeroNode mergeHead = new HeroNode(0, "", "");

        HeroNode cur1 = head1.next;
        HeroNode cur2 = head2.next;
        HeroNode mergeCur = mergeHead;
        while (cur1 != null && cur2 != null) {
            if (cur1.no <= cur2.no) {
                mergeCur.next = cur1;
                mergeCur = mergeCur.next;
                cur1 = cur1.next;
            } else {
                mergeCur.next = cur2;
                mergeCur = mergeCur.next;
                cur2 = cur2.next;
            }
        }
        
        // 任一为空，直接连接另一条链表
        if (cur1 == null) {
            mergeCur.next = cur2;
        } else {
            mergeCur.next = cur1;
        }
        return mergeHead;
    }
}

/**
 * 节点
 */
class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

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

双向链表

简介：
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

代码：

/**
 * @Auther: Arsenal
 * @Date: 2020-03-09 21:08
 * @Description: 双向链表
 */
public class DoubleLinkedListDemo {

    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        Node node1 = new Node(1, "曹操", "曹孟德");
        Node node2 = new Node(2, "刘备", "刘玄德");
        Node node3 = new Node(3, "孙权", "孙仲谋");
        // doubleLinkedList.addNodeToTail(node1);
        // doubleLinkedList.addNodeToTail(node2);
        // doubleLinkedList.addNodeToTail(node3);
        //doubleLinkedList.list();

        // System.out.println("=================修改节点=================");
        // Node newNode = new Node(1, "老王", "隔壁老王");
        // doubleLinkedList.update(newNode);
        // doubleLinkedList.list();
        // System.out.println("=================删除节点=================");
        // doubleLinkedList.delNode(2);
        // doubleLinkedList.list();
        System.out.println("=================排序插入节点=================");
        doubleLinkedList.addNodeByOrder(node2);
        doubleLinkedList.addNodeByOrder(node3);
        doubleLinkedList.addNodeByOrder(node1);
        doubleLinkedList.list();

    }
}

/**
 * 双向链表
 */
class DoubleLinkedList {

    private Node head = new Node(0, "", "");

    public Node getHead() {
        return head;
    }

    /**
     * 按顺序添加节点
     * @param newNode 需添加的节点
     */
    public void addNodeByOrder(Node newNode) {

        if (head.next == null) {
            head.next = newNode;
            newNode.pre = head;
            return;
        }
        Node cur = head.next;
        while (cur != null) {
            if (head.next.no > newNode.no) {
                //比第一个还小的情况
                head.next.pre = newNode;
                newNode.next = head.next;

                head.next = newNode;
                newNode.pre = head;
                break;
            } else if (cur.no > newNode.no) {
                //中间情况
                cur.pre = newNode;
                newNode.next = cur;
                cur.pre.next = newNode;
                newNode.pre = cur.pre;
                break;
            } else if (cur.no == newNode.no) {
                System.out.println("已存在" + newNode.no + "节点,不能添加");
                break;
            } else if (cur.next == null) {
                //最末尾的情况
                cur.next = newNode;
                newNode.pre = cur;
                break;
            }
            cur = cur.next;
        }
    }

    /**
     * 修改节点
     * @param newNode 新的节点的值
     */
    public void update(Node newNode) {

        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        Node cur = head.next;
        boolean flag = false;
        while (cur != null) {
            if (cur.no == newNode.no) {
                flag = true;
                break;
            }
            cur = cur.next;
        }

        if (flag) {
            //找到要修改的节点
            cur.name = newNode.name;
            cur.nickName = newNode.nickName;
        } else {
            System.out.println("要修改的" + newNode.no + "节点不存在");
        }

    }

    /**
     * 删除节点
     * @param no 需删除节点的编号
     */
    public void delNode(int no) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Node cur = head.next;
        boolean flag = false;
        while (cur != null) {
            if (cur.no == no) {
                flag = true;
                break;
            }
            cur = cur.next;
        }

        if (flag) {
            //找到要删除的节点
            cur.pre.next = cur.next;
            if (cur.next != null) { //判断如果是最后一个元素，那该元素的next为空，需排除空指针的情况
                cur.next.pre = cur.pre;
            }
        } else {
            System.out.println("要删除的" + no + "节点不存在");
        }
    }

    /**
     * 在链表尾部添加节点
     * @param node
     */
    public void addNodeToTail(Node node) {
        Node cur = head;
        //找到最后一个节点
        while (true) {
            if (cur.next == null) {
                break;
            }
            cur = cur.next;
        }
        cur.next = node;
        node.pre = cur;
    }

    /**
     * 遍历链表
     */
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        Node cur = head.next;
        while (cur != null) {
            System.out.println(cur);
            cur = cur.next;
        }

    }
}

/**
 * 节点
 */
class Node {
    public int no; //编号
    public String name; //名字
    public String nickName; //昵称
    public Node pre; //前一个节点
    public Node next; //下一个节点

    public Node(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

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

单向循环链表

简介：
链式的存储结构，在逻辑上是连续的，每次通过一个指针来指向下一个节点将其链接起来。

构建一个单向的环形链表思路：

先创建第一个节点, 让 first 指向该节点，并形成环形；
后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可。

遍历环形链表：

先让一个辅助指针(变量) curBoy，指向first节点；
然后通过一个while循环遍历该环形链表即可 curBoy.next == first 结束。

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

n = 5 , 即有5个人
k = 1, 从第一个人开始报数
m = 2, 数2下

解决思路：

需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点.
补充：小孩报数前，先让 first 和 helper 移动 k - 1次
当小孩报数时，让first 和 helper 指针同时的移动 m - 1 次
这时就可以将first 指向的小孩节点出圈
first = first .next
helper.next = first
原来first 指向的节点就没有任何引用，就会被回收

出圈的顺序
2->4->1->5->3

代码：

/**
 * @Auther: Arsenal
 * @Date: 2020-03-10 23:56
 * @Description: 单向环形链表
 * Josephu  问题：
 * 设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，
 * 它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
 * <p>
 * n = 5 , 即有5个人
 * k = 1, 从第一个人开始报数
 * m = 2, 数2下
 * <p>
 * 出圈的顺序
 * 2->4->1->5->3
 */
public class Josephu {
    public static void main(String[] args) {
        SingleCircleLinkedList singleCircleLinkedList = new SingleCircleLinkedList(5);
        singleCircleLinkedList.showBoy();
        System.out.println("============出圈的顺序============");
        singleCircleLinkedList.boyOut(1, 2, 5);
    }
}

/**
 * 单向环形链表
 */
class SingleCircleLinkedList {
    Boy first = null;

    /**
     * 构造器初始化单向环形链表
     * @param number 节点数
     */
    public SingleCircleLinkedList(int number) {
        if (number < 1) {
            System.out.println("无法创建个数为" + number + "的环形链表");
            return;
        }
        Boy curBoy = null;
        for (int i = 1; i <= number; i++) {
            Boy boy = new Boy(i);
            //该节点为第一个节点时
            if (i == 1) {
                first = boy;
                first.setNext(first); // 构成环
                curBoy = first; // 让curBoy指向第一个小孩
            } else { //非第一个节点时
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }

    /**
     * 遍历单向循环链表
     */
    public void showBoy() {
        if (first == null) {
            System.out.println("空链表");
            return;
        }
        Boy cur = first;
        while (true) {
            System.out.println("小孩的编号:" + cur.getNo());
            if (cur.getNext() == first) { // 说明已经遍历完毕
                break;
            }
            cur = cur.getNext();
        }

    }

    /**
     * 小孩出圈
     * @param startNo  从第几个开始数
     * @param countNum 数几下
     * @param nums     初始人数
     */
    public void boyOut(int startNo, int countNum, int nums) {

        // 先对数据进行校验
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("参数输入有误， 请重新输入");
            return;
        }

        // 创建要给辅助指针,帮助完成小孩出圈
        Boy helper = first;
        // 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
        while (true) {
            if (helper.getNext() == first) { // 说明helper指向最后小孩节点
                break;
            }
            helper = helper.getNext();
        }
        //小孩报数前，先让 first 和  helper 移动 k - 1次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //当小孩报数时，让first 和 helper 指针同时 的移动  m  - 1 次, 然后出圈
        //这里是一个循环操作，知道圈中只有一个节点
        while (true) {
            if (first == helper) { //说明链表中只剩一个节点
                break;
            }
            //按数的次数移动
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //此时first即为要出圈的小孩，打印之
            System.out.println("编号为：" + first.getNo() + " 的小孩出圈");
            //小孩出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo());
    }
}

/**
 * 节点
 */
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;
    }
}

延伸

链表
 双向链表
 链表实战（带图分析）
数据结构–双向链表
 单向循环链表
 韩顺平数据结构和算法
 Linked List Data Structure
Data Structure and Algorithms - Linked List
经典算法–约瑟夫环问题的三种解法
 (单向、单向循环、双向、双向循环)链表学习总结

Article Title:Data Structure LinkedList

Article Author:Funing Ma

Release Time:2020-03-09 18:18:18

Last Update:2020-03-30 09:58:31

Original Link:https://mafuning.github.io/2020/03/09/2020-03-09-Data-Structure-LinkedList/

License Agreement: "CC-BY-SA-4.0"