链表
一、介绍
1、介绍
链表是一种非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点（链表中每一个元素称为节点）组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域
（1）单向链表(单链表)是链表的一种，它由节点组成，每个节点都包含下一个节点的指针
（2）双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据节点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后继节点
2、图解
（1）单向链表
（2）双向链表
二、单向链表
1、存于节点的User实体
package com.dashu.linear_structure.linked_list;
public class User {
/**
* 姓名
*/
private String name;
/**
* 年龄
*/
private int age;
public User(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}
2、单向节点
public class Node {
/**
* 编号
*/
private int no;
/**
* 用户
*/
private User user;
/**
* 下一个节点
*/
private Node next;
public Node(int no, User user) {
this.no = no;
this.user = user;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public User getUser() {
return user;
}
public void setUser(User user) {
this.user = user;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
3、带头节点的单向链表
package com.dashu.linear_structure.linked_list;
import java.util.Stack;
/**
* @Author: dashu
* @Description: 包含头节点的链表
* @Date: 2021/12/6 23:55
* @Version: 1.0
*/
public class HeadLinkedList {
/**
* 初始化头节点
*/
private Node headNode = new Node(0, new User("", 0));
/**
* 末尾添加节点
*
* @param node
*/
public void add(Node node) {
/**
* 获取头节点
*/
Node temp = headNode;
/**
* 循环遍历节点
*/
while (true) {
/**
* 节点后的下一个节点为null,则链表遍历结束，退出循环
*/
if (temp.getNext() == null) {
break;
}
/**
* 节点向后移一位
*/
temp = temp.getNext();
}
/**
* 添加节点
*/
temp.setNext(node);
}
/**
* 有序添加节点
*
* @param node
*/
public void addByOrderly(Node node) {
/**
* 获取头节点
*/
Node temp = headNode;
/**
* 循环遍历节点
*/
while (true) {
/**
* 节点后的下一个节点为null,则链表遍历结束，退出循环
*/
if (temp.getNext() == null) {
break;
}
/**
* 获取遍历节点的下一个节点的编号，判断是否与添加节点的编号相等
*
* 若相等的话，则可知，节点已经存在于链表
*
* 不可以在添加
*
* 抛出异常信息
*
*/
if (temp.getNext().getNo() == node.getNo()) {
throw new RuntimeException("元素已存在，请勿重复添加");
}
/**
* 获取遍历节点的下一个节点的编号，判断是否大于添加节点的编号
*
* 若大于的话，则可知，节点不存在于链表
*
* 且节点应该添加到当前节点的下一个节点
*
* 退出循环
*
*/
if (temp.getNext().getNo() > node.getNo()) {
break;
}
/**
* 节点向后移一位
*/
temp = temp.getNext();
}
/**
* 添加节点的下一个节点为当前节点的下一个节点
*/
node.setNext(temp.getNext());
/**
* 当前节点的下一个节点为添加的节点
*/
temp.setNext(node);
}
/**
* 节点修改
*
* @param node
*/
public void update(Node node) {
/**
* 判断头节点后的下一个节点是否为空，为空，说明链表没有数据
*/
if (headNode.getNext() == null) {
System.out.println("链表为空，修改失败");
return;
}
/**
* 获取头节点的下一个节点
*/
Node temp = headNode.getNext();
/**
* 用于判断节点是否在链表
*/
boolean flag = false;
/**
* 循环遍历节点
*/
while (true) {
/**
* 节点为null,则链表遍历结束，退出循环
*/
if (temp == null) {
break;
}
/**
* 判断遍历的节点编号是否于参数节点的编号相等
*
* 相等的话，则可判定该节点存在于链表中，flag = true，退出循环
*
* 并且修改的节点是 就是temp
*/
if (temp.getNo() == node.getNo()) {
flag = true;
break;
}
/**
* 节点向后移一位
*/
temp = temp.getNext();
}
/**
* 节点存在于链表
*/
if (flag) {
/**
* 修改节点
*/
temp.setUser(node.getUser());
} else {
/**
* 节点不存在于链表
*/
System.out.println("节点不存在，修改失败");
}
}
/**
* 根据编号删除节点
*
* @param no
*/
public void delete(int no) {
/**
* 判断头节点后的下一个节点是否为空，为空，说明链表没有数据
*/
if (headNode.getNext() == null) {
System.out.println("链表为空，删除失败");
return;
}
/**
* 获取头节点
*/
Node temp = headNode;
/**
* 用于判断节点是否在链表
*/
boolean flag = false;
/**
* 循环遍历节点
*/
while (true) {
/**
* 节点后的下一个节点为null,则链表遍历结束，退出循环
*/
if (temp.getNext() == null) {
break;
}
/**
* 判断节点下一个节点的编号，是否与参数no相等
*
* 相等的话，则可判定该节点存在于链表中，flag = true，退出循环
*
* 并且节点是 temp 后的下一个节点
*/
if (temp.getNext().getNo() == no) {
flag = true;
break;
}
/**
* 节点向后移一位
*/
temp = temp.getNext();
}
/**
* 节点存在于链表
*/
if (flag) {
/**
* 删除节点
*/
temp.setNext(temp.getNext().getNext());
} else {
/**
* 节点不存在于链表
*/
System.out.println("节点不存在，删除失败");
}
}
/**
* 打印链表
*/
public void print() {
/**
* 判断头节点后的下一个节点是否为空，为空，说明链表没有数据
*/
if (headNode.getNext() == null) {
System.out.println("链表为空");
return;
}
/**
* 获取头节点后的第一个节点
*/
Node temp = headNode.getNext();
/**
* 循环遍历
*/
while (true) {
/**
* 节点为null,链表遍历结束，退出循环
*/
if (temp == null) {
break;
}
/**
* 打印
*/
System.out.println("[编号：" + temp.getNo() + "用户名：" + temp.getUser().getName() + "年龄：" + temp.getUser().getAge() + "]");
/**
* 节点向后移一位
*/
temp = temp.getNext();
}
}
/**
* 获取链表有效节点数（包含头节点）
*
* @return
*/
public int size(Node headNode) {
/**
* 获取头节点
*/
Node temp = headNode;
/**
* 有效节点数
*/
int i = 0;
/**
* 循环遍历节点
*/
while (true) {
/**
* 节点为null,则链表遍历结束，退出循环
*/
if (temp == null) {
break;
}
/**
* 有效节点数+1
*/
i++;
/**
* 节点向后移一位
*/
temp = temp.getNext();
}
return i;
}
/**
* 查询单链表倒数第n个节点
*
* @param n
* @return
*/
public Node getNodeByReverse(int n) {
/**
* 判断头节点后的下一个节点是否为空，为空，说明链表没有数据
*/
if (headNode.getNext() == null) {
System.out.println("链表为空，查询失败");
return null;
}
/**
* 获取链表有效节点数
*/
int size = size(headNode);
/**
* 判断输入值是否大于有效节点数，如果大于，则无法取到节点
*/
if (n < 0 || n > size) {
System.out.println("输入值大于链表有效为节点数");
return null;
}
/**
* 有效节点数减去输入值倒序n
* 得到的n就是正序n
*
*/
n = size - n;
/**
* 代表节点的位置
*/
int i = 0;
/**
* 获取头节点
*/
Node temp = headNode;
/**
* 循环遍历节点
*/
while (true) {
/**
* i 等于 n,则得到查询的节点
*/
if (i == n) {
return temp;
}
/**
* 节点位置 + 1
*/
i++;
/**
* 节点向后移一位
*/
temp = temp.getNext();
}
}
/**
* 链表反转
*/
public void reversalHeadLinkedList() {
/**
* 判断头节点后的下一个节点是否为空，为空，说明链表没有数据
*/
if (headNode.getNext() == null) {
System.out.println("链表为空");
return;
}
/**
* 判断有效节点数是否小于3
*
* 小于3的话，则有效节点只有头节点和一个节点，无需反转了
*/
if (headNode.getNext().getNext() == null) {
System.out.println("有效节点只有2个(头节点+一个节点)，无需反转");
return;
}
/**
* 获取第一个节点
*/
Node temp = headNode.getNext();
/**
* 创建一个临时节点
*/
Node next = null;
/**
* 创建一个临时头节点
*/
Node tempHeadNode = new Node(0, null);
/**
* 循环遍历节点
*/
while (true) {
/**
* 节点为null,则链表遍历结束，退出循环
*/
if (temp == null){
break;
}
/**
* 获取下一个节点
*/
next = temp.getNext();
temp.setNext(tempHeadNode.getNext());
tempHeadNode.setNext(temp);
/**
* 下一个节点赋值
*/
temp = next;
}
/**
* 头节点的下一个节点设置为临时头节点的下一个节点，完成链表反转
*/
headNode.setNext(tempHeadNode.getNext());
}
/**
* 逆序打印
*/
public void printByReverse(){
Stack<Node> stack = new Stack<>();
Node temp = headNode.getNext();
while (true){
if (temp == null){
break;
}
stack.add(temp);
temp = temp.getNext();
}
while (stack.size() != 0){
Node node = stack.pop();
System.out.println("[编号：" + node.getNo() + "用户名：" + node.getUser().getName() + "年龄：" + node.getUser().getAge() + "]");
}
}
/**
* 两个链表合并，并有序，取出重复的
* @param headLinkedList
* @return
*/
public HeadLinkedList merge(HeadLinkedList headLinkedList){
Node temp = headNode;
Node temp2 = headLinkedList.headNode.getNext();
Node temp3 = null;
while (true){
if (temp2 == null){
break;
}
temp3 = temp2.getNext();
while (true){
if (temp.getNext() == null || temp2.getNo() < temp.getNext().getNo()){
temp2.setNext(temp.getNext());
temp.setNext(temp2);
temp = headNode;
break;
}
if (temp2.getNo() == temp.getNext().getNo()){
temp = headNode;
break;
}
temp = temp.getNext();
}
temp2 = temp3;
}
return this;
}
}
三、双向链表
1、双向节点
public class BothwayNode {
/**
* 编号
*/
private int no;
/**
* 用户
*/
private User user;
/**
* 上一个
*/
private BothwayNode last;
/**
* 下一个节点
*/
private BothwayNode next;
/**
* 构造方法
* @param no
* @param user
*/
public BothwayNode(int no, User user) {
this.no = no;
this.user = user;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public User getUser() {
return user;
}
public void setUser(User user) {
this.user = user;
}
public BothwayNode getLast() {
return last;
}
public void setLast(BothwayNode last) {
this.last = last;
}
public BothwayNode getNext() {
return next;
}
public void setNext(BothwayNode next) {
this.next = next;
}
}
2、带头节点的双向链表
public class BothwayHeadLinkedList {
private BothwayNode headBothwayNode = new BothwayNode(-1, null);
/**
* 链表末尾添加
* <p>
* 思路：
* <p>
* 循环遍历链表，得到的节点x若next为null
* <p>
* 退出循环
* <p>
* 为x节点的next赋值加入的节点y
* <p>
* 为y节点的last赋值x节点
*
* @param bothwayNode
*/
public void add(BothwayNode bothwayNode) {
/**
* 临时节点变量
*/
BothwayNode temp = headBothwayNode;
/**
* 循环
*/
while (true) {
/**
* 遍历到末尾，退出循环
*/
if (temp.getNext() == null) {
break;
}
/**
* 节点已存在
*/
if (temp.getNext().getNo() == bothwayNode.getNo()) {
throw new RuntimeException("节点已存在");
}
/**
* 节点向后移
*/
temp = temp.getNext();
}
/**
* 为next为null的temp赋值添加的节点
*/
temp.setNext(bothwayNode);
/**
* 为添加的节点的last赋值temp
*/
bothwayNode.setLast(temp);
}
/**
* 有序添加
*
* @param bothwayNode
*/
public void addByOrderly(BothwayNode bothwayNode) {
/**
* 临时节点变量
*/
BothwayNode temp = headBothwayNode;
/**
* 循环
*/
while (true) {
/**
* 遍历到末尾，退出循环
*/
if (temp.getNext() == null) {
break;
}
/**
* 节点已存在
*/
if (temp.getNext().getNo() == bothwayNode.getNo()) {
throw new RuntimeException("节点已存在");
}
/**
* 若节点的下一个节点的编号大于加入节点的编号，退出循环。节点应该添加到当前节点的next
*/
if (temp.getNext().getNo() > bothwayNode.getNo()) {
break;
}
/**
* 节点向后移
*/
temp = temp.getNext();
}
/**
* 若temp为链表最后一个节点，则直接将节点添加到末尾
*/
if (temp.getNext() == null) {
temp.setNext(bothwayNode);
bothwayNode.setLast(temp);
} else {
/**
* 修改temp中next的节点向上指向添加的节点
*/
temp.getNext().setLast(bothwayNode);
/**
* 添加的节点下一个指向temp的next节点
*/
bothwayNode.setNext(temp.getNext());
/**
* temp的next指向添加的节点
*/
temp.setNext(bothwayNode);
/**
* 添加的节点指向temp
*/
bothwayNode.setLast(temp);
}
}
/**
* 根据编号删除一个节点
*
* @param no
*/
public void delete(int no) {
/**
* 临时节点变量
*/
BothwayNode temp = headBothwayNode.getNext();
/**
* 链表为空
*/
if (temp == null) {
System.out.println("链表为空");
return;
}
/**
* 用于判断节点是否存在于链表
*/
boolean flag = false;
/**
* 循环
*/
while (true) {
/**
* 遍历到末尾，退出循环
*/
if (temp == null) {
break;
}
/**
* 节点存在，退出循环
*/
if (temp.getNo() == no) {
flag = true;
break;
}
/**
* 节点向后移
*/
temp = temp.getNext();
}
/**
* 节点存在
*/
if (flag) {
/**
* 节点的上一个节点next指向节点的下一个节点
*/
temp.getLast().setNext(temp.getNext());
/**
* 若该节点不是最后一个节点
*
* 则节点的下一个节点last指向节点的上一个节点
*/
if (temp.getNext() != null) {
temp.getNext().setLast(temp.getLast());
}
} else {
System.out.println("节点不存在");
}
}
/**
* 修改节点
*
* @param bothwayNode
*/
public void update(BothwayNode bothwayNode) {
/**
* 临时节点变量
*/
BothwayNode temp = headBothwayNode.getNext();
/**
* 链表为空
*/
if (temp == null) {
System.out.println("链表为空");
return;
}
/**
* 用于判断节点是否存在于链表
*/
boolean flag = false;
/**
* 循环
*/
while (true) {
/**
* 遍历到末尾，退出循环
*/
if (temp == null) {
break;
}
/**
* 节点存在，退出循环
*/
if (temp.getNo() == bothwayNode.getNo()) {
flag = true;
break;
}
/**
* 节点向后移
*/
temp = temp.getNext();
}
/**
* 节点存在
*/
if (flag) {
/**
* 修改节点的user属性
*/
temp.setUser(bothwayNode.getUser());
} else {
System.out.println("节点不存在");
}
}
/**
* 链表打印
*/
public void print() {
/**
* 临时节点变量
*/
BothwayNode temp = headBothwayNode.getNext();
/**
* 链表为空
*/
if (headBothwayNode.getNext() == null) {
System.out.println("链表为空...");
return;
}
/**
* 循环
*/
while (true) {
/**
* 遍历到末尾，退出循环
*/
if (temp == null) {
break;
}
/**
* 打印
*/
System.out.println("[编号：" + temp.getNo() + "用户名：" + temp.getUser().getName() + "年龄：" + temp.getUser().getAge() + "]");
/**
* 节点向后移
*/
temp = temp.getNext();
}
}
}
版权声明：本文为weixin_43521890原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。