数组与链表的优缺点理解

数组字符串

1. 优缺点
   优点 :
   构建⼀个数组⾮常简单
   能让我们在 O(1) 的时间⾥根据数组的下标（index）查询某个元素
   //下标相当于内容的目录，通过目录可直接得值
   缺点 :
   构建时必须分配⼀段连续的空间
   查询某个元素是否存在时需要遍历整个数组，耗费 O(n) 的时间（其中， n 是元素的个数）
   //直接查找内容，需要遍历数组匹配，当查找的内容在数组的第一个时，最小时间复杂度为O(1)，当查找内容在数组的最后一个时，最大时间复杂度为O(n)
   删除和添加某个元素时，同样需要耗费 O(n) 的时间
   //这里指的是移动数组在数组中间添加内容，需要遍历数组移动下标和内容才能做到，当需要将内容元素作为数组的第一个，则需要将数组整体后移，最大时间复杂度为O(n)，不过平时都是在数组的末尾添加元素，时间复杂度为O(1)。需要注意的是，给数组赋值不属于删除或者添加元素，而对于unset($arr[$key])是通过下标删除元素，时间复杂度也是O(1)

链表

链表
1.优缺点
优点 :
灵活地分配内存空间
//链表为可变长度，可灵活分配内存空间
能在 O(1) 时间内删除或者添加元素
//链表的每个节点都有引用字段作为下一个节点的地址指向，因此在链表的任何一个位置添加或者删除元素，都可以直接存储或者删除内容和引用字段，只要修改插入或者删除位置的链表节点指向即可。如果不考虑插入、删除操作之前查找元素的过程，只考虑纯粹的插入和删除操作，时间复杂度都是O(1)。
缺点 :
查询元素需要 O(n) 时间
//通过链表直接节点内容，需要遍历链表匹配，这个和数组是一样的
不能通过下标快速查询元素
//链表的节点存储的是元素内容和地址指向，并没有下标的内容