链表的引入
从数组的缺陷说起
- 数组有2个缺陷:一个是数组中所有元素的类型必须一致;第二个是数组的元素个数必须事先制定并且一旦指定之后不能更改。
- 如何解决数组的2个缺陷:数组的第一个缺陷靠结构体去解决。结构体允许其中的元素的类型不相同,因此解决了数组的第一个缺陷。所以说结构体是因为数组不能解决某些问题所以才发明的。
- 如何解决数组的第二个缺陷?我们希望数组的大小能够实时扩展。譬如我刚开始定了一个元素个数是10,后来程序运行时觉得不够因此动态扩展为20.普通的数组显然不行,我们可以对数组进行封装以达到这种目的;我们还可以使用一个新的数据结构来解决,这个新的数据结构就是链表。
- 总结:几乎可以这样理解:链表就是一个元素个数可以实时变大/变小的数组。
大学为什么都有新校区?
- 学校初建的时候(类似于变量定义并初始化时),这时候因为旁边都是荒地而没有建筑,因此学校的校园大小由自己定的;但是学校建立了之后旁边慢慢的也有了其他建筑(类似于这个变量分配了之后,内存的相邻区域又分配了其他变量与这个变量地址相连),这时候你的校园随着发展感觉不够用了想要扩展,却发现邻居已经住满了,校园的四周全部都是别人的建筑,这时候学校要扩展有2个办法:第一个是拆迁,第二个是搬迁,第三个是外部扩展。
- 拆迁基本行不通,因为成本太高了。
- 搬迁可以行的通。程序中解决数组大小扩展的一个思路就是整体搬迁。具体步骤是:先在另外的空白内存处建立一个大的数组,然后把原来的数组中的元素的值整个复制到新数组的头部,然后再释放掉原来数组的内存空间,并且把新的数组去替代原来的数组。这种可变数组在C语言中不支持,但是在更高级语言如C++、Java等里面是支持的。
- 外部扩展的思路是最常见的,基本可以说是最合理的。它的一个思路就是化整为零,在原来的不动的前提下去外部扩展新的分基地。外部扩展在学校的例子中就是新校区;外部扩展在编程解决数组问题的点上就是链表。
链表是什么样的?
- 顾名思义,链表就是用锁链连接起来的表。这里的表指的是一个一个的节点(一个节点就是一个校区),节点中有一些内存可以用来存储数据(所以叫表,表就是数据表);这里的锁链指的是链接各个表的方法,C语言中用来连接2个表(其实就是2块内存)的方法就是指针。
- 链表是由若干个节点组成的(链表的各个节点结构是完全类似的),节点由有效数据和指针组成。有效数据区域用来存储信息完成任务的,指针区域用于指向链表的下一个节点从而构成链表。
时刻别忘了链表是用来干嘛的
- 时刻谨记:链表就是用来解决数组的大小不能动态扩展的问题,所以链表其实就是当数组用的。直白点:链表能完成的任务用数组也能完成,数组能完成的任务用链表也能完成。但是灵活性不一样。
- 简单说:链表就是用来存储数据的。链表用来存数据相对于数组来说优点就是灵活性,需要多少个动态分配多少个,不占用额外的内存。数组的优势是使用简单(简单粗暴)。
单链表的实现
单链表的节点构成
- 链表是由节点组成的,节点中包含:有效数据和指针。
- 定义的struct link只是一个结构体,本身并没有变量生成,也不占用内存。结构体定义相当于为链表节点定义了一个模板,但是还没有一个节点,将来在实际创建链表时需要一个节点时用这个模板来复制一个即可。
struct link
{
int data; // 定义一个有效数据
struct link *pNext; // 指向下一个节点
};
堆内存的申请和使用
- 链表的内存要求比较灵活,不能用栈,也不能用data数据段(开机分配)。只能用堆内存。(既 内存无限多,能随意删除,)
- 使用堆内存来创建一个链表节点的步骤:
- 申请堆内存,大小为一个节点的大小(检查申请结果是否正确);
- 清理申请到的堆内存;
- 把申请到的堆内存当作一个新节点;
- 填充下个新节点的有效数据和指针区域。
struct link *pHeader = NULL; // 定义一个头指针,指向一个链表
// 创建一个链表节点;每创建一个新节点,就把这个节点和上一个节点关联起来
struct link *p1 = (struct link *)malloc(sizeof(struct link)); // 分配一个结构体大小的内存空间
if(NULL == p1) // 检查指针的有效性
{
printf("malloc *p1 error
");
return -1;
}
memset(p1, '