数据结构--数组、单向链表、双向链表
0

线性表:

顺序线性表和链表

顺序线性表:

  1. 就是数组(c语言),初始化固定数组的大小,申请连续的内存分配。
  2. 可能面临的问题有:数组边界溢出,不够存,需要重新申请新的连续的内存空间,造成内存浪费,性能下降,拓展性差。
  3. 数组实际大小可能没有等于初始化定义的,也造成内存浪费。
  4. 但是相对链表来说,数组的优点是通过数组下标可以快速找到数据的内存地址,查找效率高(o(1)),但是相反,插入和删除数据,后面的数据都要进行移动,效率低(o(n))。

链表:

  1. 分为单向链表、双向链表、循环链表等。
  2. 跟数组最大的不同的是,链表是不连续的内存,其利用的是整合碎片内存空间起来组成一个链表,合理利用和节约了内存空间,提高性能。
  3. 数据变动不会受到类似数组边界等限制,动态能力比较高,拓展性好。
  4. 单向链表查找数据的效率需要从表头一步一步的往下找,查找效率低(o(n))。
  5. 双向链表就是为了解决查找效率问题而诞生的,其可以从链表的任何一个位置从两边开始寻找,使用二分法查找的效率明显提高了,查找效率最高的还是数组。
  6. 双向链表比单向链表多了一个属性,来指向上一个节点的地址,其查找效率是用过牺牲空间换时间的做法。
  7. 链表的插入和删除效率(o(1))比数组高,因为它不涉及到后面整组数据的变动,只需要前或者前后的指向属性做修改就可以了。

单向链表结构图:

用面向对象的思想就是有两个属性,一个是值,一个是指向。末尾的指针指向空值

file

双向链表结构图:

有三个属性,一个是值,一个是前一个节点的指针 ,一个是下一个节点的指针,前后的指针指向空值
file

总结:

《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 4

哥, 不要误导人, php数组是hashTable

3个月前
motecshine

php7 是 ZEND_ARRAY

3个月前
VankeGabe

@rayle 感谢指正,后期修复

3个月前
VankeGabe

@Noober Phper 感谢指正,后期修复

3个月前

  • 请注意单词拼写,以及中英文排版,参考此页
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`, 更多语法请见这里 Markdown 语法
  • 支持表情,使用方法请见 Emoji 自动补全来咯,可用的 Emoji 请见 :metal: :point_right: Emoji 列表 :star: :sparkles:
  • 上传图片, 支持拖拽和剪切板黏贴上传, 格式限制 - jpg, png, gif
  • 发布框支持本地存储功能,会在内容变更时保存,「提交」按钮点击时清空
  请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!