Java链表数据结构及其简单使用方法解析

认识链表结构

单向链表

单链表在内存中的表示：

可以看到，一个链表的节点包含数据域和指向下一个节点的引用，链表最后一个节点指向null（空区域）。

我们可以根据这一定义，用java语言表示一下单向链表的结构：

public class Node {
    public int value;
    public Node next;
    
  编程客栈  public Node(int value) {
        this.value = http://www.cppcns.com/ruanjian/java/value;
    }
}

在链表的结构中，有数据域value，以及一个指向下一个节点的引用next。

TIP：这里的value还可以定义成泛型的。

双向链表

我们再来看一下双向链表的结构：

双向链表中的节点有数值域，和指向它前一个节点的引用以及指向编程客栈它后一个节点的引用，据此我们可以定义出

双向链表的结构：

public class DoubleNode {
    public int value;
    public DoubleNode pre;
    public DoubleNode next;
    
    public DoubleNode(int value) {
        this.value = http://www.cppcns.com/ruanjian/java/value;
    }
}

加深对链表结构的理解

实现单向和双向链表的反转

说明：

对于一个链表如图所示：

反转的意思是，将原来链表上的节点指针指向反转，原来的指向是：a -> b -> c -> d -> null，变成现在的指向：d -> c -> b -> a -> null，

即反转后的结构如图所示：

这个题目不难，我们转换一下指针的指向就行了。

设计这样一个函数，函数的过程是调整链表各节点的指针指向，那么这个函数的要素有：

返回值是链表的新的头结点，这样能保证函数执行完，原链表变成一个有新的头结点的链表
需要传入一个链表，用头结点表示

解题技巧：定义两个Node引用辅助我们反转指针指向。

代码实现：

public static Node reverseNode(Node head) {
    Node pre = null;
    Node next = null;
    //最终让head指向null
    while (head != null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

我们来模拟一下这个函数的执行过程。

链表原始状态：

方法开始执行，此时 head.next 不为空，所以，执行如下步骤：

next = head.next：让next指向head（当前节点）的下一个节点，即b

head.next = pre：让当前节点的下一个节点指向pre，即null

此时当前节点从原来指向b，改为指向null。

pre = head：让pre指向当前节点
head = next：让当前节点指向next，相当于移动head节点，直到将head节点移动到原来tail节点的位置
Java链表数据结构及其简单使用方法解析

目录