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

线性表:

顺序线性表和链表

顺序线性表:

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

链表:

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

单向链表结构图:

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

file

双向链表结构图:

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

总结:

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 4

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

5年前 评论

@rayle 感谢指正,后期修复

5年前 评论

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

5年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!