数据结构解析-链表

什么是链表

单链表双向链表循环列表双向链表 Java ListNode 链表

链表是由一组不必相连的内存结构，按照特定的顺序连接在一起的抽象数据类型

单链表：由各个内存结构通过一个Next追针连接在一起组成，每一个内存结构都存在后继内存结构【链尾除外】

数 据 结 构 模 型 如 下 color{#FF00FF}{数据结构模型如下} 数据结构模型如下

解析模型

Data数据 + Next指针，组成一个单链表的内存结构第一个内存结构称为链头，最后一个内存结构称为链尾链尾的Next指针设置为null「指向空指针」单链表的遍历方向单一「只从链头一直遍历到链尾」 双向链表

双向链表：由各个内存结构通过指针Next 和 指针Pre连接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构。那么内存结构又分为数据域，Pre指针域和Next指针域

数 据 结 构 模 型 如 下 color{#FF00FF}{数据结构模型如下} 数据结构模型如下

解析模型

Data 数据 + Next 指针 + Pre 指针，组成一个双向链表的内存结构；第一个内存结构称之为“链头”，最后一个称之为“链尾”“链头”，“链尾”指针设置为空「NULL」Prev 指向的内存结构称为 “前驱”， Next 指向的内存结构称为“后继”；区分链表方向定义就是：把从链头的 Next 一直到链尾的[NULL] 遍历方向定义为正向，那么从链尾的 Prev 一直到链头 [NULL ]遍历方向就是反向； 循环列表

单向循环列表：由各个内存结构通过一个Next指针链接在一起，每一个内存结构都存在着后继内存结构，内存结构由数据域和Next指针域组成

单 向 列 表 数 据 结 构 模 型 如 下 color{#FF00FF}{单向列表数据结构模型如下} 单向列表数据结构模型如下

解析模型

单向说白就是在单链表的基础上，把链尾的 Next 指针直接指向链头，形成一个闭环； 双向链表

双向循环链表 : 由各个内存结构通过指针 Next 和指针 Pre 链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构，内存结构由数据域、Pre 指针域和 Next 指针域组成。

双 向 列 表 数 据 结 构 模 型 如 下 color{#FF00FF}{双向列表数据结构模型如下} 双向列表数据结构模型如下

解析模型

双向的实现就是在双向链表的基础上，把链尾的 Next 指针指向链头，再把链头的 Pre 指针指向链尾，形成一个闭环；

注意：

循环链表没有链头和链尾的说法，因为是闭环的，所以每一个内存结构都可以充当链头和链尾；

定 义 链 表 初 始 化 color{#0000FF}{定义链表初始化} 定义链表初始化

package com.j.dataStructure;


//java类就是一种自定义的数据结构
public class ListNode {
    //节点数据
    public E val;
    //对象：Java中没有指针的概念，类似于指针概念
    public ListNode next;

    //添加构造方法方便初始化 ==构造方法名称和类名相同
    public ListNode(E val) {
        this.val = val;
    }
}

遍 历 链 表 color{#0000FF}{遍历链表} 遍历链表

package basics;

import com.j.dataStructure.ListNode;


public class Test {
    public static void main(String[] args) {
        //创建首节点
        ListNode nodeStart = new ListNode(0);
        //声明一个变量在移动过程中指向当前节点
        ListNode nextNode;
        //指向首节点
        nextNode = nodeStart;

        //创建链表
        for (int i = 0; i < 10; i++) {
            ListNode node = new ListNode(i);
            //连接新节点
            nextNode.next = node;
            //当前节点向后移动
            nextNode = nextNode.next;
            //循环完成之后，nextNode指向最后一个节点
            nextNode = nodeStart;
            //输出
            print(nextNode);
        }
    }

    //打印输出方法
    private static void print(ListNode nextNode) {
        //创建链表节点
        while (nextNode != null) {
            System.out.println("节点：" + nextNode.val);
            nextNode = nextNode.next;
        }
        System.out.println();
    }
}