链表:单向链表,双向链表,单向环形链表
1,单向链表
1.1,单项链表基本介绍
- 链表是以节点的方式存储
- 链表的每个节点都包括
data
域和next
域,指向下一个节点 - 链表的各个节点不一定都是连续存储的
- 链表分为带头结点的链表和不带头结点的链表
1.2,单向链表示意图
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 + "]";
}
}
还没有评论,来说两句吧...