数据结构之简单链表
做力扣 的算法题 突然想到这个数据结构，觉得有必要记录下来
1. 定义一个Link类和一个Node类，其中Node类为Link类的内部类（避免了反复的getter和setter方法）
Link类的目的是进行节点创建
Node类的目的是进行数据和节点链接，并且Node只能为Link调用，需要定义为private
再定义一个Factory类，用来给客户端调用，返回的是一个Link类的实例
2. Node类中需要包含有以下属性：
(1) Object data : 用于存放数据
(2) Node next : 用户存放指向下一个节点的数据
构造函数就是给data赋值
3. 增加1个追加函数，往链表中添加元素
(1) 明确的是，追加数据要在Link类中完成
(2) 需要先在Link类中声明root根节点
(3) 如果没有传入数据，那么就直接返回，不做操作
(4) 对于存放的数据，那么就要新建一个节点，新建一个节点对象，然后把这个节点对象交给Node类去处理
(5) 第4步中，存放节点数据应该从root开始，如果root为空，那么存放的数据就是root，只要把新建节点赋值给root即可
如果不是，那么就要把新建节点交由Node类处理，从root节点开始
(6) Node类接收Link类传过来的newNode对象，做以下处理：
判断root的next是否为空值，若是，则把newnode赋值给root.next
若不为空，那么递归，下个是root.next.next
以上完成增加一个数据，并处理节点关系
测试程序为：
//
public class TestLinkDemo {
public static void main(String[] args) {
Link all = Factory.getInstance();
all.add("AAA");
all.add("BBB");
all.add("CCC");
}
}
//
4. 增加一个函数，获取链表中的数据个数
(1) 在Link类中定义属性，统计个数，count
(2) 定义方法，获取count，就是返回数据个数
(3) 定义isEmpty()方法，判断链表是否为空
5. 增加一个函数，可以把链表转换成对象数组
(1) 链表就是一个动态数组，返回类型为Object[] data，每个数据的取得有先后顺序，因此需要定义一个游标
(2) Link类中，首先需要判断，链表长度是否为零，如果是零，就返回空值，如果不是0，则需要遍历整个链表，
游标为0，从root节点开始调用Node中取出数据的函数（新定义）
(3) Node类中需要获取每个节点的数据，并填写到数组中，如果判断下个节点还有数据，那么就要继续递归
6. 增加一个查询数据的方法
(1) 需要equals方法支持
(2) Node中追加一个方法，用于查找指定元素，而且必须从root节点开始往后找
(3) Link中追加一个方法，用于判断必须输入查找内容，以及链表不为空，若正常，就调用Node中的方法，从root开始
7. 根据索引取得数据
(1) 在Node类里面增加一个索引查找的方法，根据游标查找
(2) 在Link类中增加一个索引查找方法，目的是保证链表有数据，同时初始化游标，查找的时候从root节点往后找
8. 修改指定索引的数据
(1) 首先在Link类中定义一个方法，传入2个参数，第一个为索引值，第二个是要修改成的目标对象值
考虑问题，如果索引超过了链表长度，那么就不修改，结束调用
否则就先设定游标，然后从root节点开始调用Node中真正修改数据的函数
(2) Node类中定义的方法，首先判断当前游标是否为指定游标，若是，则修改数据
若不是，判断当前是不是最后一个节点，如果节点不为空，那么继续往后查找节点，递归调用
9. 删除数据
(1) 所有的前提是存在该数据，所有首先由上面定义的查找方法进行查找
如果删除的是根节点，更换root的操作只需要在Link类中完成即可
如果不是，那么要把根节点的下一个节点交给Node类中的删除方法进行
(2) Node类中判断当前对象的数据是否是要删除的数据，如果是的话，就把这个对象的上一个next指向下一个next
如果不是，则继续递归删除
更新一下查找方法，原课程写的有问题
//根据索引取得数据 public Object getNode(int searchIndex) {
if (Link.this.index++ == searchIndex) {
return this.data;
} else {
return this.next.getNode(searchIndex);
}
}
class Link {
private Node root; //根节点，增加数据函数添加
private int count; //统计元素个数
private Object[] retData; //返回对象数组
private int index = 0; //操作游标
// 定义Node内部类，表示Node只为Link类服务
private class Node { //负责 保存数据，节点关系配置
private Object data;
private Node next;
public Node(Object data) {
this.data = data;
}
//增加数据
public void addNode(Node newNode) {
if (this.next == null) {
this.next = newNode;
} else {
this.next.addNode(newNode);
}
}
//转换成对象数组
public void toArrayNode() {
Link.this.retData[Link.this.index ++] = this.data;//先把root节点的数据取出，然后游标加一
if (this.next != null){ //如果下个节点还有数据，则递归获取
this.next.toArrayNode();
}
}
//查找数据
public boolean containsNode(Object search) {
if (search.equals(this.data)) {
return true; //找到数据
} else {
if (this.next != null) { //还有后续节点
return this.next.containsNode(search);//递归查找
} else {
return false;
}
}
}
//根据索引取得数据
public Object getNode(int searchIndex) {
if (Link.this.index ++ == searchIndex) {
return this.data;
} else {
this.next.getNode(searchIndex);
}
return null;
}
//修改指定索引的数据
public void setNode(int searchIndex, Object newData) {
if (Link.this.index ++ == searchIndex) {
this.data = newData;
} else {
if (this.next != null) {
this.next.setNode(searchIndex,newData);
}
}
}
//删除元素
public void removeDataNode(Node previous, Object data) {
if (this.data.equals(data)) {
previous.next = this.next; //中间是this，如果this的data是所要删除的data，那么把this之前的一个node指向this之后的一个node
} else {
this.next.removeDataNode(this, data);
}
}
}
// ---------以下是Link类定义-----------
//增加元素
public void add(Object data) {
if ( data == null ) {//不允许存放空值数据
return;
}
Node newNode = new Node(data); //创建一个新的节点
if (this.root == null) {
this.root = newNode;
} else {
this.root.addNode(newNode);
}
this.count ++;
}
//获取链表大小
public int size() {
return this.count;
}
//判断链表是否为空
public boolean isEmpty() {
if (this.root == null && this.count == 0 ) {
return false;
} else {
return true;
}
}
//链表转换成对象数组
public Object[] toArray() {
if (this.count == 0) { //如果链表没有数据，那么就返回null
return null;
}
this.retData = new Object[this.count];//如果count不为零，那么开辟指定空间的对象数组
this.index = 0;//游标初始化为0
this.root.toArrayNode();//交给Node类进行数据的取出
return this.retData;//返回对象数组
}
//查找数据
public boolean contains(Object search) {
if (search == null || this.root == null) {
return false;
}
return this.root.containsNode(search);
}
//根据索引取得数据
public Object get(int searchIndex) {
if (searchIndex >= this.count) {
return null;
}
this.index = 0;
return this.root.getNode(searchIndex);
}
//修改指定索引的数据
public void setData(int searchIndex, Object newData) {
if (searchIndex >= this.count) {
return ;
} else {
this.index = 0;
this.root.setNode(searchIndex, newData);
}
}
//删除数据
public void removeData(Object data) {
if (this.contains(data)) {
if (this.root.data.equals(data)) {
this.root = this.root.next;
} else {
this.root.next.removeDataNode(this.root, data);
}
this.count --;
}
}
}
class Factory {
public static Link getInstance() {
return new Link();
}
}
public class TestLinkDemo {
public static void main(String[] args) {
Link all = Factory.getInstance();
//
all.add("AAA");
all.add("BBB");
all.add("CCC");
//
System.out.println("链表大小为： " + all.size());
//
Object[] result = all.toArray();
System.out.println("链表转换成对象数组并输出: ");
for ( Object x : result ) {
System.out.println(x);
}
//查询数据方法
System.out.println("查询数据方法: ");
System.out.println(all.contains("AAA"));
System.out.println(all.contains("D"));
//取得索引数据
System.out.println("查找索引为0的数据: ");
System.out.println(all.get(0));
System.out.println("查找索引为3的数据: ");
System.out.println(all.get(3));
//修改索引数据
System.out.println("修改索引数据: ");
all.setData(0,"DDD");
Object[] result1 = all.toArray();
System.out.println("修改索引数据并输出: ");
for ( Object x : result1 ) {
System.out.println(x);
}
//删除数据
System.out.println("删除数据: ");
all.removeData("BBB");
Object[] result2 = all.toArray();
System.out.println("删除数据并输出: ");
for ( Object x : result2 ) {
System.out.println(x);
}
}
}
测试结果：
以上是 数据结构之简单链表 的全部内容， 来源链接： utcz.com/z/510475.html
