线性-链表
定义
链表(Linked List)是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点或上一个节点的指针(Pointer)。
访问:O(n)
增删:O(1)
特点
增删O(1),查找O(n)
不用像数组那样预先分配存储空间的大小
无法进行回溯操作,如不能从尾节点倒序访问头节点
空间利用
不用预先知道数据大小,充分利用内存空间,可灵活管理内存
增加节点的指针域,空间开销较大
分类
单链表
双链表
循环链表
块状链表
存储结构
共享存储空间
优点:不需要提前分配内存,可存储无限多的内容
缺点:内容分散,不利于调试
独立存储空间(数组模拟链表):用表示在数组中的位置的下标索引代替了指向内存地址的指针,这种下标索引其实也是逻辑上的指针
优点:可以自动获得一个附加数据——唯一的编号,并且方便调试
缺点:不能动态分配内容,但是可以在上面加一层块状链表用来分配内存
用途
用于组织检索较少,而删除、添加、遍历较多的数据
应用与扩展
其他数据结构的基础:堆、栈、队列
基于多个线性链表:跳表
非线性链表:树、图
单链表
定义
包含两个域,一个信息域和一个指针域。节点的指针域指向链表中的下一个节点,而最后一个节点则指向一个空值。
访问
从一个节点开始(如root节点),通过指针域每次访问下一个节点,一直访问到需要的位置。也可以直接把一个节点的位置(指针)存储起来,以便下一次直接从该节点开始访问。
变形
最后一个节点指针指向头节点,可构成循环链表。或者在逻辑上实现:当访问到最后一个节点时,手动跳转到头节点。
题型
单链表反转
单链表反转
双链表
定义
每个节点有两个指针:一个指向前一个节点,(当此指针为第一个指针时,指向空值或者空列表);而另一个指向下一个节点,(当此指针为最后一个指针时,指向空值或者空列表)。
访问
双链表不仅有指向后一个节点的指针,还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点,当然也可以访问后一个节点,以至整个链表。
变形
尾节点指向下一个节点的指针指向头节点,头节点指向前一个节点的指针指向尾节点,构成循环链表。
题型
回文链表
循环链表
定义
首节点和末节点被连接在一起。第一个节点之前就是最后一个节点,反之亦然。
题型
判断链表是否有环
找到环中第一个节点
块状链表
定义
块状链表本身是一个链表,但是链表储存的并不是一般的数据,而是由这些数据组成的顺序表。每一个块状链表的节点,也就是顺序表,可以被叫做一个块。
各操作的时间复杂度为O(sqrt(n))
操作
定位:先定位元素所在的链表节点,然后再定位该元素在数组中的位置。
分裂:将某个链表节点分裂成两个节点。
插入:首先定位要插入的位置,然后将所在节点分裂成两个节点,并将数据放到第一个节点的末尾。 如果要插入的是一大块数据,首先要将数据切成多个block(每个block对应一个块状链表的一个节点)并将这些block链起来,然后将它们插入那两个节点之间。
删除:首先定位删除元素的位置,然后按照数组删除元素的方法删除该数据。如果删除一大块数据,首先要定位数据块首元素和末元素所在的位置,然后分别将它们所在的节点分裂成两个节点,最后删除首元素和末元素之间的节点即可
核心
确定链表长度和每个节点的数组长度,以及怎么保证这个长度值?设块状链表中元素总个数为X,链表长度为n,每个节点中数据长度为m,则当m=n=sqrt(X)
时,可保证m和n同时最小,此时各种操作的时间复杂度最低。在实际应用时,需维持块状链表的每个节点大小在[sqrt(n)/2, 2*sqrt(n)]
,否则,块状链表会退化。维护方法是,适当的时候,对节点进行合并与分裂(维护本身不会使复杂度增加)
参考
Last updated
Was this helpful?