数组和链表总结

定义

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

访问方式

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

内存结构

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

插入&删除

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

内存分配

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

类型

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

依赖性

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

额外空间

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

示例图

• 数组

输入图片说明

• 链表

输入图片说明

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