写点什么

软件测试 / 测试开发丨 Python 学习笔记 之 链表

作者:测试人
  • 2023-08-30
    北京
  • 本文字数:556 字

    阅读完需:约 2 分钟

免费领取:测试资料+测试用例+简历模板+测试文档

本文为霍格沃兹测试开发学社学员学习笔记分享

原文链接:https://ceshiren.com/t/topic/26458

链表与数组的区别

  • 复杂度分析


  • 其他角度分析内存连续,利用 CPU 的机制,可以预读链表中的数据,故访问效率高而数组在内存中并不是连续存储的,所以 CPU 缓存不友好,没办法预读数组的大小不固定,及时动态申请,也需要拷贝数据,费时费力链表支持动态扩容链表的缺点是:存储空间大


单链表和循环链表

  • 区别在于头结点与尾结点是否相连

  • 循环链表从尾部可以直接到达头,适合环形数据结构,比如约瑟夫问题

双向链表优点

  1. 找到上一个结点的时间复杂度为 O(1)

  2. 插入、删除操作更高效

  3. 删除结点中“值等于给定值”的结点

  4. 删除指定指针指向的结点

代码实现单链表

# 链节点类class ListNode:    def __init__(self, val):        self.val = val        self.next = None

# 链表类class LinkedList: def __init__(self): self.head = None
# 根据 data 初始化一个新链表 def create(self, data): self.head = ListNode(0) cur = self.head for i in range(len(data)): node = ListNode(data[i]) cur.next = node cur = cur.next
# 获取链表长度 def length(self): count = 0
复制代码


发布于: 刚刚阅读数: 4
用户头像

测试人

关注

专注于软件测试开发 2022-08-29 加入

霍格沃兹测试开发学社,测试人社区:https://ceshiren.com/t/topic/22284

评论

发布
暂无评论
软件测试/测试开发丨Python 学习笔记 之 链表_Python_测试人_InfoQ写作社区