链表 vs 数组

[juzhiyuan]

改自 https://www.studytonight.com/data-structures/linked-list-vs-array

链表 vs 数组

Array	Linked List
数组是相似类型元素的集合	链表是相同类型元素的有序集合，它们使用指针互相连接
数组支持随机访问，这意味着可以使用索引直接访问元素，如第一个元素是arr [0]，第七个元素是arr [6]等。因此，访问数组中的元素很快，时间复杂度为O（1）	链表支持顺序访问，这意味着访问链表中的任何元素/节点，我们必须顺序遍历完整的链表，直到该元素。访问有n个元素的链表，时间复杂度为O（n）。
在数组中，元素以连续的方式存储在存储器中。	分配给新元素的存储器位置地址存储在链表的先前节点中，从而形成两个节点/元素之间的链接。
在数组中，插入和删除操作需要更多时间，因为内存位置是连续且固定的。	在链表中，新元素存储在第一个空闲、可用的存储位置，只有一个开销步骤，即将存储位置的地址存储在链表的前一个节点中。
在编译时，一旦声明了数组，就会分配内存。 它也被称为静态内存分配。	在添加新节点时，在运行时分配内存。 它也被称为动态内存分配。
每一个元素都是独立的，可以通过索引来访问	每一个节点/元素都指向了下一个、上一个或双方节点
数组可以是一维、二维或者多维的	链表可以是单向的、双向的以及循环的
数组大小必须在声明时被指定	链表在运行时随着节点增减大小是可变的。
数组获取栈中分配的内存	链表从堆中获取内存