单链表

介绍

链表是有序的列表，但是它在内存中是存储如下(物理结构)

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

逻辑结构

思路

实现单链表的增删改查
1.不需要构造器,用一个成员变量head指向第一个节点(一般不为空)
2.添加:从头开始遍历,找到最后一个元素,然后把元素挂在最后一个元素的next
3.顺序添加:从头开始遍历,找到值大于元素值的上一个节点,然后挂在这个节点和他next的中间
4.修改:遍历找到节点,然后赋值
5.删除:找到需要删除节点的前一个节点,然后node.next=node.next.next

代码实现

package com.sgg.datastructure.linklist;
public class SingleLinkList {
    public HeroNode head = new HeroNode(0, "", "");
    public void add(HeroNode heroNode) {
        HeroNode tmp = head;
        while (true) {
            if (tmp.next == null) {
                tmp.next = heroNode;
                break;
            }
            tmp = tmp.next;
        }
    }
    //按照编号no的顺序添加到指定位置
    //编号相同则提示
    public void addByOrder(HeroNode node) {
        boolean flag = false;
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == node.no) {
                flag = true;
                break;
            } else if (temp.next.no > node.no) {
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.printf("英雄编号%d已经重复了,不允许重复添加\n", node.no);
        } else {
            node.next = temp.next;
            temp.next = node;
        }
    }
    //修改
    public void update(HeroNode heroNode) {
        boolean flag = false;
        if (head.next == null) {
            System.out.println("链表为空,无法操作");
            return;
        }
        HeroNode temp = head;
        while (true) {
            temp = temp.next;
            if (temp.no == heroNode.no) {
                flag = true;
                break;
            }
            if (temp.next == null) {
                break;
            }
        }
        if (flag) {
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        }else {
            System.out.printf("链表里面没有编号为%d的英雄\n",heroNode.no);
        }
    }
    //删除:找到相等的那个节点的上一个节点,把他的next=next.next
    public void delete(int no) {
        boolean flag = false;
        if (head.next == null) {
            System.out.println("链表为空,无法操作");
            return;
        }
        HeroNode temp = head;
        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 show() {
        if (head.next == null) {
            System.out.println("链表无数据");
            return;
        }
        HeroNode tmp = head.next;
        do {
            System.out.println(tmp);
            tmp = tmp.next;
        } while (tmp != null);
    }
    public static void main(String[] args) {
        SingleLinkList singleLinkList = new SingleLinkList();
        singleLinkList.addByOrder(new HeroNode(1, "宋江", "及时雨"));
        singleLinkList.addByOrder(new HeroNode(3, "吴勇", "智多星"));
        singleLinkList.addByOrder(new HeroNode(4, "aa", "dddd"));
        singleLinkList.addByOrder(new HeroNode(2, "曹盖", "牛逼"));
        singleLinkList.show();
        System.out.println();
        HeroNode update=new HeroNode(1, "宋江11", "及时雨11");
        singleLinkList.update(update);
        singleLinkList.show();
        System.out.println();
        singleLinkList.delete(3);
        singleLinkList.delete(1);
        singleLinkList.delete(9);
        singleLinkList.show();
    }
}

作业

比较简单直接写代码,放在上面的那个类里面

    /**
     * 得到链表的长度
     */
    public int getSize() {
        if (head.next == null) {
            return 0;
        }
        HeroNode temp = head.next;
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }
    /**
     * 找到倒数第k个节点
     */
    public HeroNode findLastK(int k) {
        int size = getSize();
        if (k > size) {
            throw new RuntimeException("倒数的个数超过总容量,报错");
        }
        int index = size - k + 1;
        HeroNode temp = head;
        while (index > 0) {
            temp = temp.next;
            index--;
        }
        return temp;
    }

