【数据结构】——链表(链式存储和基于Java的运算实现)-创新互联
**概述：**从链表的开始结点出发，顺链逐个将结点的值和给定的值k进行比较，若遇到相等的值，则返回该结点的储存位置，否则返回NULL。时间复杂度：O(n)
站在用户的角度思考问题，与客户深入沟通，找到安福网站设计与安福网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：成都做网站、网站建设、企业官网、英文网站、手机端网站、网站推广、国际域名空间、网页空间、企业邮箱。业务覆盖安福地区。
插入运算
**概述：**先使p指向a(i-1)的位置，然后生成一个数据域值为x的新结点*s，再进行插入操作。
图解：
**时间复杂度：**O(n)
删除运算
**概述：**先使p指向第i-1个结点，然后再使得p—>next指向第i+1个结点，再将第i个结点释放掉。
图解：
**时间复杂度：**O(n)
代码实现
一、结点类
//链表结点类
public class Node {
//数据域
private Object data;
//指针域
private Node next;
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) {
//创建结点值
Node n1 = new Node("qq", null);
Node n2 = new Node("ww", null);
Node n3 = new Node("ee", null);
Node n4 = new Node("rr", null);
//头插法
SingleLinkedList.CreateListF(n1);
SingleLinkedList.CreateListF(n2);
SingleLinkedList.CreateListF(n3);
SingleLinkedList.CreateListF(n4);
System.out.println(SingleLinkedList.linkList);
}
}
运行结果：
4.1.2 尾插法建表
public class SingleLinkedListTest {
public static void main(String[] args) {
//创建结点值
Node n1 = new Node("qq", null);
Node n2 = new Node("ww", null);
Node n3 = new Node("ee", null);
Node n4 = new Node("rr", null);
//尾插法
SingleLinkedList.CreateListR(n1);
SingleLinkedList.CreateListR(n2);
SingleLinkedList.CreateListR(n3);
SingleLinkedList.CreateListR(n4);
System.out.println(SingleLinkedList.linkList);
}
}
运行结果：
4.2 基本操作测试
**说明：**上边使用的头插法和尾插法是为了创建链表，只需要选择其中的一种创建方式即可。尾插法创建出来的链表跟我们插入的顺序是一样的，更符合实际，为了测试时方便查验，下边对链表的测试都是基于尾插法建立的表进行测试的。
public class SingleLinkedListTest {
public static void main(String[] args) {
//创建结点值
Node n1 = new Node("qq", null);
Node n2 = new Node("ww", null);
Node n3 = new Node("ee", null);
Node n4 = new Node("rr", null);
//尾插法
SingleLinkedList.CreateListR(n1);
SingleLinkedList.CreateListR(n2);
SingleLinkedList.CreateListR(n3);
SingleLinkedList.CreateListR(n4);
System.out.println(SingleLinkedList.linkList);
System.out.println("---------------------------------");
//遍历
System.out.println("链表元素遍历为：");
SingleLinkedList.ListShow();
System.out.println("---------------------------------");
//查找：按结点序号
Node node = SingleLinkedList.GetNodeI(1);
System.out.println("结点序号为1的元素值为：" + node.getData());
System.out.println("---------------------------------");
//查找：按结点值查找
Node node1 = SingleLinkedList.GetNodeK("ww");
System.out.println("元素值是‘ww’的结点为：" + node1);
System.out.println("---------------------------------");
}
}
运行结果：
4.3 插入删除测试
public class SingleLinkedListTest {
public static void main(String[] args) {
//创建结点值
Node n1 = new Node("qq", null);
Node n2 = new Node("ww", null);
Node n3 = new Node("ee", null);
Node n4 = new Node("rr", null);
//尾插法
SingleLinkedList.CreateListR(n1);
SingleLinkedList.CreateListR(n2);
SingleLinkedList.CreateListR(n3);
SingleLinkedList.CreateListR(n4);
System.out.println(Singl
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jBij6bZk-1669875451789)(https://mmbiz.qpic.cn/mmbiz_png/nMicohCxH9r2BPjylgQTOxQFBMTBcucNMZpohd3FpUkGsDf2wzGZa3cjx7icEg6dCMg15vGibA9Q8C21s6CdL6K0g/0?wx_fmt=png)]
eLinkedList.linkList);
System.out.println("---------------------------------");
//插入
SingleLinkedList.InsertList(3, "66");
//遍历
System.out.println("插入结点之后遍历链表为：");
SingleLinkedList.ListShow();
System.out.println("---------------------------------");
//删除
Object o = SingleLinkedList.DeleteList(4);
System.out.println("被删除的元素值为："+o);
//遍历
System.out.println("删除结点之后遍历链表为：");
SingleLinkedList.ListShow();
System.out.println("---------------------------------");
}
}
运行结果：
循环链表
");
//遍历
System.out.println("插入结点之后遍历链表为：");
SingleLinkedList.ListShow();
System.out.println("---------------------------------");
//删除
Object o = SingleLinkedList.DeleteList(4);
System.out.println("被删除的元素值为："+o);
//遍历
System.out.println("删除结点之后遍历链表为：");
SingleLinkedList.ListShow();
System.out.println("---------------------------------");
}
}
运行结果：
循环链表
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前文章：【数据结构】——链表(链式存储和基于Java的运算实现)-创新互联
URL分享：http://pwwzsj.com/article/gpdse.html
