【数据结构】——链表(链式存储和基于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元起，快前往官网查看详情吧