反转链表
思路:
1.新定义头结点new
2.遍历链表,取出,放在new的最前端
3.head.next=new
代码实现

    /**
     * 反转 自己写的
     */
    public void reverse() {
        //除了头结点以外没有节点或只有1个节点,就不用反转
        if (head.next == null || head.next.next == null) {
            return;
        }
        HeroNode reverseNode = new HeroNode();
        HeroNode temp = head.next;
        while (temp != null) {
            HeroNode heroNode = new HeroNode(temp.no, temp.name, temp.nickname);
            heroNode.next = reverseNode.next;
            reverseNode.next = heroNode;
            temp = temp.next;
        }
        head.next = reverseNode.next;
    }
    /**
     * 老师的思路
     */
    public void reverseTeacher() {
        //除了头结点以外没有节点或只有1个节点,就不用反转
        if (head.next == null || head.next.next == null) {
            return;
        }
        HeroNode reverseNode = new HeroNode();
        HeroNode temp = head.next;
        HeroNode next = null;//保留下一个节点,要不然去操作temp.next后就丢了
        while (temp != null) {
            next = temp.next;
            temp.next = reverseNode.next;
            reverseNode.next = temp;
            temp = next;
        }
        head.next = reverseNode.next;
    }

有点意思,老师写的比较巧妙,把丢的东西先放在兜里,似乎可以节约一些空间
逆序打印

    /**
     * 逆序打印单链表
     * 思路:不破坏原先的链表
     * 利用栈的后进先出的特性
     */
    public void reversePrint(){
        Stack<HeroNode> stack = new Stack<>();
        HeroNode temp = head.next;
        while (temp != null) {
            stack.add(temp);
            temp = temp.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

合并2个有序的链表，合并完也要有序的
暂时还不会做

双向链表

介绍

在单链表基础上增加个，其他不变

public HeroNode prev;//相比单项链表，需要额外维护这个

单链表查找是单向的，这个可以是双向的
删除的时候不用辅助节点，自己就行了

思路

增加：多维护一个关系
修改不变
遍历展示不变
删除：改2个维护关系，后面的那个可能是空就不维护

代码实现

package com.sgg.datastructure.doubleLinkedLis;
public class DoubleLinkList {
    public HeroNode head = new HeroNode(0, "", "");
    /**
     * 默认加到最后
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        HeroNode tmp = head;
        while (true) {
            if (tmp.next == null) {
                tmp.next = heroNode;
                heroNode.prev = tmp;//多维护个
                break;
            }
            tmp = tmp.next;
        }
    }
    //作业
    //按照编号no的顺序添加到指定位置
    //编号相同则提示
    public void addByOrder(HeroNode node) {
        boolean flag = false;
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == node.no) {
                flag = true;
                break;
            } else if (temp.next.no > node.no) {
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.printf("英雄编号%d已经重复了,不允许重复添加\n", node.no);
        } else {
            if (temp.next != null) {
                temp.next.prev = node;
            }
            node.next = temp.next;
            temp.next = node;
            node.prev = temp;
        }
    }
    //修改，不变
    public void update(HeroNode heroNode) {
        boolean flag = false;
        if (head.next == null) {
            System.out.println("链表为空,无法操作");
            return;
        }
        HeroNode temp = head;
        while (true) {
            temp = temp.next;
            if (temp.no == heroNode.no) {
                flag = true;
                break;
            }
            if (temp.next == null) {
                break;
            }
        }
        if (flag) {
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        } else {
            System.out.printf("链表里面没有编号为%d的英雄\n", heroNode.no);
        }
    }
    //删除:找到相等的那个节点的 他的上个节点指向他的下个节点，如果有下个节点，那么下个节点指向上个节点
    public void delete(int no) {
        boolean flag = false;
        if (head.next == null) {
            System.out.println("链表为空,无法操作");
            return;
        }
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.prev.next = temp.next;
            if (temp.next != null) {
                temp.next.prev = temp.prev;
            }
        } else {
            System.out.printf("链表里面没有编号为%d的英雄\n", no);
        }
    }
    //不变
    public void show() {
        if (head.next == null) {
            System.out.println("链表无数据");
            return;
        }
        HeroNode tmp = head.next;
        do {
            System.out.println(tmp);
            tmp = tmp.next;
        } while (tmp != null);
    }
    public int getSize() {
        if (head.next == null) {
            return 0;
        }
        HeroNode temp = head.next;
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }
    public static void main(String[] args) {
        DoubleLinkList list = new DoubleLinkList();
//        list.add(new HeroNode(1, "宋江", "及时雨"));
//        list.add(new HeroNode(2, "22", "及时雨"));
//        list.add(new HeroNode(3, "吴勇", "智多星"));
//        list.add(new HeroNode(4, "aa", "dddd"));
//        list.show();
//        list.update(new HeroNode(4, "aa4", "dddd4"));
//        System.out.println();
//        list.show();
//        list.delete(4);
//        System.out.println();
//        list.show();
        list.addByOrder(new HeroNode(2, "22", "及时雨"));
        list.addByOrder(new HeroNode(1, "宋江", "及时雨"));
        list.addByOrder(new HeroNode(4, "aa", "dddd"));
        list.addByOrder(new HeroNode(9, "吴勇9", "智多星"));
        list.addByOrder(new HeroNode(8, "吴勇8", "智多星"));
        list.addByOrder(new HeroNode(6, "吴勇6", "智多星"));
        list.show();
    }
}

作业

顺序添加，有点难。要维护4个指针关系

环形链表

介绍

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

思路

构建(批量添加)

临时指针指向最后一个
第一次：首节点next指向自己，临时指针指向first
>=2次：临时指针next=新节点,新节点next=首节点,临时执政指向新的

遍历

遍历,直到next是首节点

出圈(形成队列)

/*
描述:n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列
出圈的思路
1.创建个辅助指针,指向队列的最后一个位置(已经有了1个指向第一个位置的)
2.辅助指针和头指针先向前移动k-1个位置
3.辅助指针和头指针向前移动m-1个位置
4.出列的做法:头指针移动下一个位置,辅助指针指向新头指针位置
5.最终尾指针和头指针指向同一个位置,结束
*/

代码实现

package com.sgg.datastructure.circleLinkedList;
public class CircleLinkedList {
    private Boy first = new Boy(0);
    public CircleLinkedList() {
    }
    public void add(int num) {
        if (num < 2) {
            System.out.println("数量必须大于等于2");
            return;
        }
        Boy temp = null;
        for (int i = 1; i <= num; i++) {
            if (i == 1) {
                first = new Boy(1);
                temp = first;
                first.setNext(first);
            } else {
                Boy boy = new Boy(i);
                temp.setNext(boy);
                boy.setNext(first);
                temp = boy;
            }
        }
    }
    /**
     * 不断遍历,如果指针下一个是头结点,打印下就退出
     */
    public void show() {
        Boy temp = first;
        while (true) {
            System.out.println(temp.getNo());
            if (temp.getNext() == first) {
                break;
            }
            temp = temp.getNext();
        }
    }
    public int size() {
        int size = 1;
        Boy temp = first;
        while (temp.getNext() != first) {
            size++;
            temp = temp.getNext();
        }
        return size;
    }
    /**
     * 描述:n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列
     * 出圈的思路
     * 1.创建个辅助指针,指向队列的最后一个位置(已经有了1个指向第一个位置的)
     * 2.辅助指针和头指针先向前移动k-1个位置
     * 3.辅助指针和头指针向前移动m-1个位置
     * 4.出列的做法:头指针移动下一个位置,辅助指针指向新头指针位置
     * 5.最终尾指针和头指针指向同一个位置,结束
     */
    public int finalPerson(int k, int m) {
        if (k > size()) {
            throw new RuntimeException("k必须小于小朋友的总数");
        }
        if (m < 1) {
            throw new RuntimeException("m必须大于2");
        }
        Boy temp = first;
        while (true) {
            if (temp.getNext() == first) {
                break;
            }
            temp = temp.getNext();
        }
        //5
        while (temp != first) {
            //2
            for (int i = 0; i < k - 1; i++) {
                first = first.getNext();
                temp = temp.getNext();
            }
            //3
            for (int i = 0; i < m - 1; i++) {
                first = first.getNext();
                temp = temp.getNext();
            }
            System.out.printf("小朋友%d出列\n", first.getNo());
            //4
            first = first.getNext();
            temp.setNext(first);
        }
        System.out.println("final winner:"+first.getNo());
        return first.getNo();
    }
    public static void main(String[] args) {
        CircleLinkedList circleLinkedList = new CircleLinkedList();
        int n = 5;
        int k =1;
        int m = 2;
        circleLinkedList.add(n);
        circleLinkedList.show();
        System.out.println("size:" + circleLinkedList.size());
        int result1 = circleLinkedList.finalPerson(k, m);
    }
}

java

四.链表

单链表

介绍

思路

代码实现

作业

双向链表

介绍

思路

代码实现

作业

环形链表

介绍

思路

构建(批量添加)

遍历

出圈(形成队列)

代码实现

结果