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

目录
  • 认识链表结构
    • 单向链表
    • 双向链表
  • 加深对链表结构的理解
    • 实现单向和双向链表的反转
    • 实现把链表中给定的值都删除
  • 小结

    认识链表结构

    单向链表

    单链表在内存中的表示:

    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还可以定义成泛型的。

    双向链表

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

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

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

    双向链表的结构:

    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;
        }
    }

    加深对链表结构的理解

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

    说明:

    对于一个链表如图所示:

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

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

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

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

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

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

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

    解题技巧:定义两个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;
    }

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

    链表原始状态:

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

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

    next = head.next:让next指向head(当前节点)的下一个节点,即b

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

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

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

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

    扫一扫手机访问