文章目录单链表的定义结点结构核心特点两种结构不带头结点带头结点用代码定义单链表的结点说明用代码定义一个单链表不带头结点的单链表初始化函数带头结点的单链表初始化函数判断是否为空单链表的定义单链表是一种线性表它逻辑上由一串结点Node组成每个结点包含数据元素和指向下一个节点的 “ 链 ”从而形成一条单向的线性序列。单链表每个节点只包含两部分数据域存放当前元素的值指针域存放下一个结点的地址只能单向向后遍历无法回头。结点结构【数据data】 | 【后继指针next】next存储下一个节点地址最后一个节点next NULL代表链表结束。核心特点内存不连续依靠指针串联无需预先分配空间动态申请 / 释放结点按值查找、插入删除需要遍历时间复杂度O(n)没有随机访问不能像顺序表data[i]直接定位只能顺着指针向后走不能反向遍历。两种结构不带头结点头指针 L 直接指向第一个存数据的结点空链表L NULL头指针指向空说明无下一个元素。表头插入、删除第一个元素需要特殊处理代码繁琐。带头结点头指针L指向一个不存数据的空节点头结点真正数据从L-next开始空链表L-next NULL所有位置插入 / 删除逻辑统一无需单独处理表头代码简洁。用代码定义单链表的结点// 定义结点类型typedefstructLNode{intdata;// 数据域存放有效数据这里以int为例structLNode*next;// 指针域存放下一个同类型结点的地址}LNode,*LinkList;// ① LNode 是结点别名② LinkList 是“指向结点的指针”的别名// typedef struct LNode LNode;// typedef struct LNode *LinkList;// 要表示一个单链表时只需声明一个头指针 L ,指向单链表的第一个结点// LNode * L; // 声明一个指向单链表第一个结点的指针// LinkList L; // 声明一个指向单链表第一个结点的指针//说明struct LNode节点结构体类型typedef struct LNode LNode简写类型名 LNodetypedef struct LNode *LinkListLinkList LNode *链表头指针类型LinkList L等价于LNode *L代表链表头指针LNode *与LinkList都表示头结点但使用LinkList强调这是一个单链表使用LNode强调这是一个结点。用代码定义一个单链表不带头结点的单链表#includestdio.h#includestdlib.htypedefstructLNode{// 定义单链表结点类型intdata;// 以intl类型为例 // 每个结点存放一个数据元素structLNode*next;// 指针指向下一个同类型的结点}LNode,*LinkList;// 初始化一个空的单链表boolInitList(LinkListL){LNULL;// 空表暂时还没有任何结点 : 防止脏数据returntrue;}// 判断单链表是否为空boolEmpty(LinkList L){if(LNULL)//returntrue;elsereturnfalse;}// 或//bool Empty(LinkList L){// return (LNULL);//}intmain(){LinkList L;// 声明一个指向单链表的指针// 初始化一个单链表InitList(L);// ...return0;}LNode等价于struct LNode代表结点类型用于 malloc 分配内存。LinkList等价于struct LNode *代表指向结点的指针即链表头指针类型用于定义头指针 L。LinkList L等价LNode *L。语义上的区别当写LinkList L;时强调的是“这是一个链表入口指针”。当写LNode *p;时强调的是“这是一个指向某个节点的指针临时遍历用”。虽然底层都是指针但用不同的别名能显著提高代码可读性。在代码中写LinkList L是绝对标准的。初始化函数boolInitList(LinkListL){LNULL;returntrue;}1.LinkList LC 中的引用函数内的L是main中头指针L的别名如果不加只会修改函数内副本外部头指针依旧是随机野指针2.L NULL核心不带头结点链表头指针直接指向第一个数据结点没有结点时头指针直接赋值NULL代表空链表。带头结点的单链表#includestdio.h#includestdlib.htypedefstructLNode{// 定义单链表结点类型intdata;// 以intl类型为例 // 每个结点存放一个数据元素structLNode*next;// 指针指向下一个同类型的结点}LNode,*LinkList;// 初始化一个空的单链表 带头结点boolInitList(LinkListL){L(LNode*)malloc(sizeof(LNode));// 分配一个头结点if(LNULL)// 内存不足分配失败returnfalse;L-nextNULL;// 头结点之后暂时还没有结点 头结点的下一个数据的指针置空代表当前链表没有任何有效数据结点。returntrue;}// 判断单链表是否为空 (带头结点boolEmpty(LinkList L){if(L-nextNULL)//returntrue;elsereturnfalse;}// 或//bool Empty(LinkList L){// return (L-nextNULL);//}intmain(){LinkList L;// 声明一个指向单链表的指针// 初始化一个单链表InitList(L);// ...return0;}初始化函数boolInitList(LinkListL){L(LNode*)malloc(sizeof(LNode));if(LNULL)returnfalse;L-nextNULL;returntrue;}L (LNode *)malloc(sizeof(LNode));在堆内存分配一个结点大小的空间作为头结点头结点不存储有效数据仅用来统一链表操作逻辑malloc返回void*必须强制转换为LNode*。if(L NULL)堆内存耗尽时malloc分配失败返回空指针直接返回false表示初始化失败。判断是否为空
