专栏首页九州牧云数组和链表总结

数组和链表总结

定义

  • 数组是具有相同数据类型的元素的集合
  • 链表是由链接/指针连接的元素的有序集合

访问方式

  • 在数组中,可以使用索引/下标值来访问元素,即元素可以被随机访问,比如arr[0]、arr[3]等,因此数组提供快速和随机访问。
  • 在链表中,元素不能随机访问,只能按顺序访问,访问元素需要花费O(n)时间

内存结构

  • 在数组中,元素以连续的方式存储在内存中
  • 在链表中,元素可以存储在任何可用的地方,节点的地址存储在以前的节点中

插入&删除

  • 因为元素存储在连续的内存位置,在数组中插入和删除需要更多的时间,每次操作都需要移动元素
  • 插入和删除在链表中是快速和容易的,因为只需要改变指针的值

内存分配

  • 在数组中,在编译时分配内存,即静态内存分配
  • 在链表中,内存在运行时分配,即动态内存分配

类型

  • 数组可以是单维的,二维的或多维的
  • 链表可以是单端链表、双端链表或循环链表

依赖性

  • 在数组中,每个元素都是独立的,与以前的元素或位置无关
  • 在链表中,元素的位置或地址存储在前一个元素/节点的链接部分

额外空间

  • 在数组中,没有使用类似链表的指针,因此不需要内存中的额外空间来存放指针
  • 在链表中,元素之间使用指针或链接来维护,因此使用指针,并且需要额外的内存空间

示例图

  • 数组
  • 链表

编译自:Difference between Array and Linked List | Array vs. Linked List

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 常用 Git 命令清单

    一般来说,日常使用只要记住下图6个命令,就可以了。但是熟练使用,恐怕要记住60~100个命令。

    九州暮云
  • Java命令学习系列(三)——Jmap

    jmap是JDK自带的工具软件,主要用于打印指定Java进程(或核心文件、远程调试服务器)的共享对象内存映射或堆内存细节。可以使用jmap生成Heap Dump...

    九州暮云
  • Java 性能要点:自动装箱/ 拆箱 (Autoboxing / Unboxing)

    如果我告诉你:“只要修改一个字符,下面这段代码的运行速度就能提高5倍。”,你觉得可能么?

    九州暮云
  • 数组和链表的区别

    数组: 数组是将元素在内存中连续存放,由于每个元素占用内存 相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内...

    猿人谷
  • 程序面试题之我见

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    用户2615200
  • 2018-06-13 关于Java集合的小抄

    Albert陈凯
  • 数据结构学习笔记——线性表(下)

    了解过线性表的链式存储结构以后,有人就想出来用数组来代替指针,来描述单链表。看看他们是怎么做到的。

    蜻蜓队长
  • 【从0到1学算法】 数组和链表

    今天讲最基本的数据结构,数组和链表。如果你已经滚瓜烂熟,可以跳过本文或选择查缺补漏。

    KEN DO EVERTHING
  • (美团)巧用数组下标,轻轻松松找出所有元素

    今天分享的算法题和 数组 这个数据结构有关,如果你不了解数组的特点,你百分百无法想到它的解法。

    五分钟学算法
  • 关于Java集合的小抄

    在尽可能短的篇幅里,将所有集合与并发集合的特征,实现方式,性能捋一遍。适合所有”精通Java”其实还不那么自信的人阅读。

    哲洛不闹

扫码关注云+社区

领取腾讯云代金券