数据结构 - 单链表
概念与结构
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。虽然逻辑上是线性的,但物理存储不一定连续。
可以把链表想象成一列火车,车头是哨兵位(可有可无),车厢就是节点。每节车厢都是独立存在的,去掉或加上一节不会影响其他车厢。
结点
链表的每节'车厢'在内存中是独立申请的,我们称之为'结点'。一个结点主要包含两部分:
- 当前结点要保存的数据。
- 保存下一个结点的地址(指针变量)。
我们需要通过指针变量来保存下一个结点的位置,才能从当前结点找到下一个结点。当没有下一个结点时,指针通常指向 NULL。
结合结构体知识,假设当前保存的结点为整型,定义如下:
struct SListNode {
int data; // 结点数据
struct SListNode* next; // 指针变量,用于保存下一个结点的地址
};
当我们想要保存一个整型数据时,实际是向操作系统申请了一块内存,这块内存不仅要保存整型数据,也需要保存下一个结点的地址。当我们想要从第一个结点走到最后一个结点时,只需要在当前结点拿取下一个结点的地址就可以了。
链表的打印
遍历链表并输出每个节点的值是调试和验证的基础操作。
实现单链表
下面以 C 语言为例,展示单链表的核心功能实现。
头文件 (SList.h)
定义了数据类型、节点结构以及函数声明。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 链表的数据类型
typedef int SLTDataType;
// 链表的结构
typedef struct SListNode {
SLTDataType data;
struct SListNode* next; // 指向下一个节点的地址
} SLTNode;
// 函数声明
void SLTPrint;
;
;
;
;
SLTNode* ;
;
;
;
;
;


