4.链表上（Linked List）

通过“指针”将一组零散的内存块串联使用，支持动态扩容

单链表

链表的结点——内存块

后继指针next——记录下个节点地址的指针

头结点记录链表的基地址

尾结点指向空地址NULL

插入删除只需改变相邻结点的指针，时间复杂度O(1)

随机访问时间复杂度O(n)
（类比队伍，队伍中每个人只知道自己后面的人是谁）

循环链表

区别：尾结点指针指向链表的头结点

优点：从链尾到链头比较方便

双向链表

每个结点还有前驱指针prev指向前面结点

优点：支持双向遍历

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容