前面学习了链表,其存储结构如图 1 所示:
类似图 1 这样的链表,它更喜欢人们称它为 "动态链表"。
随后又接触了静态链表。同样是存储图 1 中的数据 {1,2,3},使用静态链表存储数据的状态如图 2 所示:
为了让读者分清动态链表和静态链表,本节来分析一下它们之间的区别和联系。
使用静态链表存储数据,需要预先申请足够大的一整块内存空间,也就是说,静态链表存储数据元素的个数从其创建的那一刻就已经确定,后期无法更改。
比如,如果创建静态链表时只申请存储 10 个数据元素的空间,那么在使用静态链表时,数据的存储个数就不能超过 10 个,否则程序就会发生错误。
不仅如此,静态链表是在固定大小的存储空间内随机存储各个数据元素,这就造成了静态链表中需要使用另一条链表(通常称为"备用链表")来记录空间存储空间的位置,以便后期分配给新添加元素使用,如图 2 所示。
这意味着,如果你选择使用静态链表存储数据,你需要通过操控两条链表,一条是存储数据,另一条是记录空闲空间的位置。
使用动态链表存储数据,不需要预先申请内存空间,而是在需要的时候才向内存申请。也就是说,动态链表存储数据元素的个数是不限的,想存多少就存多少。
同时,使用动态链表的整个过程,你也只需操控一条存储数据的链表。当表中添加或删除数据元素时,你只需要通过 malloc 或 free 函数来申请或释放空间即可,实现起来比较简单。