链表：单向链表，双向链表，单向环形链表

亦凉 2023-02-27 13:57 6阅读 0赞

# 1，单向链表 #

## 1.1，单项链表基本介绍 ##

*  链表是以节点的方式存储
 *  链表的每个节点都包括`data`域和`next`域，指向下一个节点
 *  链表的各个节点不一定都是连续存储的
 *  链表分为带头结点的链表和不带头结点的链表

## 1.2，单向链表示意图 ##

![在这里插入图片描述][20200718134404827.png]

## 1.3，单向链表代码实现 ##

package com.self.datastructure.linked;
    
    import lombok.Data;
    
    /** * @author LiYanBin * @create 2020-01-08 14:06 **/
    public class MyLinkedList { 
    
        public static void main(String[] args) { 
            SimpleLinkedList linkedList = new SimpleLinkedList();
            linkedList.addByOrder(new LinkedNode(2, "名称", "昵称"));
            linkedList.addByOrder(new LinkedNode(1, "名称", "昵称"));
            linkedList.addByOrder(new LinkedNode(4, "名称", "昵称"));
            linkedList.addByOrder(new LinkedNode(3, "名称", "昵称"));
            linkedList.update(new LinkedNode(1, "覆盖", "覆盖"));
            linkedList.delete(new LinkedNode(3, "", ""));
            linkedList.showDetails();
        }
    
    }
    
    class SimpleLinkedList { 
    
        // 初始化头结点
        private LinkedNode head = new LinkedNode(-1, "", "", null);
    
        // 添加数据, 直接添加不带过滤
        public void add(LinkedNode linkedNode) { 
            // 赋值头节点到临时节点
            LinkedNode temp = head;
            while (null != temp.getNext()) { 
                temp = temp.getNext();
            }
            // 将尾节点的下一个节点指向当前节点
            temp.setNext(linkedNode);
        }
    
        // 添加数据, 按照主键排序
        public void addByOrder(LinkedNode linkedNode) { 
            // 赋值头几点到临时节点
            LinkedNode temp = head;
            while (null != temp.getNext()) { 
                LinkedNode nextNode = temp.getNext();
                // 进行升序排列
                if (nextNode.getNo() > linkedNode.getNo()) { 
                    temp.setNext(linkedNode);
                    linkedNode.setNext(nextNode);
                    return;
                    // 相同直接进行修改
                } else if (nextNode.getNo() == linkedNode.getNo()) { 
                    temp.setNext(linkedNode);
                    linkedNode.setNext(nextNode.getNext());
                    nextNode.setNext(null); // 辅助GC
                    return;
                }
                temp = nextNode;
            }
            // 将尾节点的下一个节点指向当前节点
            temp.setNext(linkedNode);
        }
    
        // 修改数据
        public void update(LinkedNode linkedNode) { 
            LinkedNode temp = head;
            while (null != temp) { 
                LinkedNode next = temp.getNext();
                if (null != next && next.getNo() == linkedNode.getNo()) { 
                    temp.setNext(linkedNode);
                    linkedNode.setNext(next.getNext());
                    next.setNext(null); // 辅助GC
                    return;
                }
                temp = next;
            }
        }
    
        // 删除节点, 根据编号删除
        public void delete(LinkedNode linkedNode) { 
            LinkedNode temp = head;
            while (null != temp.getNext()) { 
                LinkedNode next = temp.getNext();
                // 找到该节点, 并把该节点的next节点指向上一个节点的next, 把该节点挂空
                if (next.getNo() == linkedNode.getNo()) { 
                    temp.setNext(next.getNext());
                    next.setNext(null); // 辅助GC
                    return;
                }
                temp = next;
            }
        }
    
        // 展示详情信息
        public void showDetails() { 
            LinkedNode next = head.getNext();
            while (next != null) { 
                System.out.println(next);
                next = next.getNext();
            }
        }
    
    }
    
    @Data
    class LinkedNode { 
    
        // 编号, 编号为主键, 不允许重复, 并需要顺序处理
        private int no;
    
        // 名称
        private String name;
    
        // 昵称
        private String nickName;
    
        // 单项链表
        private LinkedNode next;
    
        public LinkedNode(int no, String name, String nickName) { 
            this(no, name, nickName, null);
        }
    
        public LinkedNode(int no, String name, String nickName, LinkedNode next) { 
            this.no = no;
            this.name = name;
            this.nickName = nickName;
            this.next = next;
        }
    
        @Override
        public String toString() { 
            return "[LinkedNode: no = " + no + ", name = " + name + ", nickName = " + nickName + "]";
        }
    
    }

