【数据结构】——链表 (链式存储和基于Java的运算实现)_插入排序链式存储java

public Node() {

}

public Node(Object data, Node next) {

this.data = data;

this.next = next;

}

public Object getData() {

return data;

}

public void setData(Object data) {

this.data = data;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

@Override

public String toString() {

return “\nNode{” +

“data=” + data +

“, next=” + next +

‘}’;

}

}

二、链表类

//链表类

public class LinkList {

//头结点

Node head;

//链表长度

int size;

//构造方法

public LinkList() {

head = null;

size = 0;

}

@Override

public String toString() {

return “LinkList{” +

“head=” + head +

“, size=” + size +

‘}’;

}

}

三、操作类

//操作类

public class SingleLinkedList {

//定义一个单链表

static LinkList linkList = new LinkList();

//定义一个尾指针

static Node rear = linkList.head;

//头插法建表

public static void CreateListF(Node node) {

//申请新结点

Node n = new Node();

//数据域赋值

n.setData(node.getData());

//指针域赋值

n.setNext(linkList.head);

//头指针指向新结点

linkList.head = n;

//链表长度加1

linkList.size++;

}

//尾插法建表

public static void CreateListR(Node node) {

//申请新结点

Node n = new Node();

//数据域赋值

n.setData(node.getData());

//判断链表是否为null，并插入新结点

if (linkList.head == null) {

linkList.head = n;

} else rear.setNext(n);

//尾指针指向新结点

rear = n;

//终端结点指针域置空

if (rear.getNext() != null)

rear.setNext(null);

//链表长度加1

linkList.size++;

}

//遍历

public static void ListShow() {

//定义一个新结点，用于循环赋值显示

Node n = linkList.head;

//循环链表

for (int i = 0; i < linkList.size; i++) {

//输出新结点的数据值

System.out.println(n.getData());

//新结点指向下一个结点

n = n.getNext();

}

}

//查找：按结点序号查找,返回该结点

public static Node GetNodeI(int i) {

//判断查找的序号是否合法

if (i <= 0 || i > linkList.size) {

System.out.println(“position error!”);

}

//定义一个新结点并赋值

Node n = linkList.head;

//序号无负数，从1开始

for (int j = 1; j <= linkList.size; j++) {

if (i == j) {

break;

}

//新结点指向下一个结点

n = n.getNext();

}

return n;

}

//查找：按结点值查找,参数为结点值

public static Node GetNodeK(Object n) {

//判断链表是否为空

if (linkList.size == 0) {

System.out.println(“LinkList is null!”);

}

//判断结点值是否与头结点相等

if (n == linkList.head.getData()) {

return linkList.head;

}

//定义一个新结点并赋值

Node newNode = linkList.head;

while (linkList.size > 0) {

if (newNode.getData() == n) {

return newNode;

}

//新结点指向下一个结点

newNode = newNode.getNext();

linkList.size–;

}

return null;

}

//插入：将值为x的新结点插入到第i个结点的位置上

public static void InsertList(int i, Object x) {

//判断插入的位置是否合法

if (i <= 0 || i > linkList.size) {

System.out.println(“position error!”);

}

//链表长度加1

linkList.size++;

int k = 1;

//创建新结点并赋值

Node p = linkList.head;

//使p指向i-1个结点

while (p != null && k < i - 1) {

p = p.getNext();

k++;

}

//申请一个新结点

Node newNode = new Node();

//数据域赋值

newNode.setData(x);

//指针域赋值

newNode.setNext(p.getNext());

//i-1个结点指向新节点

p.setNext(newNode);

}

//删除：将链表中的第i个结点删除,并返回该值

public static Object DeleteList(int i) {

//判断要删除的位置是否合法

if (i <= 0 || i > linkList.size) {

System.out.println(“position error!”);

}

int n = 1;

//创建新结点并赋值

Node p = linkList.head;

//使p指向i-1个结点

while (p != null && n < i - 1) {

p = p.getNext();

n++;

}

//定义一个新结点,指向第i个结点

Node s = p.getNext();

//使p的下一个结点指向i+1个结点

p.setNext(s.getNext());

//保存被删除结点的值

Object x = s.getData();

linkList.size–;

return x;

}

}

四、测试类

4.1 建立单链表测试

4.1.1 头插法建表

