单链表（一）中，如何实现节点插入操作？

本文共计1108个文字，预计阅读时间需要5分钟。

通过学习排序表，我们可以发现排序表存在以下几点缺陷：

1.空间不足，需要扩容。扩容时使用realloc进行异地扩容，虽然效率较高，但存在一定的代价值。下次扩容还可能存在一定的空间浪费。

2.头部或头部可能存在未充分利用的空间。

通过对顺序表的学习，我们可以发现顺序表有以下几点缺陷： 1.空间不够时需要扩容，扩容尤其是用realloc进行异地扩容时，是有一定代价的，其次还可能存在一定空间浪费。 2.头部或者中间插入删除，需要挪动数据，效率低下。 那我们可以对其所具有的缺陷进行优化：可以按需申请空间同时插入删除时不挪动数据。而单链表就符合这些优化所具有特点。==但是我们要注意的是单链表具有这些优点并不代表链表就可以完全替代顺序表==。

一、单链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 </br> 从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续，物理结构中指针域存储的是下一个结点的地址；而且链式结构的结点一般都是从堆上申请出来的；从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。