[数据结构与算法]2021-08-17

有关链表的一些知识点的总结

链表是一种特别的链式数据结构，他通过C语言中的指针功能来实现数据之间的链接。

因为指针可以达到间接访问的目的，所以当使用malloc函数得到一块内存，并且进行合理类型转换之后，我们就可以用指针来对这块内存进行访问。

由于我们开辟了内存空间，所以我们也要承担对相应内存的释放工作。

链表的每个节点里面有一个数据段和指针段。由于int类型的变量只能存储int，所以链表节点通常是结构体， 即一种复合类型的结构

在编写链表有关的程序时，我们会经常用到结构体指针。通过->访问符， 访问到指针所指向的结构体的各个对象

双向链表比单项链表多了一个向前指示的一个指针，且单链表只能向一个方向进行移动，而双向链表可以向两个方向移动

下面是顺序表和链表的差别

首先顺序表随机访问性强，查找速度快，可通过下标快速找到
但插入和删除时需要移动的数据，所以插入和删除效率低，且申请数组之前必须规定数组的大小，如果大小不合理，可能会浪费内存，数组大小固定，不能动态拓展

链表插入删除速度快，内存利用率高，不会浪费内存，大小没有固定，拓展很灵活。但是链表不能随机查找，必须从第一个开始遍历，查找效率相对较低