public class SingleLinkedListTest {

public static void main(String[] args) {
1

    //创建结点值
1

    Node n1 = new Node("qq", null);
1

    Node n2 = new Node("ww", null);
1

    Node n3 = new Node("ee", null);
1

    Node n4 = new Node("rr", null);
1

    //头插法
1

    SingleLinkedList.CreateListF(n1);
1

    SingleLinkedList.CreateListF(n2);
1

    SingleLinkedList.CreateListF(n3);
1

    SingleLinkedList.CreateListF(n4);
1

    System.out.println(SingleLinkedList.linkList);
1

}
1

}

运行结果：

4.1.2 尾插法建表

public class SingleLinkedListTest {

public static void main(String[] args) {
1

    //创建结点值
1

    Node n1 = new Node("qq", null);
1

    Node n2 = new Node("ww", null);
1

    Node n3 = new Node("ee", null);
1

    Node n4 = new Node("rr", null);
1

    //尾插法
1

    SingleLinkedList.CreateListR(n1);
1

    SingleLinkedList.CreateListR(n2);
1

    SingleLinkedList.CreateListR(n3);
1

    SingleLinkedList.CreateListR(n4);
1

    System.out.println(SingleLinkedList.linkList);
1

}
1

}

运行结果：

4.2 基本操作测试

**说明：**上边使用的头插法和尾插法是为了创建链表，只需要选择其中的一种创建方式即可。尾插法创建出来的链表跟我们插入的顺序是一样的，更符合实际，为了测试时方便查验，下边对链表的测试都是基于尾插法建立的表进行测试的。

public class SingleLinkedListTest {

public static void main(String[] args) {
1

    //创建结点值
1

    Node n1 = new Node("qq", null);
1

    Node n2 = new Node("ww", null);
1

    Node n3 = new Node("ee", null);
1

    Node n4 = new Node("rr", null);
1

    //尾插法
1

    SingleLinkedList.CreateListR(n1);
1

    SingleLinkedList.CreateListR(n2);
1

    SingleLinkedList.CreateListR(n3);
1

    SingleLinkedList.CreateListR(n4);
1

    System.out.println(SingleLinkedList.linkList);
1

    System.out.println("---------------------------------");
1

    //遍历
1

    System.out.println("链表元素遍历为：");
1

    SingleLinkedList.ListShow();
1

    System.out.println("---------------------------------");
1

    //查找：按结点序号
1

    Node node = SingleLinkedList.GetNodeI(1);
1

    System.out.println("结点序号为1的元素值为：" + node.getData());
1

    System.out.println("---------------------------------");
1

    //查找：按结点值查找
1

    Node node1 = SingleLinkedList.GetNodeK("ww");
1

    System.out.println("元素值是‘ww’的结点为：" + node1);
1

    System.out.println("---------------------------------");
1

}
1

}

运行结果：

4.3 插入删除测试

public class SingleLinkedListTest {

public static void main(String[] args) {
1

    //创建结点值
1

    Node n1 = new Node("qq", null);
1

    Node n2 = new Node("ww", null);
1

    Node n3 = new Node("ee", null);
1

    Node n4 = new Node("rr", null);
1

    //尾插法
1

    SingleLinkedList.CreateListR(n1);
1

    SingleLinkedList.CreateListR(n2);
1

    SingleLinkedList.CreateListR(n3);
1

    SingleLinkedList.CreateListR(n4);
1

    System.out.println(SingleLinkedList.linkList);
1

    System.out.println("---------------------------------");
1

    //插入
1

    SingleLinkedList.InsertList(3, "66");
1

    //遍历
1

    System.out.println("插入结点之后遍历链表为：");
1

    SingleLinkedList.ListShow();
1

    System.out.println("---------------------------------");
1

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！

如果你觉得这些内容对你有帮助，可以扫码获取！！（备注Java获取）

最后的话

无论是哪家公司，都很重视Spring框架技术，重视基础，所以千万别小看任何知识。面试是一个双向选择的过程，不要抱着畏惧的心态去面试，不利于自己的发挥。
同时看中的应该不止薪资，还要看你是不是真的喜欢这家公司，好了希望这篇文章对大家有帮助！

部分截图：

《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取！
nmdTHgFj-1713420667713)]

[外链图片转存中…(img-IafrH9uM-1713420667713)]

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！

如果你觉得这些内容对你有帮助，可以扫码获取！！（备注Java获取）

最后的话

无论是哪家公司，都很重视Spring框架技术，重视基础，所以千万别小看任何知识。面试是一个双向选择的过程，不要抱着畏惧的心态去面试，不利于自己的发挥。
同时看中的应该不止薪资，还要看你是不是真的喜欢这家公司，好了希望这篇文章对大家有帮助！

部分截图：
[外链图片转存中…(img-84MZgdrX-1713420667713)]

《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取！