## 1.4，单向链表相关面试题 ##

### 1.4.1，获取单链表的节点个数 ###

/** * 获取单向链表中有效节点的数量 * @param head 头节点 * @param isNeedHead 头节点是否是有效节点 * @return */
    public static int getNodeLength(LinkedNode head, boolean isNeedHead) { 
        if (null == head) { 
            return 0;
        }
        // 需要头节点直接初始化为1，表示头结点已经统计
        int count = isNeedHead ? 1 : 0;
        LinkedNode temp = head;
        for (;null != temp.getNext();) { 
            count++;
            temp = temp.getNext();
        }
        return count;
    }

### 1.4.2，查找单向链表中的倒数第K个节点：即获取正数第（count - K）个节点的数据 ###

/** * 获取单链表中的倒数第K个节点 * 索引从0开始算, 即倒是第K个节点就是正数第(length - k) * @param head 单向链表头结点 * @param isNeedHead 头结点是否是有效节点 * @param descCount 倒数位置 * @return */
    public static LinkedNode getIndexDataDesc(LinkedNode head, boolean isNeedHead, int descCount) { 
    	// 获取数量
    	int count = getNodeLength(head, isNeedHead);
    	if (count < descCount) { 
    		throw new IndexOutOfBoundsException("索引越界");
    	}
    	int index = count - descCount;
    	LinkedNode temp = isNeedHead ? head : head.getNext();
    	for (int i = 0; i < index; i++, temp = temp.getNext());
    	return temp;
    }

### 1.4.3，单链表反转 ###

/** * 单向链表反转 * 每次获取下一个节点, 并重新构造该节点为头节点 * 把之前存储的头节点置位该节点的next节点, 即一步步遍历, 一步步后推 * @param head 单向链表 * @param isNeedHead 头节点是否是有效节点 * @return */
    public static LinkedNode reverseLinked(LinkedNode head, boolean isNeedHead) { 
    	// 获取有效数据
    	LinkedNode realData = isNeedHead ? head : head.getNext();
    	// 初始化返回数据, 不需要头节点的直接初始化虚拟节点
    	LinkedNode reverseLinked = isNeedHead ? null : new LinkedNode(head);
    	// 反转
    	for (; null != realData ;) { 
    		// 构造新节点
    		LinkedNode newNode = new LinkedNode(realData);
    		if (null == reverseLinked) { 
    			reverseLinked = newNode;
    		} else { 
    			// 获取下一个节点
    			// 非虚拟头节点
    			if (isNeedHead) { 
    				newNode.setNext(reverseLinked);
    				reverseLinked = newNode;
    			} else {  // 虚拟头节点
    				// 获取虚拟头节点的下一个节点
    				LinkedNode nextNode = reverseLinked.getNext();
    				// 把原节点挂到该节点下
    				newNode.setNext(nextNode);
    				// 把当前节点设为下一个节点
    				reverseLinked.setNext(newNode);
    			}
    		}
    		realData = realData.getNext();
    	}
    	return reverseLinked;
    }

### 1.4.4，反向打印链表 ###

/** * 从尾节点开始打印链表 * 方式1: * 先将单链表进行翻转操作, 然后进行遍历即可 * 该方式可能会改变原链表结构, 不建议 * 该方式可以直接调用反转方法, 并打印 * 方式2: * 利用栈数据结构, 将各个节点压入栈中 * 利用栈先进后出的特点, 完成逆序打印 * @param linkedNode 节点 * @param isNeedHead 头结点是否是有效节点 */
    public static void showDetailsReverse(LinkedNode linkedNode, boolean isNeedHead) { 
    	Stack<LinkedNode> stack = new Stack<>();
    	LinkedNode realNode = isNeedHead ? linkedNode : linkedNode.getNext();
    	if (null == realNode) { 
    		return;
    	}
    	// 遍历节点, 添加到栈中
    	for (; null != realNode; ) { 
    		stack.push(realNode);
    		realNode = realNode.getNext();
    	}
    	// 打印栈对象
    	LinkedNode currNode = null;
    	for (;stack.size() > 0; ) { 
    		System.out.println(stack.pop());
    	}
    }

