一 什么是链表?
一种包含当前节点值和指向下一个节点地址的数据存储结构。最后一个节点指向空值。
链表一般是分散存储在内存中,不需要连续地址。
二 链表的基本操作
链表一个节点结构如下
1 | class Node: |
1.增加元素分3种
1.1头部插入 时间复杂度O(1)
1.2尾部插入 时间复杂度O(n)
1.3中间插入 时间复杂度O(n)
2.删除元素分3种
2.1头部删除 时间复杂度O(1)
2.2尾部删除 时间复杂度O(n)
2.3中间删除 时间复杂度O(n)
3.遍历链表
从头节点开始,通过每个节点next的引用,可以从一个节点移动到另一个节点,当next指向空时,该节点为尾节点。
1 | class Node: |
链表反转
首先定义两个节点,cur,pre,
每次完成一次局部反转,直至尾节点。
1 | def reverse_listnode(head): |
小结:链表插入/删除的时间复杂度是O(n),是因为当要插入/删除某个给定值的节点时,需要遍历链表而引起的。
如果是频繁的插入,查询和遍历很少,可以采用链表存储数据。