[数据结构与算法]数据结构和算法学习笔记之 03.单向双向链表和环形链表构建

5.单向链表

把一个节点Node当做是一个对象，改对象里面包含了数据和指向下一个节点的引用指针

5.1 链表的添加和遍历

5.1.1 思路分析

• 添加
  • 创建一个head头节点表示链表的头节点，里面的存放数据的data = null
  • 每添加一个元素就直接添加到链表的最后(尾插法)
• 遍历
  • 通过辅助变量来遍历整个链表节点

List、LinkedHashMap、LinkedHashSet、TreeMap、TreeSet是有序的，List、LinkedHashMap、LinkedHashSet、LinkedHashSet在遍历时会保持添加的顺序，TreeMap、TreeSet在遍历时会以自然顺序（Comparable接口的compareTo）输出

5.1.2 代码实现

package com.tomdd.model;

/**
 * <h1>英雄结点对象</h1>
 * 可以把该节点对象定义为单向链表的内部类
 *
 * @author zx
 * @date 2022年11月12日 10:07
 */
public class SingleHeroNode {
    /**
     * 英雄编号
     */
    public Integer no;

    /**
     * 英雄mc
     */
    public String name;

    /**
     * 昵称
     */
    public String nickName;

    /**
     * 指向下一个英雄结点
     */
    public SingleHeroNode next;

    public SingleHeroNode(Integer 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 + '\'' +
                '}';
    }
}

package com.tomdd.linkedlist;

import com.tomdd.model.SingleHeroNode;

/**
 * 英雄单向链表
 *
 * @author zx
 * @date 2022年12月21日 10:32
 */
public class HeroSingleLinkedList {
    /**
     * 初始化一个头结点(头结点不能动)
     */
    private SingleHeroNode head = new SingleHeroNode(0, null, null);

    /**
     * 添加结点数据到单向链表
     */
    public void add(SingleHeroNode singleHeroNode) { //尾插发
        //思路:找到结点最后一个结点数据，然后把新增的数据放到结点末尾即可 [不考虑编号顺序]
        //找到末尾结点;然后末尾结点的next域指向新增结点

        //1.定义临时结点
        SingleHeroNode temp = head;
        //2.遍历链表找到最后
        while (true) {
            if (temp.next == null) {
                break;
            }
            //temp 往后移
            temp = temp.next;
        }
        temp.next = singleHeroNode;
    }

    /**
     * <h2>遍历链表</h2>
     * 需要辅助遍历.head结点不能动的。
     */
    public void list() {
        //1.链表是否为空
        if (head.next == null) {
            return;
        }
        SingleHeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                return;
            }

            System.out.println(temp);
            temp = temp.next;

        }
    }
    
}

5.2 按照英雄编号进行顺序添加

5.2.1 思路分析

• 这里添加的位置是他真正添加的位置的前一个节点，找到这个这个节点后可以直接使用
  • temp.next = newNode; newNode.next = temp.next

5.2.2 代码实现

    /**
     * <h2>按照编号顺序添加</h2>
     * 添加的时候根据no进行排名，也就是插入后根据no排序
     * 根据排名添加英雄，如果已经存在排名给出提示
     * <p>
     * 思路分析:
     * 1.首先找到新添加的位置,是通过辅助指针 temp,也就是temp.next.no > newNode.no
     * <p>
     * 2.newNode.next = temp.next
     * <p>
     * 3.temp.next = newNode
     */
    public void addByOrder(SingleHeroNode singleHeroNode) throws Exception {
        //头结点不能动，通过temp 辅助指针来帮助找到添加的位置。
        //temp.next.no > newNode.no 也就是temp的下一个节点
        // 位于添加位置的前一个节点。
        SingleHeroNode temp = head;
        //标识符，表示添加的编号是否存在，默认为false;
        Boolean flag = false;
        while (true) {
            if (temp.next == null) {
                //说明temp在链表的最后，添加的结点在链表最后
                break;
            }
            if (temp.next.no > singleHeroNode.no) {
                //位置找到。就在 temp  ~ temp.next中间添加新节点
                break;
            }
            if (temp.next.no == singleHeroNode.no) {
                //说明添加的节点已经存在，不能添加
                flag = true;
            }
            //指针后移动
            temp = temp.next;
        }
        if (flag) {
            throw new IllegalAccessException("英雄编号:" + singleHeroNode.no + "已经存在");
        }
        singleHeroNode.next = temp.next;
        temp.next = singleHeroNode;
    }