### 1.4.5，合并两个有序的单链表，合并之后的链表依然有序 ###

/** * 合并两个有序(顺序)链表, 默认不需要头结点 * @param firstNode * @param secondNode */
    public static LinkedNode mergeOrderNode(LinkedNode firstNode, LinkedNode secondNode) { 
    	// 获取有效节点
    	firstNode = firstNode.getNext();
    	secondNode = secondNode.getNext();
    	// 存在为空, 直接返回
    	if (null == firstNode || null == secondNode) { 
    		return null == firstNode ? secondNode : firstNode;
    	}
    	// 比较节点数据
    	// 用首节点编号较小的链表进行遍历,
    	// 较大编号的链表进行填充, 最终返回有效节点
    	return firstNode.getNo() > secondNode.getNo()
    			? doMergeOrderNode(secondNode, firstNode)
    			: doMergeOrderNode(firstNode, secondNode);
    }
    
    public static LinkedNode doMergeOrderNode(LinkedNode firstNode, LinkedNode secondNode) { 
    	// 初始化头节点
    	SimpleLinkedList simpleLinkedList = new SimpleLinkedList();
    	// 遍历节点进行填充
    	for (;null != firstNode;) { 
    		// first节点数据大于second节点数据, 将second节点数据置于之前
    		for (;secondNode != null && firstNode.getNo() > secondNode.getNo();) { 
    			simpleLinkedList.add(new LinkedNode(secondNode));
    			// 当前second已经被比较过, 向前推动一位
    			secondNode = secondNode.getNext();
    		}
    		// 处理完成当前区间的seconde数据后, 添加first数据
    		simpleLinkedList.add(new LinkedNode(firstNode));
    		firstNode = firstNode.getNext();
    	}
    	// first节点遍历完成后, 如果second节点还存在数据, 全部添加到最后
    	for (;null != secondNode;) { 
    		simpleLinkedList.add(new LinkedNode(secondNode));
    		secondNode = secondNode.getNext();
    	}
    	return simpleLinkedList.getHead();
    }

# 2，双向链表 #

## 2.1，双向链表介绍 ##

*  单向链表查找方向是能是一个方向；双向链表可以向前或者向后查找
 *  单向链表不能自我删除，需要靠辅助节点即前一个节点；双向链表可以进行自删除，因为同时持有上一个节点和下一个节点的地址
 *  **遍历**：遍历方式与单向链表基本一致，不过双向链表可以直接从后往前遍历
 *  **添加**：
    
     *  先找到需要插入到双向链表的目标节点
     *  讲节点和对应前置节点与后置节点的`pre`和`next`属性进行修改
 *  **删除**：
    
     *  双向链表可以实现单个节点的自删除，直接遍历到需要删除的当前节点
     *  将当前节点前置节点的`next`属性指向当前节点的后置节点
     *  将当前节点后置节点的`pre`属性指向当前节点的前置节点
     *  处理之后，当前节点在链表中会挂空，也就是从链表中删除

## 2.2，代码演示 ##

