软件测试 / 测试开发丨 Python 学习笔记 之 链表
免费领取:测试资料+测试用例+简历模板+测试文档
本文为霍格沃兹测试开发学社学员学习笔记分享
链表与数组的区别
复杂度分析
其他角度分析内存连续,利用 CPU 的机制,可以预读链表中的数据,故访问效率高而数组在内存中并不是连续存储的,所以 CPU 缓存不友好,没办法预读数组的大小不固定,及时动态申请,也需要拷贝数据,费时费力链表支持动态扩容链表的缺点是:存储空间大
单链表和循环链表
区别在于头结点与尾结点是否相连
循环链表从尾部可以直接到达头,适合环形数据结构,比如约瑟夫问题
双向链表优点
找到上一个结点的时间复杂度为 O(1)
插入、删除操作更高效
删除结点中“值等于给定值”的结点
删除指定指针指向的结点
代码实现单链表
复制代码
版权声明: 本文为 InfoQ 作者【测试人】的原创文章。
原文链接:【http://xie.infoq.cn/article/d9ee8aa89087f6f3b7ef62dfd】。文章转载请联系作者。
评论