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("豆浆"));
}
}
结果：

成都创新互联公司制作网站网页找三站合一网站制作公司,专注于网页设计,网站设计、成都网站制作,网站设计,企业网站搭建,网站开发,建网站业务,680元做网站,已为1000+服务,成都创新互联公司网站建设将一如既往的为我们的客户提供最优质的网站建设、网络营销推广服务!

馒头
茶叶蛋
麻花
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一样的效果。