【数据结构入门】2.5.1线性表的链式表示和实现（核心概念）（持续更新ing）

一、核心概念

（一）结点（Node）

数据元素的存储映像，由 数据域 和 指针域 两部分组成：

• 数据域：存储元素的数值数据（如“赵、钱、孙”等具体数据 ）。
• 指针域：存储直接后继结点的存储位置（地址），通过指针建立结点间的逻辑关联，使离散的结点能构成表结构。

（二）链表（Linked List）

由 n（n≥0 ）个结点通过指针链连接组成，是线性表的链式存储映像，体现线性表逻辑结构的“一对一”关系。与顺序表不同，链表不要求元素在内存中连续存储，通过指针维护元素间逻辑顺序，插入、删除操作无需大规模移动元素（只需调整指针）。

二、链表关键组件

（一）头指针（Head Pointer）

• 定义：指向链表中第一个结点的指针（若有头结点则指向头结点，无头结点则直接指向首元结点 ）链表的“入口”。

（二）头结点（Head Node）

• 定义：在链表首元结点之前附加的结点。

（三）首元结点（First Element Node）

链表中存储第一个有效数据元素的结点

（线性表逻辑结构里的 a₁、“赵”等 ）

若有头结点，首元结点是头结点后继结点；无头结点时，首元结点直接由头指针指向。

三、链表分类与结构示例

（一）单链表（Singly Linked List）

• 结构特点：每个结点只有一个指针域，指向直接后继结点，表尾结点指针域为 NULL（或 ^ ），表示无后继。
• 示例（以 26 个小写英文字母线性表 (a, b, …, y, z) 为例 ）：
  • 逻辑结构：线性表元素按顺序排列，体现“a→b→…→z”的逻辑关系。
  • 链式存储：head 为头指针，指向首元结点（存储 ‘a’ 的结点 ）；每个结点数据域存字母，指针域存后继结点地址，‘z’ 结点指针域为 NULL，链表结束。
  • 

（二）双链表（Doubly Linked List）

• 结构特点：每结点两个指针域，分别指向 直接前驱结点 和 直接后继结点 

（可双向遍历，弥补单链表只能从前往后遍历的局限，插入、删除时需同时调整前驱和后继指针。）

• 示例示意：头指针 L 指向头结点（或首元结点，依设计而定 ），结点通过 prev（前驱指针 ）和 next（后继指针 ）连接，首尾结点的前驱/后继指针合理置空或指向头结点（循环双链表场景 ）。
• 

（三）循环链表（Circular Linked List）

• 结构特点：表尾结点指针域不指向 NULL，而是指向头结点（带头结点循环链表 ）或首元结点（不带头结点循环链表 ），使链表形成环形，可从任意结点开始遍历整个链表，适用于需循环访问数据的场景（如约瑟夫环问题 ）。
• 示例（带头结点循环链表 ）：头指针 L 指向头结点，表尾结点指针域指向头结点，遍历到表尾后可直接回到表头，逻辑上无“终点”，强化循环访问特性。

讨论1：如何表示空表？

  （1）无头结点时，头指针为空为空表

（2）有头结点时，当头指针的指针域为空时表示空表

讨论1：链表中设置头结点有什么好处？

(1)便于首元节点的·1处理

          首元节点 的 地址 保存在 头结点 的 指针域 中，所以在 链表 的第一个位置上的操作和其他位置一致，无需特殊处理

讨论 3：头结点的数据域内装的是什么？

头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。

实体信息为链表（链式存储结构）的特点

（1）结点在存储器中位置任意，逻辑相邻数据元素物理不一定相邻 。

（2）访问需经头指针进入，依结点指针域顺序扫描，找第一个和最后一个结点耗时不等 。

顺序表像 “连续的货架”，知道层数（下标）就能直接找；

链表像 “用绳子串起的珠子”，想找第 n 颗，必须从第一颗挨个捋绳子 。

文章来源于互联网:【数据结构入门】2.5.1线性表的链式表示和实现（核心概念）（持续更新ing）

相关推荐: 5 零基础学comfyUI | 插件的安装方式与基础插件

    摘要： 本节聚焦ComfyUI插件的相关内容，核心介绍其安装方式及必备插件的概况。ComfyUI的强大得益于开源社区的各类插件，这些插件需通过新建节点及连接才能使用，因此正式使用前需了解并安装常用插件。插件安装方式有五种：启动器中搜索名称或通过地址安装…