数据结构之线性表的链式存储（Java表示）
程序员文章站
2022-06-03 18:31:45
...
目录
线性表的链式存储
一些基本概念
- 数据域：在链表中用来存放数值。
- 链接域：在链表中用来存放指针的，用一带箭头的线段表示。
主要操作实现
1. 求表长
- 时间复杂度：O(n)
- 求表长的思路
顺序表由于存储是连续的，求表长就是Last+1。但是链式存储表中，存储不是连续的，所以需要将链表从头到尾遍历一遍：设定一个移动指针p和计数器cnt，初始化后，p从表的第一个节点开始向后逐步向后移，同时计数器cnt加1，当后面不再有节点时，cnt的值就是节点个数也就是表长。
2. 查找
- （1）按序号查找：FindKth
- 时间复杂度：O(n)
- 按序号查找的思路
顺序表的按序号查找要得到第K个元素的值就是list[K-1]。但是链式存储表中需要：从链表的第一个元素节点开始，判断当前节点是否是第K个，如果是则返回该节点的值，否则继续下一个，直到表结束为止，如果没有第K个节点则返回错误信息。
- （2）按值查找：Find
- 时间复杂度：O(n)
- 按值查找的思路
按值查找也是从头到尾的遍历，直到找到为止：从链表的第一个元素节点开始，判断其当前节点的值是否等于要查找的值X，如果是则返回该节点的位置否则继续下一个直到表结束为止。找不到则返回错误信息。
3. 插入
- 平均查找次数：n/2
- 时间复杂度：O(n)
- 插入的说明
线性表的插入是在指定位序i（1<=i<=n+1）前插入一个新元素X。当前插入位序为1时，代表插入到链表的头；i为n+1时表示插入到链表的最后 - 插入的思路
基本思路是如果i不为1则找到位序为i-1的节点pre；若存在则申请一个新节点并在数据域上填上相应值X，如果将新节点插入到节点pre后，返回结果链表；如果不存在则返回错误信息。
4. 删除
- 平均查找次数：n/2
- 时间复杂度：O(n)
- 删除的思路
在单向链表中删除指定位序i的元素，首先要找到被删除节点的前一个元素，然后再删除节点并释放空间。
5. 小结
在单链表上插入、删除一个节点，必须知道其前驱节点。
单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。
Java代码实现
Node.java
public class Node {
private Object data;
private Node next;
public Node(){
super();
}
public Node(Object data,Node next){
super();
this.data=data;
this.next=next;
}
public Node(Object data){
super();
this.data=data;
}
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;
}
}
MyLinearList.java
/**
* 线性表链式存储常用操作集实现
*
* @author lck100
*/
public class MyLinearList {
private MyLinearList() {
super();
}
/**
* 获取表长
*
* @return 返回链表长度
*/
private int length(Node sourceNode) {
// node指向表的第一个结点
Node node = sourceNode;
// 计数器，用来统计链表结点个数，初始为0个
int j = 0;
// 结点为null时表示没有下一个结点了，跳出循环，返回链表长度
while (node != null) {
// 当前node指向第j个结点
node = node.getNext();
j++;
}
return j;
}
/**
* 按序号查找值
*
* @param i 查找的序号
* @param sourceNode 当前要操作的链表
* @return 如果查找成功返回该结点，否则返回null
*/
private Node findKth(int i, Node sourceNode) {
Node node = sourceNode;
// 计数器，统计当前是第几个结点
int j = 1;
// 循环的条件是结点不能为null并且j必须小于i
while (node != null && j < i) {
node = node.getNext();
j++;
}
// 判断计数器的值是否等于要查询的位序，如果是返回结点否则返回null
if (j == i) {
return node;
} else {
return null;
}
}
/**
* 按值查找
*
* @param obj 要查找的值
* @param sourceNode 要操作的链表
* @return 如果查找成功返回该值所在结点
*/
private Node find(Object obj, Node sourceNode) {
Node node = sourceNode;
// 循环判断结点的值是否与要查询的值相等，相等则返回当前结点
while (node != null && node.getData() != obj) {
node = node.getNext();
}
return node;
}
/**
* 在指定位置插入
*
* @param i 要插入的位序
* @param data 要插入的数据
* @param sourceNode 要操作的链表
* @return 返回插入成功的链表
* @throws Exception 抛出异常
*/
private Node insert(int i, Object data, Node sourceNode) throws Exception {
// p指的是要插入的位置之前的结点，s指的是要新插入的结点
Node p, s;
// 如果新结点要插在表头
if (i == 1) {
// 申请新结点
s = new Node();
// 设置新结点的数据
s.setData(data);
// 设置新节点的指针（下一个结点）的位置
s.setNext(sourceNode);
return s;
}
// 查找第(i-1)个结点，即查找要插入的位置的前一个结点
p = findKth(i - 1, sourceNode);
// 判断查询到的结点是否为null
if (p == null) {
throw new Exception("参数i错误！");
} else {
// 申请新结点
s = new Node();
// 设置新结点的数据
s.setData(data);
// 设置新结点的指针（下一个结点的位置）为查询到的结点的指针
s.setNext(p.getNext());
// 将要插入位置的前一个结点的指针指向当前要添加的新结点
p.setNext(s);
return sourceNode;
}
}
/**
* 删除指定位置的数据
*
* @param i 指定的位序
* @param sourceNode 链表
* @return 返回删除成功的链表
* @throws Exception 抛出异常
*/
private Node delete(int i, Node sourceNode) throws Exception {
// p指的是要删除的结点之前的结点，s指的是要删除的结点
Node p, s;
// 如果要删除第一个结点
if (i == 1) {
s = sourceNode;
if (sourceNode != null) {
// 从链表中删除，即指针指向了第一个结点的下一个结点
sourceNode = sourceNode.getNext();
} else {
return null;
}
return sourceNode;
}
// 查询要删除结点的上一个节点
p = findKth(i - 1, sourceNode);
if (p == null) {
throw new Exception("第" + (i - 1) + "个结点不存在！");
} else if (p.getNext() == null) {
throw new Exception("第" + i + "个结点不存在！");
} else {
// 将s指向第i个结点，即获取要删除的节点（通过上一个节点的指针获取要删除的节点的位置）
s = p.getNext();
// 从链表中删除
p.setNext(s.getNext());
return sourceNode;
}
}
/**
* 打印该链表的所有结点数据
*
* @param node 链表
*/
private void print(Node node) {
while (node != null) {
System.out.print(node.getData() + "\t");
node = node.getNext();
}
System.out.println();
}
public static void main(String[] args) throws Exception {
MyLinearList linearList = new MyLinearList();
// 作头结点使用
Node head = new Node("唐僧", null);
// 插入一个结点，位序是1
Node insert1 = linearList.insert(1, "孙悟空", head);
linearList.print(insert1);
// 插入一个结点，位序非1
Node insert2 = linearList.insert(2, "猪八戒", insert1);
linearList.print(insert2);
// 打印链表的长度
System.out.println(linearList.length(insert2));
// 按序号查找
Node kth = linearList.findKth(2, insert2);
System.out.println(kth.getData());
// 按值查找
Node find = linearList.find("唐僧", insert2);
System.out.println(find.getData());
// 删除指定位序的结点，比如删除第二个结点
Node delete = linearList.delete(2, insert2);
linearList.print(delete);
}
}
控制台打印：
把上面的代码整理了一下，代码如下：
/**
* 线性表链式存储常用操作集实现
*
* @author lck100
*/
public class MyLinearList2 {
private Node source = new Node();
private int size = 0;// 计数器，统计链表中结点的个数
private MyLinearList2() {
super();
}
/**
* 获取表长
*
* @return 返回链表长度
*/
private int length() {
return size;
}
/**
* 按序号查找值
*
* @param i 查找的序号
* @return 如果查找成功返回该结点，否则返回null
*/
private Node findKth(int i) {
Node node = source;
// 计数器，统计当前是第几个结点
int j = 1;
// 循环的条件是结点不能为null并且j必须小于i
while (node != null && j < i) {
node = node.getNext();
j++;
}
// 判断计数器的值是否等于要查询的位序，如果是返回结点否则返回null
if (j == i) {
return node;
} else {
return null;
}
}
/**
* 按值查找
*
* @param obj 要查找的值
* @return 如果查找成功返回该值所在结点
*/
private Node find(Object obj) {
Node node = source;
// 循环判断结点的值是否与要查询的值相等，相等则返回当前结点
while (node != null && node.getData() != obj) {
node = node.getNext();
}
return node;
}
/**
* 在指定位置插入
*
* @param i 要插入的位序
* @param data 要插入的数据
* @return 返回插入成功的链表
* @throws Exception 抛出异常
*/
private Node insert(int i, Object data) throws Exception {
// p指的是要插入的位置之前的结点，s指的是要新插入的结点
Node p, s;
// 如果新结点要插在表头
if (i == 1) {
// 申请新结点
s = new Node();
// 设置新结点的数据
s.setData(data);
// 处理第一个结点问题
if (size == 0) {
// 设置新节点的指针（下一个结点）的位置
s.setNext(null);
} else {
// 设置新节点的指针（下一个结点）的位置
s.setNext(source);
}
source = s;
size++;
return s;
}
// 查找第(i-1)个结点，即查找要插入的位置的前一个结点
p = findKth(i - 1);
// 判断查询到的结点是否为null
if (p == null) {
throw new Exception("参数i错误！");
} else {
// 申请新结点
s = new Node();
// 设置新结点的数据
s.setData(data);
// 设置新结点的指针（下一个结点的位置）为查询到的结点的指针
s.setNext(p.getNext());
// 将要插入位置的前一个结点的指针指向当前要添加的新结点
p.setNext(s);
size++;
return source;
}
}
/**
* 删除指定位置的数据
*
* @param i 指定的位序
* @return 返回删除成功的链表
* @throws Exception 抛出异常
*/
private Node delete(int i) throws Exception {
// p指的是要删除的结点之前的结点，s指的是要删除的结点
Node p, s;
// 如果要删除第一个结点
if (i == 1) {
s = source;
if (source != null) {
// 从链表中删除，即指针指向了第一个结点的下一个结点
size--;
source = source.getNext();
} else {
return null;
}
return source;
}
// 查询要删除结点的上一个节点
p = findKth(i - 1);
if (p == null) {
throw new Exception("第" + (i - 1) + "个结点不存在！");
} else if (p.getNext() == null) {
throw new Exception("第" + i + "个结点不存在！");
} else {
// 将s指向第i个结点，即获取要删除的节点（通过上一个节点的指针获取要删除的节点的位置）
s = p.getNext();
// 从链表中删除
p.setNext(s.getNext());
size--;
return source;
}
}
/**
* 打印该链表的所有结点数据
*/
private void print() {
Node node = source;
while (node != null) {
System.out.print(node.getData() + "\t");
node = node.getNext();
}
System.out.println();
}
public static void main(String[] args) throws Exception {
MyLinearList2 linearList = new MyLinearList2();
linearList.insert(1,"唐僧");
linearList.print();
System.out.println(linearList.length());
linearList.insert(2,"孙悟空");
linearList.insert(3,"猪八戒");
linearList.print();
System.out.println(linearList.length());
linearList.insert(1,"沙僧");
linearList.insert(2,"小白龙");
linearList.print();
linearList.delete(2);
linearList.print();
linearList.delete(4);
linearList.print();
Node node = linearList.find("孙悟空");
System.out.println(node.getData());
Node kth = linearList.findKth(2);
System.out.println(kth.getData());
}
}
控制台打印如下：
上一篇： 数据结构之队列的链式存储（Java表示）
下一篇： 指针函数与函数指针的区别