Java实现简单的链表-面向初学者

很久之前用C语言实现过链表，现在已经太久没用C语言。就先用JAVA实现一个简单链表好了，还是使用最原始的C语言实现的思路，想来语言变了实现方式大同小异吧。后续可能会不断实现不一样的数据结构。

节点
先确定节点数据结构（一个节点一个数字好了），后续慢慢一点点扩展：

/**
 * @author hsf
 * @description
 * @create 2018-07-14 下午3:47
 **/

public class Node {
    //数据
    public int value;
    //下一节点
    public Node next;

}

或许我需要换一个习惯的写法;

/**
 * @author hsf
 * @description
 * @create 2018-07-14 下午3:47
 **/

public class Node {
    //数据
    private int value;
    //下一节点
    private Node next;

    public int getValue() {
        return value;
    }

    public Node setValue(int value) {
        this.value = value;
        return this;
    }

    public Node getNext() {
        return next;
    }

    public Node setNext(Node next) {
        this.next = next;
        return this;
    }
}

这个时候其实就可以创建一个链表了，直接创建main方法吧；

public static void main(String [] args){
    //头节点
    Node head = new Node();
    head.setValue(-1);
    head.setNext(null);
    //第一个节点
    Node firstNode = new Node();
    firstNode.setValue(0);
    firstNode.setNext(null);
    //链接
    head.setNext(firstNode);
    System.out.println(head.getValue() + 
    " " +head.getNext().getValue());
}

运行结果

WX20180714-164038@2x.png

这可能是最简陋的链表了。
继续加工，把可以封装的封装起来，能增加的增加。
给节添加构造函数：

public Node(int value,Node next){
    this.value =value;
    this.next = next;
}

public Node(int value){
    this.value = value;
}

public Node(){}

封装几个方法

public boolean hasNext(){
    return this.next == null ? false : true;
}

public Node addToNext(Node node){
    this.next = node;
    return node;
}

改造main方法：

ublic static void main(String [] args){
    //头节点
    Node head = new Node(-1);
    //第一个节点
    Node firstNode = new Node(0);
    //第二个节点
    Node secondNode = new Node(1);
    //链接
    head.addToNext(firstNode);
    firstNode.addToNext(secondNode);
    System.out.println(head.getValue() + 
            " " +head.getNext().getValue() + 
            " " +head.getNext().getNext().getValue());
}

说实话这个输出方式有些蠢，需要一个新的方式输出，这里就写一个输出方法，效果就是以当前节点为头，输出以后的所有节点。
继续改造Node类

//直接重写toString好了
@Override
public String toString() {
    String val = Integer.toString(value);
    if(next != null){
        val = val.concat(" hasNext ");
        val = val.concat(next.toString());
    }
    return val;
}

这样就直接可以输出了，当然也可以使用循环方法实现。原来的输出直接换成

System.out.println(head);

输出

WX20180714-170151@2x.png

这是有个问题我假如需要加入一个节点到尾部怎么办呢，也就是也就是尾插法,新增一个方法：

//先找到尾巴，在插入就好了  需要的话可以返回尾节点。
public void addToTail(Node node){
    Node temp = this;
    while(temp.hasNext()){
        temp = temp.next;
    }
    temp.next = node;
}

既然有尾插法，那么就应该来一个头插法，头插法一般需要一个头节点，方法可以这么实现。

//现将新节点的值指向原有头节点的下一个节点，再将头节点指向新节点
public void addToHead(Node head,Node node){
    node.next = head.next;
    head.next = node;
}

当我需要往指定的位置插入一个节点的时候就想到了之前写的一个方法addToNext，此时再详细看这个方法会发现，这里的这个方法有问题，这里只是纯粹的再在当前节点后面添加，而不管这个节点之后是不是已经有节点。这样的会造成链表被截断。修改原有方法，增加链接原有节点到新节点。

public Node addToNext(Node node){
    node.next = this.next;
    this.next = node;
    return node;
}

最终main函数测试：

public static void main(String [] args){
    //头节点
    Node head = new Node(-1);
    //第一个节点
    Node firstNode = new Node(0);
    //第二个节点
    Node secondNode = new Node(1);
    //链接
    head.addToNext(firstNode);
    //加入第二个节点
    firstNode.addToNext(secondNode);
    //向尾部添加节点
    head.addToTail(new Node(2));
    //向头部添加节点
    head.addToHead(head,new Node(3));
    //向中间添加节点
    secondNode.addToNext(new Node(4));
    //输出
    System.out.println(head);
}

最终输出：

WX20180714-233034@2x.png

以上是一个单项链表简单实现；

单向链表逆转
假设只知道一个头节点。难度其实在于单向链表在没有指向前趋节点的情况下怎么获取到前驱节点，并且逆转之后怎么获取正确的原有下一节点。
先创建一个测试的方法入口并且定义好测试用的链表。

public static void main(String[] args) {
    //1个
    Node head = new Node(1);
    System.out.println(head);
    System.out.println(reverse(head));
    //2个
    head = new Node(1);
    head.addToNext(new Node(2));
    System.out.println(head);
    System.out.println(reverse(head));
    //3个
    head = new Node(1);
    head.addToNext(new Node(2))
            .addToNext(new Node(3));
    System.out.println(head);
    System.out.println(reverse(head));
    //4个
    head = new Node(1);
    head.addToNext(new Node(2))
            .addToNext(new Node(3))
            .addToNext(new Node(4));
    System.out.println(head);
    System.out.println(reverse(head));
    //多个
    head = new Node(1);
    Node tempHead = head;
    for (int i = 2; i <= 15; i++) {
        head = head.addToNext(new Node(i));
    }
    System.out.println(tempHead);
    System.out.println(reverse(tempHead));
}

·直接在原基础链表上反转
操作：遍历原有链表，直接将其下一个节点引用反转

public static Node reverse(Node head) {
    Node curNode = null;
    Node afterNode = null;
    if (head == null) {
        return null;
    }
    if (head.hasNext()) {
        curNode = head.getNext();
    } else {
        return head; //假如只有一个节点，则不反转
    }
    if (curNode.hasNext()) {
        afterNode = curNode.getNext();
    } else {
        curNode.setNext(head); //假如链表只有两个节点 直接反转引用
        head.setNext(null);
        return curNode;
    }
    //假如有3个及3个以上
    //先将第一个节点独立，如果不独立则这个节点将永远指向原链表中的第二个节点，则会成环。必须切断引用。
    head.setNext(null);
    Node newHead = head;//作为尾节点
    while (afterNode.hasNext()) {
        curNode.setNext(newHead);
        newHead = curNode;
        curNode = afterNode;
        afterNode = afterNode.getNext();
    }
    curNode.setNext(newHead);
    afterNode.setNext(curNode);
    return afterNode;
}

执行结果：

WX20180715-022129@2x.png

方法还有别的并且这个方法也应该是可以简化的,这个只是第一感觉写出来的，后续再更新......未完......

Java实现简单的链表-面向初学者

推荐阅读更多精彩内容