接上节：C/C++编程笔记：如何使用C++实现单链表？单链表第一部分。

单链表上的基本运算实现

(四) 求表长

由于我们的代码中已经定义过一个叫做 curLength 的变量用来记录我们的表长

所以我们可以直接返回，我们在定义中已经实现了，也就是这句：

        int size()const {return curLength;}//返回单链表的当前实际长度

但是如果我们没有这样一个变量，我们想要实现这样的功能又是什么样的方法呢？

(五) 遍历单链表

我们需要从头到尾访问单链表中的每一个节点，并且输出其中数据域的信息。

(六) 按照位序 i 寻找其元素对应内存地址

设置一个移动工作指针，和一个计数器 count，初始时p指向头结点，每当指针p移向下一个结点的时候，计数器count + 1 ，直到 p指向位序为 i的节点为止。返回 p。

(七) 按值查询节点位序

设置一个移动工作指针，和一个计数器 count，从单链表的第一个节点开始，开始于给定的值进行比对，如果相等则查找成功，返回节点的位序，否则继续查询知道单链表结束，查询失败返回 -1。

(八) 插入节点

在位序为 i 出插入值为value 的新节点q，我们需要做的就是找到位序为i - 1 的节点p，让q指针域指向原来p的后继，然后修改p的后继为q即可，说白了也就是修改插入元素位置前后的元素指向关系就可以了。

(九) 删除节点

能看懂添加节点的方法，理解删除节点也是手到擒来。

单链表整表的创建

回顾我们前面认识的顺序表，它其实可以理解为一个数组，我们声明一个类型，同时给定值，初始化其大小，但是单链表就不一样了，它是一种动态组织，它不需要像顺序表一样元素集中，它可以随着实际的情况来动态生成节点，所以也不需要预先分配空间大小和位置。

(一) 头插法创建单链表

头插法的意思就是说，每次新增节点全部插在头结点之后，首元结点之前，你可以这样理解，我先来排队，但是后面来了人，他就会排到我的前面去，我们来借助图看一下：

我们一次插入元素 123 但实际上输出的是按照321的顺序存储的，也就是说和我们的逻辑顺序是相反的。

我们来看一看怎么实现它：

逆置单链表

我们知道单链表中元素顺序与读入的顺序是相反的，我们可以通过逆置单链表的算法，帮助我们重新恢复我们的惯有思维顺序。

(二) 尾插法创建单链表

看完了头插法，但是感觉这样的顺序与我们一贯的思维总是有一点别扭，而尾插法则是一种，逻辑顺序与我们一致的创建方法。

还是看一下图：

合并单链表

要求：假设我们给出两个仍然是递增的单链表la和lb，我们将其合并为lc 仍保证递增，利用原表空间，但是我们仍在下面将表C称作新表。

因为我们的要求是递增的，所以使用尾插法是非常合适的，我们设计三个工作指针，分别指向两个表的首元结点，然后将第三个指针指向新表的头结点，比较前两个指针指向的值，小的就放到新表的表尾，然后后移动两表中较小的那一个的指针，以此类推，直到其中一个表尾空，将剩余的节点全部链接到新表的末尾。

总结

单链表，采取了链式存储结构，用一组任意的存储单元存放线性表的元素，尤其对于需要频繁的插入和删除数据的时候更加适用，如果需要进行频繁的查找还是推荐使用顺序表，例如对于一个学生成绩管理系统的制作，学生更多的时候是查看自己的成绩，而录入的老师，也只有在考试后录入一次，所以应该使用顺序表，而例如考勤打卡系统，更多的是打卡信息的记录，所以还是选择使用链表，当然例子可能不是很恰当，同时正常的开发中还会有更多复杂的问题需要考虑，举例子只为了利于理解。

另外，UP在主页上传了一些学习C/C++编程的视频教程，有兴趣或者正在学习的小伙伴一定要去看一看哦！会对你有帮助的~