🌺链表的定义
线性表的链式存储又称为单链表，其特点是用一组任意的存储单元来存储线性表的数据元素。
为了表示每个数据元素ai与其后续数据元素ai+1之间的逻辑关系，a1除了存储自身的信息之外，还需要存储一个指向其后续内容的信息（一般为后续内容的地址）。这两部分信息组成数据元素ai的存储映像，称为结点。
单链表中结点类型的描述如下：
typedef struct LNode //定义单链表结点类型 { ElemType data; //数据元素 struct LNode *next; //指向下一地址 }LNode, *LinkList;
🌺链表的存储方式
整个链表的存取必须从头指针开始进行，头指针指向链表的第一个结点的存储位置。同时由于最后一个元素没有直接后继，则单链表的最后一个结点的指针为空（NULL）
我们来想一想，如果用链表来存储【Ceylan】，它的逻辑状态是什么样的呢？
首先应该需要一个头指针L，它指向第一个元素 'C'，通过 'C' 所在结点的信息，可以访问下一节点 'e' 所在位置，以此类推，就可以完整找到整个【Ceylan】
🌺单链表的初始化
单链表的初始化就是建立一个新的空的单链表。
🔺实现原理
1️⃣生成新结点作为头结点，用头指针L指向头结点
2️⃣头结点指向空
💬 代码演示
Status InilList(LinkList &L) {//构建一个空的链表L L=new LNode; //生成新结点作为头结点，用头指针L指向头结点 L->next=NULL; //头结点指向空 return OK; }
🌺头插法建立单链表
🔺实现原理
1️⃣建立一个空表，生成新节点
2️⃣将数据存放到新节点的数据域中
3️⃣将新节点插入到当前链表的表头，也就是头结点之后
💬 代码演示
void CreateList_H(LinkList &L,int n) { L=new LNode; L->next=NULL; //先建立一个带头结点的空链表 for(int i=0;i<n;i++) { p=new LNode; //生成新节点*p cin>>p->data; //输入p结点的数据 p->next=L->next;L->next=p; //将新结点*p插入到头结点之后 } }
❗️注意：
因为每次插入都是在链表头部，所以应该逆位序输入数据。输入顺序和线性表中的逻辑顺序是相反的。
🌺尾插法建立单链表
🔺实现原理
1️⃣建立一个空表，生成新节点
2️⃣将数据存放到新节点的数据域中
3️⃣将新节点插入到当前链表的尾部
💬 代码演示
void CreateList_R(LinkList &L,int n) { L=new LNode; //先建立一个带头结点的空链表 r=L; //尾指针指向头结点 for(int i=0;i<n;i++) { p=new LNode; //生成新节点*p cin>>p->data; //输入p结点的数据 p->next=NULL;r->next=p; //将新结点*p插入尾结点*r之后 r=p } }
🌺按序号寻找结点值
🔺实现原理
1️⃣从第一个结点开始，顺指针next逐个向下搜索，直到找到第 i 个结点，
2️⃣若没有找到，返回最后一个指针域NULL
💬 代码演示
LNode *GetElem(LinkList L,int i) { int j=1; //计数，初始为1 LNode *p=L->next; //头结点指针赋值给p if(i==0) return L; //若i为 0，返回头指针 if(i<1) return NULL; //若i无效，则返回 NULL while(p&&j<i) //从第一个元素开始找，直到第i个结点 { p=p->next; j++; } return p; //返回第 i 个结点的指针 }
🌺按值寻找结点
🔺实现原理
1️⃣从第一个结点开始，顺指针next逐个向下搜索数值，直到找到符合的数值
2️⃣若没有找到，返回最后一个指针域NULL
💬 代码演示
LNode *LocateElem(LinkList L,ElemType e) { LNode *p=L->next; while(p!=NULL&&p->data!=e) //从第一个结点开始查找数据域为 e 的结点 { p=p->next; } return p; //找到后返回该结点指针，否则返回NULL }
🌺插入结点
将值为 x 的新结点插到单链表的第 i 个位置。
🔺实现原理
1️⃣调用按序号查找函数，查找第i-1个结点，假设返回结点为*p
2️⃣令新结点*s的指针域指向*p的后续结点
3️⃣令结点*p的指针域指向新的插入的结点*s
💬 代码演示
p=GetElem(L,i-1) //查找插入位置的前驱结点 s->next=p->next; //新结点*s的指针域指向*p的后续结点 p->next=s; //令结点*p的指针域指向新的插入的结点*s
🌺删除结点
将单链表的第 i 个结点删除。
🔺实现原理
1️⃣调用按序号查找函数，查找第 i 个结点，假设返回结点为*p
2️⃣将*p指针域next指向下下位结点
p=GetElem(L,i-1) //查找删除位置的前驱结点 q=p->next; //令q指向被删除结点 p->next=q->next; //将*q结点从链中断开 free(q); //释放结点的存储空间
🌺结束语
本人不才，如有错误，欢迎各位大佬在评论区指正。有帮助的话还请【关注➕点赞➕收藏】，不行的话我再努努力💪💪💪
