网上报建贵州建设局网站,wordpress新用户下载权限,教育机构加盟,车墩做网站公司什么是链表
什么是链表#xff0c;链表是一种通过指针串联在一起的线性结构#xff0c;每一个节点由两部分组成#xff0c;一个是数据域一个是指针域#xff08;存放指向下一个节点的指针#xff09;#xff0c;最后一个节点的指针域指向null#xff08;空指针的意思链表是一种通过指针串联在一起的线性结构每一个节点由两部分组成一个是数据域一个是指针域存放指向下一个节点的指针最后一个节点的指针域指向null空指针的意思。 链表的入口节点称为链表的头结点也就是head。 如图所示
链表的类型
单链表 双链表
单链表中的指针域只能指向节点的下一个节点。 双链表每一个节点有两个指针域一个指向下一个节点一个指向上一个节点。 双链表 既可以向前查询也可以向后查询。 如图所示
循环链表
循环链表顾名思义就是链表首尾相连。
链表的存储方式
数组是在内存中是连续分布的但是链表在内存中可不是连续分布的。 链表是通过指针域的指针链接在内存中各个节点。 所以链表中的节点在内存中不是连续分布的 而是散乱分布在内存中的某地址上分配机制取决于操作系统的内存管理。 如图所示 这个链表起始节点为2 终止节点为7 各个节点分布在内存的不同地址空间上通过指针串联在一起。
链表的定义
class ListNode:def __init__(self, val, nextNone):self.val valself.next next链表的操作
删除节点
删除D节点如图所示 只要将C节点的next指针 指向E节点就可以了。 那有同学说了D节点不是依然存留在内存里么只不过是没有在这个链表里而已。 是这样的所以在C里最好是再手动释放这个D节点释放这块内存。 其他语言例如Java、Python就有自己的内存回收机制就不用自己手动释放了。
添加节点
如图所示 可以看出链表的增添和删除都是O(1)操作也不会影响到其他节点。 但是要注意要是删除第五个节点需要从头节点查找到第四个节点通过next指针进行删除操作查找的时间复杂度是O(n)。
性能分析
再把链表的特性和数组的特性进行一个对比如图所示 数组在定义的时候长度就是固定的如果想改动数组的长度就需要重新定义一个新的数组。 链表的长度可以是不固定的并且可以动态增删 适合数据量不固定频繁增删较少查询的场景。
参考https://programmercarl.com/
