java实现一个简单的链表结构

定义

所谓链表就是指在某节点存储数据的过程中还要有一个属性用来指向下一个链表节点，这样的数据存储方式叫做链表

链表的优缺点

优点：易于存储和删除

缺点：查询起来较麻烦

java实现

下面我们用java来实现如下链表结构：

首先定义节点类：

代码块1

package LinkTest;
/**
 * 链表节点类
 * @author admin
 *
 */
public class Node {
    private int value;//存储数据
    private Node next;//下一个节点
    /**
     * 定义构造器
     * @param vlaue
     * @param value 
     */
    public Node(int value){
        this.value=value;
    }
    public int getValue() {
        return value;
    }
    public void setValue(int value) {
        this.value = value;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
}

再定义一个链表类：

注意：遍历链表定义了两个方法，一个是普通方法，一个是递归方法，都可以遍历出来

代码块2

代码块2

package LinkTest;
/**
 * 链表
 * @author admin
 *
 */
public class Link {
    private Node current;
    private Node root;
    public void insert(int vlaue){
        Node newNode=new Node(vlaue);
        if(this.current==null){
            this.current=newNode;
            this.root=this.current;
        }else{
            this.current.setNext(newNode);
            this.current=this.current.getNext();
        }
    }
    //普通遍历
    public void getList(){
        this.current=this.root;
        while(this.current!=null){
            System.out.print(this.current.getValue());
            this.current=this.current.getNext();
            if(this.current!=null){
                System.out.print("------->");
            }
        }
    }

    //递归遍历
    public void getList2(){
        DG(this.root);
    }

    //递归方法
    public void DG(Node node){
        System.out.print(node.getValue()+"----->");
        if(node.getNext()!=null){
            DG(node.getNext());
        }else{
            return;
        }
    }
}

测试类：

代码块3

package LinkTest;
/**
 * 测试类
 * @author admin
 *
 */
public class Test {
    public static void main(String[] args){
        Link l=new Link();
        l.insert(1);
        l.insert(4);
        l.insert(5);
        l.insert(6);
        l.insert(9);
        l.insert(8);
        l.getList();
    }
}

测试类运行结果：

1------->4------->5------->6------->9------->8

这样我们就用java实现了一个简单的链表结构。

链表的翻转

所谓链表翻转，就是让原来的链表元素倒过来，比如：

1------->4------->5------->6------->9------->8

翻转后就变成了：

8------->9------->6------->5------->4------->1

代码实现：

代码块4

static Node reserve(Node node) {
    
    if (node == null || node.getNext() == null) {
		return node;
    }

    Node prev = null;
    Node next = null;

		while (node != null) {
        next = node.getNext(); // 利用next暂存剩下的链条

        // 下面这两步用来构建翻转链表
        node.getNext() = prev; // 当前node的next指向prev
				prev = node; // prev变成当前的node

				node = next; // node恢复成原来剩下的链条，便于后续遍历
		}
	return prev; // 最终返回翻转后的链表
}

将一个链表丢到上述方法中，就会返回一个顺序颠倒的结果出来。