5.3 链表的修改和删除

5.3.1 思路分析

• 修改
  • 通过遍历找到需要修改的节点
  • 找到该节点后直接修改节点里面的数据内容
• 删除
  • 找到该需要删除节点的前面一个节点 ,比如:temp
  • 改指针引用: temp.next = temp.next.next即可

5.3.2 代码实现

    /**
     * <h2>修改结点</h2>
     * 修改名称和昵称
     *
     * @return 返回修改的结点
     */
    public void updateNodeByNo(SingleHeroNode singleHeroNode) throws Exception {
        //根据heroNode的no进行修改
        if (head.next == null) {
            throw new IllegalAccessException("节点链表为空");
        }
        SingleHeroNode temp = head.next;
        //表示是否找到该结点
        Boolean flag = false;
        while (true) {
            if (temp == null) {
                // 表示链表已经结束，没有找到要修改的结点信息
                break;
            }
            if (temp.no == singleHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag是否找到要修改的结点
        if (flag) {
            temp.name = singleHeroNode.name;
            temp.nickName = singleHeroNode.nickName;
        }
        if (!flag) {
            throw new IllegalAccessException("没有找到编号:" + singleHeroNode.no + "节点信息");
        }
    }


    /**
     * <h2>删除结点</h2>
     * 找到要删除节点的上一个结点
     * <p>
     * 思路分析:
     * 1.先找到需要删除这个节点的前一个节点。【采用临时指针】
     * <p>
     * 2.temp.next = temp.next.next
     * 3.被删除的节点将不会有其他引用指向，将会被GC进行回收
     */
    public void delNode(SingleHeroNode singleHeroNode) throws Exception {
        //head 节点不能动，需要辅助指针temp；然后找到待删除的前一个节点。
        // 比较的时候使用: temp.next.no = delNode.no 进行比较
        SingleHeroNode temp = head;
        //是否找到待删除节点的前一个节点
        Boolean flag = false;
        for (; ; ) {
            if (temp.next == null) {
                //已经到链表最后
                break;
            }
            if (temp.next.no == singleHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.next = temp.next.next;
        }
        if (!flag) {
            throw new IllegalAccessException("节点编号:" + singleHeroNode.no + "不存在");
        }
    }

5.4 完整的代码

package com.tomdd.linkedlist;

import com.tomdd.model.SingleHeroNode;

import java.util.Stack;

/**
 * <h1>单向链表</h1>
 * <p>
 * 往结点末尾添加，不考虑排序
 *
 * @author zx
 * @date 2022年11月12日 10:00
 */
@SuppressWarnings("all")
public class SingleLinkedList {
    /**
     * 初始化一个头结点(头结点不能动)
     */
    private SingleHeroNode head = new SingleHeroNode(0, null, null);

    /**
     * 添加结点数据到单向链表
     */
    public void add(SingleHeroNode singleHeroNode) { //尾插发
        //思路:找到结点最后一个结点数据，然后把新增的数据放到结点末尾即可 [不考虑编号顺序]
        //找到末尾结点;然后末尾结点的next域指向新增结点

        //1.定义临时结点
        SingleHeroNode temp = head;
        //2.遍历链表找到最后
        while (true) {
            if (temp.next == null) {
                break;
            }
            //temp 往后移
            temp = temp.next;
        }
        temp.next = singleHeroNode;
    }

    /**
     * <h2>按照编号顺序添加</h2>
     * 添加的时候根据no进行排名，也就是插入后根据no排序
     * 根据排名添加英雄，如果已经存在排名给出提示
     * <p>
     * 思路分析:
     * 1.首先找到新添加的位置,是通过辅助指针 temp,也就是temp.next.no > newNode.no
     * <p>
     * 2.newNode.next = temp.next
     * <p>
     * 3.temp.next = newNode
     */
    public void addByOrder(SingleHeroNode singleHeroNode) throws Exception {
        //头结点不能动，通过temp 辅助指针来帮助找到添加的位置。
        //temp.next.no > newNode.no 也就是temp的下一个节点
        // 位于添加位置的前一个节点。
        SingleHeroNode temp = head;
        //标识符，表示添加的编号是否存在，默认为false;
        Boolean flag = false;
        while (true) {
            if (temp.next == null) {
                //说明temp在链表的最后，添加的结点在链表最后
                break;
            }
            if (temp.next.no > singleHeroNode.no) {
                //位置找到。就在 temp  ~ temp.next中间添加新节点
                break;
            }
            if (temp.next.no == singleHeroNode.no) {
                //说明添加的节点已经存在，不能添加
                flag = true;
            }
            //指针后移动
            temp = temp.next;
        }
        if (flag) {
            throw new IllegalAccessException("英雄编号:" + singleHeroNode.no + "已经存在");
        }
        singleHeroNode.next = temp.next;
        temp.next = singleHeroNode;
    }

    /**
     * <h2>删除结点</h2>
     * 找到要删除节点的上一个结点
     * <p>
     * 思路分析:
     * 1.先找到需要删除这个节点的前一个节点。【采用临时指针】
     * <p>
     * 2.temp.next = temp.next.next
     * 3.被删除的节点将不会有其他引用指向，将会被GC进行回收
     */
    public void delNode(SingleHeroNode singleHeroNode) throws Exception {
        //head 节点不能动，需要辅助指针temp；然后找到待删除的前一个节点。
        // 比较的时候使用: temp.next.no = delNode.no 进行比较
        SingleHeroNode temp = head;
        //是否找到待删除节点的前一个节点
        Boolean flag = false;
        for (; ; ) {
            if (temp.next == null) {
                //已经到链表最后
                break;
            }
            if (temp.next.no == singleHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.next = temp.next.next;
        }
        if (!flag) {
            throw new IllegalAccessException("节点编号:" + singleHeroNode.no + "不存在");
        }
    }

    /**
     * <h2>修改结点</h2>
     * 修改名称和昵称
     *
     * @return 返回修改的结点
     */
    public void updateNodeByNo(SingleHeroNode singleHeroNode) throws Exception {
        //根据heroNode的no进行修改
        if (head.next == null) {
            throw new IllegalAccessException("节点链表为空");
        }
        SingleHeroNode temp = head.next;
        //表示是否找到该结点
        Boolean flag = false;
        while (true) {
            if (temp == null) {
                // 表示链表已经结束，没有找到要修改的结点信息
                break;
            }
            if (temp.no == singleHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag是否找到要修改的结点
        if (flag) {
            temp.name = singleHeroNode.name;
            temp.nickName = singleHeroNode.nickName;
        }
        if (!flag) {
            throw new IllegalAccessException("没有找到编号:" + singleHeroNode.no + "节点信息");
        }
    }


    /**
     * <h2>遍历链表</h2>
     * 需要辅助遍历.head结点不能动的。
     */
    public void list() {
        //1.链表是否为空
        if (head.next == null) {
            return;
        }
        SingleHeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                return;
            }

            System.out.println(temp);
            temp = temp.next;

        }
    }


    /**
     * <h2>链表个数</h2>
     * 获取单向链表有效个数，不统计头节点
     */
    public synchronized int size() {
        //链表为空
        if (head.next == null) {
            return 0;
        }
        int size = 0;
        SingleHeroNode currentNode = head.next;
        while (currentNode != null) {
            size++;
            currentNode = currentNode.next;
        }
        return size;
    }

    /**
     * <h2>查找单链表中倒数第K个结点</h2>
     * 思路:
     * 1. 编写一个方法，接收index,表示倒数第index节点
     * <p>
     * 2.遍历链表得到这个链表的总个数
     * <p>
     * 3. 得到size个数后，我们从链表的第一个开始遍历(size-index)就可以得到
     */
    public SingleHeroNode getLastIndexNode(int index) {
        int size = size();
        //链表为空返回空
        if (size == 0) {
            return null;
        }
        //第二次遍历（size-index)就是倒数index的节点
        if (index <= 0 || index > size) {
            return null;
        }
        SingleHeroNode temp = head.next;
        for (int i = 0; i < (size - index); i++) {
            temp = temp.next;
        }

        return temp;
    }

    /**
     * <h2>反转链表</h2>
     */
    public void reverse() {
        //空链表或者只有一个节点不用反转
        if (head.next == null || head.next.next == null) {
            return;
        }
        //当前节点
        SingleHeroNode curr = head.next;
        //记录当前节点的下一个节点。
        SingleHeroNode currNext = null;

        SingleHeroNode reverseHead = new SingleHeroNode(0, null, null);
        //遍历原来的链表 ,并放到反转的链表头，并且放到新的节点的前面。
        while (curr != null) { //头插法
            //先暂时保持当前节点的下一个节点，便于节点往下遍历
            currNext = curr.next;

            //当前节点下一个节点指向反转节点的下一个节点[进行构建新的反转链表]
            curr.next = reverseHead.next;
            //将curr连接到新的链表上
            reverseHead.next = curr;

            curr = currNext;
        }
        head.next = reverseHead.next;
    }

    public void reversePrintByStack(){
        if(head.next == null){
            //空链表不打印
            return;
        }
        //将节点压入栈中
        Stack<SingleHeroNode> singleHeroNodeStack = new Stack<>();
        SingleHeroNode temp = head.next;
        while(temp !=null){
            singleHeroNodeStack.push(temp);
            temp = temp.next;
        }

        while(singleHeroNodeStack.size()>0){
            System.out.println(singleHeroNodeStack.pop());
        }

    }

}

6.双向链表

package com.tomdd.model;

/**
 * 双向节点英雄结点对象
 * <p>
 * 可以定义为内部类
 *
 * @author zx
 * @date 2022年11月13日 18:59
 */
public class DoubleHeroNode {
    /**
     * 英雄编号
     */
    public Integer no;

    /**
     * 英雄mc
     */
    public String name;

    /**
     * 昵称
     */
    public String nickName;

    /**
     * 指向下一个英雄结点
     */
    public DoubleHeroNode next;

    /**
     * 指向上一个节点
     */
    public DoubleHeroNode pre;

    public DoubleHeroNode(Integer 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 + '\'' +
                '}';
    }
}

package com.tomdd.linkedlist;

import com.tomdd.model.DoubleHeroNode;

/**
 * 双向链表
 *
 * @author zx
 * @date 2022年11月13日 18:58
 */
public class DoubleLinkedList {

    /*
    双向链表的CRUD思路分析:
    1.遍历的方式和单链表的方式一样，只是可以向前、向后查找
    2.添加:
        默认添加到链表最后
        1.辅助节点找到链表末尾，next 指向为空就是链表的末尾
        2.temp.next = newHeroNode 末尾结点下一个节点指向新增的节点
        3.newHeroNode.pre = temp; 维护新增结点的上一个结点

    3.修改: 修改的思路和单向链表的修改思路是一样。
    4.删除: 双向链表中有上一个和下一个节点的引用，可以实现自我删除,找到要删除节点。
        temp.pre.next = temp.next
        temp.next.pre = temp.pre
     */
    /**
     * 头结点
     */
    private final DoubleHeroNode head = new DoubleHeroNode(0, null, null);


    public void add(DoubleHeroNode newHeroNode) {
        if (head.next == null) {
            head.next = newHeroNode;
            newHeroNode.pre = head;
            return;
        }
        DoubleHeroNode temp = head.next;
        //2.遍历链表找到最后
        while (temp !=null) {
            //temp 往后移
            temp = temp.next;
        }
        temp.next = newHeroNode;
        newHeroNode.pre = temp;

    }


    public void list() {
        if (head.next == null) {
            return;
        }
        DoubleHeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }


    }
}

7.使用for循环遍历链表另一种形式

package com.mayikt.linkedlist;

/**
 * 单向链表
 *
 * @author zx
 * @date 2022年01月28日 16:10
 */
public class SingleLinkedList<T> {

    /**
     * 头结点
     */
    transient Node<T> firstNode;

    /**
     * 链表结点个数
     */
    int size = 0;


    /**
     * 把元素添加到链表的头结点
     *
     * @param t 添加的元素
     * @return true表示添加成功
     */
    public boolean add(T t) {
        addNodeToHead(t);
        return true;
    }

    private void addNodeToHead(T t) {
        Node<T> tempNode = firstNode;
        firstNode = new Node<>(t, tempNode);
        size++;
    }

    public void showInfo() {

        Node<T> temp = firstNode;

        while (true) {
            System.out.println(temp.item);
            if (temp.nextEntry == null) {
                //链表遍历到最后了
                break;
            }
            temp = temp.nextEntry;

        }
    }


    /**
     * 使用for循环遍历单向链表的写法
     */
    public void foreEach() {
        for (Node<T> temp = firstNode; temp != null; temp = temp.nextEntry) {
            System.out.println(temp.item);
        }
    }

    static class Node<T> {
        T item;

        Node<T> nextEntry;

        public Node(T item, Node<T> nextEntry) {
            this.item = item;
            this.nextEntry = nextEntry;
        }
    }

    public static void main(String[] args) {
        SingleLinkedList<String> singleLinkedList = new SingleLinkedList<>();
        singleLinkedList.add("I");
        singleLinkedList.add("LOVE");
        singleLinkedList.add("YOU");

        singleLinkedList.showInfo();
        System.out.println("--------------使用for循环遍历链表:------------------");
        singleLinkedList.foreEach();
    }
}

8.环形链表

8.1 思路分析

8.2 代码实现

package com.mayikt.circle_linked;

/**
 * <h1>环形链表</h1>
 *
 * @author zx
 * @date 2022年07月12日 8:18
 */
public class CircleLinked {

    /**
     * 环形链表的第一个节点
     */
    private Body first = new Body(-1);

    /**
     * <h2>构建环形链表</h2>
     *
     * @param num 环形链表的节点数
     */
    public void buildCircleLinked(int num) {
        if (num < 1) {
            throw new RuntimeException("节点数应该大于1");
        }
        //当前节点(辅助节点）
        Body currentBody = null;
        for (int i = 1; i <= num; i++) {
            Body body = new Body(i);
            if (i == 1) {
                first = body;
                //第一个节点进行自关联
                first.setNext(first);
                //辅助遍历 复制为第一个节点
                currentBody = first;
                continue;
            }
            //添加第二个节点的时候
            currentBody.setNext(body);
            body.setNext(first);
            //移动当前节点为新增的节点
            currentBody = body;
        }

    }

    /**
     * <h2>打印环形链表</h2>
     */
    public void printCircleLinked() {
        if (first.getNo() == -1) {
            throw new RuntimeException("环形链表为空");
        }
        Body currentBody = first;
        while (true) {

            System.out.println(currentBody.getNo());
            currentBody = currentBody.getNext();
            if (currentBody.getNext() == first) {
                System.out.println(currentBody.getNo());
                break;
            }

        }
    }

    /**
     * <h2>环形链表节点</h2>
     */
    static class Body {
        private Integer no;
        private Body next;

        public Body(Integer no) {
            this.no = no;
        }

        public Integer getNo() {
            return no;
        }

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

        public Body getNext() {
            return next;
        }

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