您好，欢迎来到爱问旅游网。
科技 教育 生活 旅游 时尚 美容 美食 健康 体育 游戏 汽车 家电
搜索
您的当前位置：首页算法学习（2）--数组、链表和跳表的基本实现与特性

算法学习（2）--数组、链表和跳表的基本实现与特性

来源：爱问旅游网

一、数组

 

二、链表

  1. node，有单链表、双向链表、循环链表，pHead/pTail/构造函数。
  2. 增删不涉及群移操作，移动和修改操作的时间复杂度为O（1）。
  3. 访问元素节点的时间复杂度为线性复杂度O（n）。
  4. LRU cache利用链表。

 

三、跳表

  1. Skip List，只能用于元素有序的情况。
  2. 跳表对标的是平衡树AVL和二分查找，是一种插入/删除/搜索都是O（logn）的数据结构。
  3. 优势是原理简单、容易实现、方便拓展、效率高，在一些热门的项目中来替代平衡树，如Redis，LevelDB（Google，Jeff Dean）
  4. 跳表是一维数组升维实现的，在思考提升链表插座的效率的过程中，原链表如下：

建立第一级索引：

建立第二级索引：

建立多级索引：

5. 现实中跳表的形态

6.跳表查找的时间复杂度为O（logn）；增加和删除需要维护更新索引，时间复杂度为O（logn），空间复杂度为O（n）。

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

Copyright © 2019- awee.cn 版权所有 湘ICP备2023022495号-5

违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务