一文吃透单向链表：定义、查找、插入、删除全套 C 代码实现

简介链表是一个线性数据结构由一系列的结点组成每个结点包括两个部分一个是存储数据元素的数据域另一个是存储下一个结点地址的指针域节点动态分配长度可变。常见类型单向链表singly、双向链表doubly、循环链表circular。用途需要频繁在中间插入/删除的场景很合适。链表可用于实现数据队列。队列Queue是一种抽象数据类型ADT遵循 FIFO先进先出规则。只在队尾插入enqueue只在队头删除dequeue。队列可以用数组循环缓冲或链表实现。一、单向链表的数据定义单向链表也叫单链表是链表中最简单的一种形式它的每个节点包含两个域一个信息域元素域和一个链接域。这个链接指向链表中的下一个节点而最后一个节点的链接域则指向一个空值。单向链表是一种线性表实际上是由节点Node组成的一个链表拥有不定数量的节点。其数据在内存中存储是不连续的它存储的数据分散在内存中每个结点只能也只有它能知道下一个结点的存储位置。由N各节点Node组成单向链表每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点Head我们对链表的所有操作都是直接或者间接地通过其头节点来进行的。链表的数据定义代码如下//单向链表定义 typedef struct LNode *List; struct LNode { ElementType Data; List Next; }二、获取单向链表长度具体代码实现如下//获取单向链表长度 int Length(List Pstart) { List p Pstart; int j 0; while(p) { p p-Next; j; } return j; }三、单向链表查找数据3.1 按序号查找代码实现如下//1.按序号查找 int FindK(int K, List Ptrl) { List p Ptrl; int i 0; while((p ! NULL) (i K)) { P P-Next; i; } if(i K) { return p; } else { return NULL; } }3.2 按值查找代码实现如下//2.按值查找 int Find(ElementType Val, List Ptrl) { List p Ptrl; while((p ! NULL) (p-Data ! Val)) { p p-Next; } return p; }四、单向链表插入在第i-11≤i≤n1个结点后插入一个值为X的新结点。1.先构造一个新结点用s指向2.再找到链表的第i-1个结点用p指向3.然后修改指针插入结点p之后插入新结点是s。链表插入过程如下图所示程序实现如下//单向链表插入在第i-11≤i≤n1个结点后插入一个值为X的新结点 List Insert(ElementType X,int i,List Ptrl) { List P,S; if(i 1) //新结点插入在表头 { S (List)malloc(sizeof(stroct LNode)); //申请、填装结点 S-Data X; S-Next Ptrl; return S; //返回表头指针 } P Find(i-1,Ptrl); //查找第i-1个结点 if(P NULL) //第i-1个不存在不能插入 { printf(参数i错\r\n); return NULL; } else { S (List)malloc(sizeof(struct LNode)); S-Data X; S-Next P-Next; //新结点插入在第i-1个结点的后面 P-Next S; return Ptrl; } }五、删除删除链表的第i1≤i≤n个位置上的结点。1.先找到链表的第i-1个结点用p表示2.再用指针s指向要删除的结点p的下一个结点3.然后修改指针删除s所指向的结点4.最后释放s所指向结点的内存空间。链表删除过程如下图所示程序实现如下//删除删除链表的第i1≤i≤n个位置上的结点 List Delete(int i,List Ptrl) { List p,s; if(i 1) //若删除的是表的第一个结点 { s Ptrl; //s指向第一个结点 if(Ptrl ! NULL) { Ptrl Ptrl-Next; //从链表中删除 } else { return NULL; } free(s); //释放被删除的结点 return Ptrl; } p Find(i-1,Ptrl); //查找第i-1个结点 if(p NULL) { printf(第%d个结点不存在,i-1); return NULL; } else if(p-Next NULL) { printf(第%d个结点不存在,i); return NULL; } else { s p-Next; //s指向第i个结点 p-Next s-Next; //从链表中删除结点s free(s); //释放被删除的结点s return Ptrl; } }六、总结链表的知识点初学起来感觉很抽象开始时可以先把链表的定义、查找、插入、删除这些基本操作用代码敲一下然后最好是实际应用一下找一个例程把需要处理的数据通过链表存储起来数据的查找、更新数据插入、删除旧的数据等这些操作都实践一下只有用了才能真正理解链表只学习概念理论没什么用。