package com.self.datastructure.linked;
    
    import lombok.Data;
    
    /** * 双向链表 * @author LiYanBin * @create 2020-01-09 14:21 **/
    public class DoubleLinkedList { 
    
        public static void main(String[] args) { 
            DLinkedList dLinkedList = new DLinkedList();
    // dLinkedList.add(new DoubleNode(0, "名称", "昵称"));
    // dLinkedList.add(new DoubleNode(1, "名称", "昵称"));
    // dLinkedList.add(new DoubleNode(2, "名称", "昵称"));
    // dLinkedList.add(new DoubleNode(3, "名称", "昵称"));
    
            dLinkedList.addByOrder(new DoubleNode(3, "名称", "昵称"));
            dLinkedList.addByOrder(new DoubleNode(2, "名称", "昵称"));
            dLinkedList.addByOrder(new DoubleNode(4, "名称", "昵称"));
            dLinkedList.addByOrder(new DoubleNode(1, "名称", "昵称"));
            dLinkedList.showDetailsFromHead();
        }
    
    }
    
    class DLinkedList { 
    
        private DoubleNode head = new DoubleNode(-1, "", "");
    
        private DoubleNode tail = new DoubleNode(-2, "", "");
    
        public DLinkedList() { 
            head.setNext(tail);
            tail.setPre(head);
        }
    
        // 根据序列号添加
        public void addByOrder(DoubleNode doubleNode) { 
            // 获取有效数据
            DoubleNode realData = head.getNext();
            for (;null != realData;) { 
                // 遍历到尾节点, 直接添加
                if (realData == tail) { 
                    add(doubleNode);
                    return;
                }
                // 编号大于当前编号, 则置于该编号之前
                if (realData.getNo() > doubleNode.getNo()) { 
                    DoubleNode pre = realData.getPre();
                    pre.setNext(doubleNode);
                    doubleNode.setPre(pre);
                    doubleNode.setNext(realData);
                    realData.setPre(doubleNode);
                    return;
                }
                realData = realData.getNext();
            }
        }
    
        // 添加数据到链表中, 默认添加到链表尾部
        public void add(DoubleNode doubleNode) { 
            // 获取尾节点的上一个节点
            DoubleNode preNode = tail.getPre();
            // 将上一个节点置为该节点的前置节点,
            preNode.setNext(doubleNode);
            // 添加该节点的前置节点和后置节点
            doubleNode.setPre(preNode);
            doubleNode.setNext(tail);
            // 将tail节点的前置节点改为该节点
            tail.setPre(doubleNode);
        }
    
        // 删除指定数据
        public void remove(int no) { 
            DoubleNode realData = head.getNext();
            for (;null != realData && tail != realData;) { 
                // 匹配到数据, 直接移除
                if (realData.getNo() == no) { 
                    // 获取前置节点
                    DoubleNode pre = realData.getPre();
                    // 获取后置节点
                    DoubleNode next = realData.getNext();
                    // 互为前置后置节点, 将当前节点挂空
                    pre.setNext(next);
                    next.setPre(pre);
                    realData = null; // 辅助GC
                    return;
                }
                realData = realData.getNext();
            }
        }
    
        // 打印, 从头打印
        public void showDetailsFromHead() { 
            DoubleNode realData = head.getNext();
            for (;null != realData && tail != realData;) { 
                System.out.println(realData);
                realData = realData.getNext();
            }
        }
    
        // 打印, 从尾部打印
        public void showDetailsFromTail() { 
            DoubleNode realData = tail.getPre();
            for (;null != realData && realData != head;) { 
                System.out.println(realData);
                realData = realData.getPre();
            }
        }
    
        public DoubleNode getHead() { 
            return head;
        }
    
        public DoubleNode getTail() { 
            return tail;
        }
    
    }
    
    @Data
    class DoubleNode { 
    
        private DoubleNode pre;
    
        private DoubleNode next;
    
        private int no;
    
        private String name;
    
        private String nickName;
    
        public DoubleNode(DoubleNode doubleNode) { 
            this(doubleNode.getNo(), doubleNode.getName(), doubleNode.getNickName());
        }
    
        public DoubleNode(int no, String name, String nickName) { 
            this(no, name, nickName, null, null);
        }
    
        public DoubleNode(int no, String name, String nickName, DoubleNode pre, DoubleNode next) { 
            this.no = no;
            this.name = name;
            this.nickName = nickName;
            this.pre = pre;
            this.next = next;
        }
    
        @Override
        public String toString() { 
            return "[DoubleNode: no = " + no + ", name = " + name + ", nickName = " + nickName + "]";
        }
    
    }

# 3，单向环形链表：约瑟夫问题（Josephu） #

## 3.1，Josephu（约瑟夫）问题介绍 ##

*  设编号为1，2 … n的n个人围成一个圈，并约定编号为K（1<=K<=n）的人从1开始报数，数到M的那个人出列，他的下一位又从1开始数，依次类推，直到所有人出列
 *  通过不带头节点的单向链表来处理

## 3.2，Josephu（约瑟夫）问题实现代码 ##

