Java 实现自定义链表

Java 实现自定义链表
节点类 Node.java
操作功能类 Link.java
App.java
节点类 Node.java
public class Node {
/ 当前节点的数据*/
private String data;
/* 如果当前节点是首/尾节点 NULL 或者是 下一个节点的实例/
private Node next;
public Node(final String data) {
this.data = data;
}
public void setNext(final Node next) {
this.next = next;
}
public Node getNext() {
return this.next;
}
public String getData() {
return this.data;
}
public void addNode(final Node newNode) {
if (this.next == null) {
this.next = newNode;
} else {
this.next.addNode(newNode);
}
}
public void printNode() {
System.out.println(this.data);
if (this.next != null) {
this.next.printNode();
}
}
public boolean containNode(final String data) {
/ 比对当前节点数据是否相同*/
if (this.data.equals(data)) {
return true;
} else {
if (this.next != null) {
return this.next.containNode(data);
} else {
return false;
}
}
}
public void removeNode(final Node previous, final String data) {
/ 比对当前节点数据是否和将要删除的数据相同*/
if (this.data.equals(data)) {
/* 数据相同的前提下 把下一个节点覆盖到上一个节点的 next/
previous.next = this.next;
} else {
this.next.removeNode(this, data);
}
}
}
操作功能类 Link.java
public class Link {
private Node root;
public void add(final String data) {
if (data == null || this.contains(data)) {
return;
}
Node newNode = new Node(data);
if (this.root == null) {
this.root = newNode;
} else {
this.root.addNode(newNode);
}
}
public void print() {
if (this.root != null) {
this.root.printNode();
}
}
public boolean contains(final String data) {
if (data == null || this.root == null) {
return false;
}
return this.root.containNode(data);
}
public void remove(final String data) {
/ 1. 首先判断是否有相同数据节点*/
if (this.contains(data)) {
/ 2. 将要删除的数据和当前根节点数据节点相同的话 把下一个节点覆盖到根节点*/
if (this.root.getData().equals(data)) {
this.root = this.root.getNext();
} else {
/* 通过当前根节点和将要删除的数据, 删除节点/
this.root.getNext().removeNode(this.root , data);
}
}
}
}
App.java
public class App {
public static void main(String[] args) {
final Link list = new Link();
list.add("馒头");
list.add("豆浆");
list.add("茶叶蛋");
list.add("包子");
list.add("麻花");
list.add("豆浆");
/ 删除*/
list.remove("包子");
list.remove("豆浆");
/* 打印/
list.print();
/* 查询/
System.out.println(list.contains("馒头"));
System.out.println(list.contains("豆浆"));
}
}
结果：

馒头
茶叶蛋
麻花
true
false
1.入门级
首先实现一个节点类：
package jimo.love;
public class Node {
private String data;//数据
private Node next;//指向下一个节点
public Node(String data){
this.data = data;
}
public void setNext(Node next){
this.next = next;
}
public Node getNext(){
return this.next;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
}
然后在主方法中生成节点，完成连接关系，并打印出来，看代码有解释：
package jimo.love;
public class Test {
public static void main(String[] args) {
//1.准备所有数据
Node head = new Node("头节点");
Node n1 = new Node("n1");
Node n2 = new Node("n2");
head.setNext(n1);
n1.setNext(n2);
//2.取出所有数据
//方法一：
Node curNode = head;
while(curNode!=null){
System.out.println(curNode.getData());
curNode = curNode.getNext();
}
//方法二,递归方式：
print(head);
}
//采用递归方式
public static void print(Node curNode){
if(curNode==null){
return ;
}
System.out.println(curNode.getData());
print(curNode.getNext());
}
}
代码中用了两种方式取数据，看执行结果：
1
可以看到Main方法里写的东西太多了，还要设置数据，输出数据。
但面向对象的思想让我们不需要关注太多的东西和具体的实现。
所以我们需要ThinkMarkets返佣www.kaifx.cn/broker/thinkmarkets.html一个工具类，我们只关注存数据和取数据，并不关心怎么存，怎么取。
2.中级
我们增加一个Link类用于业务操作：
public class Link {
private Node head;
public void add(String data){
Node newNode = new Node(data);
if(this.head==null){
this.head = newNode;//头节点
}else{
//头插法
// newNode.setNext(this.head.getNext());
// this.head.setNext(newNode);
//尾插法
this.head.addNode(newNode);
}
}
public void print(){
if(this.head!=null){
this.head.printNode();
}
}
}
其中的addNode和printNode方法来自Node类：
//递归添加节点
public void addNode(Node node){
if(this.next==null){
this.next = node;
}else{
this.next.addNode(node);
}
}
//递归打印节点
public void printNode(){
System.out.println(this.data);
if(this.next!=null){
this.next.printNode();
}
}
在主函数里：
Link link = new Link();
link.add("1");
link.add("2");
link.add("3");
link.print();
3.高级
在可用链表中，你不可能直接操作节点类吧,像这样：
Node n = new Node("n");
所以，我们要让Node类只能被Link类使用，具体方法是将Node类声明为Link类的私有内部类：
4.终极
一个链表不可能只有一个add方法吧，接下来就完善方法：
1.size():取得元素个数
在Link类中声明属性count：
private int count = 0;
在add函数里自加：
this.count++;//增加完就++
返回size：
//取得数量
public int size(){
return this.count;
}
测试：
Link link = new Link();
link.add("1");
link.add("2");
link.add("3");
link.add(null);
System.out.println(link.size());
可以看到我添加了一个null元素，但也添加进去了，添不添加取决于自己4，我这里不让添加，所以在add函数里修改：
if(null==data){
return ;
}
2.isEmpty():判断链表是否为空：
public boolean isEmpty(){
return 0==this.count;
}
3.contains(data):判断数据是否存在：
在Link类中：
//根据内容查询数据
public boolean contains(String data){
if(null==data||null==this.head){
return false;
}else{
return this.head.containNode(data);
}
}
在Node类中：
public boolean containNode(String data){
if(data.equals(this.data)){
return true;
}else{
if(null!=this.next){
return this.next.containNode(data);
}else{
return false;//递归结束条件
}
}
}
4.get(int index):根据索引查找数据：
在Link类添加属性：
private int index = 0;
1
在Node类添加方法：
public String getNode(int index){
//注意Link.this.index
if(Link.this.index++==index){
return this.data;
}else{
return this.next.getNode(index);
}
}
注意：Link.this.index是内部类获得外部类属性的方法。
在Link类添加方法：
//通过索引查找内容
public String get(int index){
if(index >= this.count){
return null;
}
this.index = 0;//每次从头向后查询
return this.head.getNode(index);
}
注意：查找时索引从0开始，当然可以改成从1开始。
5.set(int index,data):根据索引修改内容：
其实和查找一样，只是操作不同方而已：
在Node类：
public void setNode(int index,String data){
if(Link.this.index++==index){
this.data = data;
}else{
this.next.setNode(index, data);
}
}
在Link类：
//根据索引修改内容
public void set(int index,String data){
if(index >= this.count){
return ;
}else{
this.head.setNode(index,data);
}
}
6.remove(data)：删除一个元素：
这也是相对来说最复杂的部分，不过也很简单。
在Node类：
//对非根节点的删除
public void removeNode(Node preNode,String data){
if(data.equals(this.data)){
preNode.next = this.next;
}else{
this.next.removeNode(this, data);
}
}
在Link类，要判断是否是根节点：
//删除
public void remove(String data){
if(this.contains(data)){
//删除根节点
if(data.equals(this.head.data)){
this.head = this.head.next;
}else{ //非根节点
this.head.next.removeNode(this.head, data);
}
this.count--;//别忘了
}
}
7.toArray():转化成数组：
在Link类添加一个属性：private String[] retArray;
在Node类：
public void toArrayNode(){
Link.this.retArray[Link.this.index++] = this.data;
if(null!=this.next){
this.next.toArrayNode();
}
}
在Link类：
public String[] toArray(){
if(null == this.head){
return null;
}
this.index = 0;
this.retArray = new String[this.count];
this.head.toArrayNode();
return this.retArray;
}
5.总结
以上代码不能够用于实战开发，只是为了理解引用关系的传递，后续的改进可以添加更多的方法，不用递归，加入泛型，做出和List一样的效果。