封装链表:
1、单链表
由于不封装链表结构时,链表的尾添加效率低
其次非法位置的判断效率也很低,只能遍历来判断
节点:
数据域data
指针域next
链表结构:
头指针
尾指针
节点数量
注意:删除节点时,无论是按位置删除、按值删除都需要找到待删除节点的前一个节点
2、静态链表(了解)
节点:
数据域
游标
特点:
1、静态链表的节点存储在一段连续的内存中,通过游标来访问下一个节点
2、插入、删除节点时,只需要修改游标的值即可,不需要动态申请、释放节点(静态链表)
3、但是也牺牲了随机访问的功能、堆内存的要求高,只是给没有指针的编程语言提供实现链表的方式
3、循环链表
链表的最后一个节点的next不指向NULL,而是指向第一个节点,这种链表称为循环链表,如果是单链表则称为单循环链表,好处是可以在任意一个节点开始遍历整个链表
4、双向链表(大部分循环)
注意:双线链表一般会实现为双向循环链表,最好一个节点的nuxt指向第一个节点,第一个节点的prev指向最后一个节点。
节点:
前趋指针: prev
数据域: data
后继指针: next
封装双循环链表结构:
头节点指针 head
节点数量
注意:1、封装的是带头节点的双链表,否则插入删除操作可能会改变head的指向,需要每次判断(麻烦),带头节点不需要考虑以上情况
2、删除操作时,不再需要找待删除节点的前一个位置
3、因为是双向循环链表,所以可以更具需要从前往后遍历,也可以从后往前遍历,从而提高查找的效率
5、Linux内核链表
既然节点中不能包含任何类型,那么就让任何类型来包含节点
6、通用链表
能够存储并操作任意类型的数据到链表中并提供对应的操作
万能指针 void*
C语言中任意类型的指针可以转换成void*类型
void*类型指针可以转换成任意类型指针
节点:
void* ptr; //数据域
指针域;
链表结构:
头节点
数量
核心点:
1、void* 确保能存储任意类型数据
2、普通操作参考双链表即可
3、通过回调模式来实现一些特殊操作,例如:遍历、按值操作、排序