package com.self.datastructure.linked;
    
    import lombok.Data;
    
    import java.util.Scanner;
    
    /** * 约瑟夫问题解决代码 * @author LiYanBin * @create 2020-01-09 15:45 **/
    public class JosephuQuestion { 
    
        public static void main(String[] args) { 
            // 初始化游戏玩家
            JosephuLinkedList linkedList = new JosephuLinkedList();
            for (int i = 0; i < 10; i++) { 
                linkedList.add(new Node(i));
            }
            linkedList.startGame();
        }
    
    }
    
    class JosephuLinkedList { 
    
        // 该头节点表示有效节点
        private Node head = null;
    
        // 统计总数
        private int totalCount = 0;
    
        // 开始游戏
        public void startGame() { 
            Scanner scanner = new Scanner(System.in);
            // 默认从头号玩家开始
            Node startNode = head;
            for(;;) { 
                if (totalCount == 0) { 
                    System.out.println("编号全部移除, 游戏结束...");
                    return;
                }
                System.out.println("当前游戏人数: " + totalCount);
                String input = scanner.nextLine();
                switch (input) { 
                    case "s": // show
                        showDetails();
                        break;
                    case "r": // run
                        System.out.println("输入跳过的人数: M");
                        int runCount = scanner.nextInt();
                        // 移除数据
                        // 从1号开始数两位, 则移除3号, 下一次从4号开始玩
                        // 此处获取要移除数据的前一位
                        Node targetPreNode = startNode;
                        for (int i = 0; i < runCount - 1; i++, targetPreNode = targetPreNode.getNext());
                        // 记录, 获取移除数据的下一个数据, 此处需要两次next
                        startNode = targetPreNode.getNext().getNext();
                        System.out.println("移除完成..., 移除编号: " + targetPreNode.getNext().getNo() + ", 下次开始编号: " + startNode.getNo());
                        // 直接移除, 将该节点的next 指向目标节点的next, 将目标节点挂空
                        targetPreNode.setNext(targetPreNode.getNext().getNext());
                        totalCount--;
                        // 移除, 此处不需要调移除, 因为节点已经挂空
                        // remove(targetNode.getNo());
                        break;
                    case "e": //exit
                        return;
                    default:
                        break;
                }
            }
        }
    
        // 添加元素
        public void add(Node node) { 
            // 设置为头结点
            if (null == head) { 
                totalCount++;
                head = node;
                head.setNext(head);
                return;
            }
            // 与头节点进行比较
            Node temp = head;
            for (;null != temp;) { 
                // 从头节点开始, 每次获取到下一个节点进行判断
                Node next = temp.getNext();
                if (head == next) {  // 与头节点相等, 说明已经到有效链表末尾
                    totalCount++;
                    temp.setNext(node);
                    node.setNext(head);
                    return;
                }
                temp = temp.getNext();
            }
        }
    
        public void remove(int no) { 
            if (null == head) return;
            // 头结点处理
            if (head.getNo() == no) { 
                // 链表只有当前数据, 直接清空
                if (head == head.getNext()) { 
                    head = null;
    
                } else { 
                    // 链表存在其他数据, 移除头节点后遍历
                    Node preHead = head;
                    head = head.getNext();
                    Node temp = head;
                    for (; null != temp; ) { 
                        // 再遇头节点
                        if (preHead == temp.getNext()) { 
                            temp.setNext(head);
                            break;
                        }
                        temp = temp.getNext();
                    }
                }
            } else {  // 非头节点处理
                Node temp = head;
                for (;null != temp;) { 
                    Node next = temp.getNext();
                    // 无论是否存在, 再遇头结点直接移除
                    if (next == head) { 
                        return;
                    }
                    // 存在, 直接移除
                    if (next.getNo() == no) { 
                        temp.setNext(next.getNext());
                        break;
                    }
                    temp = temp.getNext();
                }
            }
            totalCount--;
        }
    
        public void showDetails() { 
            if (null == head) { 
                System.out.println("数据为空...");
                return;
            }
            Node temp = head;
            boolean flag = false;
            for (;null != temp;) { 
                if (flag && temp == head) { 
                    System.out.println("遍历完成...");
                    return;
                }
                flag = true;
                System.out.println(temp);
                temp = temp.getNext();
            }
        }
    
        public Node getHead() { 
            return head;
        }
    
    }
    
    @Data
    class Node { 
    
        // 编号
        private int no;
    
        // 下一个节点
        private Node next;
    
        public Node(int no) { 
            this.no = no;
        }
    
        @Override
        public String toString() { 
            return "[Node: no = " + no + "]";
        }
    
    }

[20200718134404827.png]: /images/20230209/9265bdc970af462dbe29817537ebf6e4.png