数组在内存中存储是一段连续的内存空间,不可分开
查询过程:记下第一个元素所在的内存地址 比如在201这个内存地址中,而想要访问a[3],并且数组中存放的int,是为4byte,计算a[3]所在的内存地址为 201+4*4 然后直接去这个地址中取出对应的数据,时间复杂度为O(1)
链表由节点(node)组成,每个节点保存当前节点的值(value)和下一个节点的内存地址,所以节点可以分散在内存中的各个地方,通过每个节点的下一个节点这样连起来,
查询过程:当访问头节点,查看头节点中下一个节点的内存地址,再访问下一个节点,再到下一个节点中拿出下下个节点的内存地址,直到访问到的内存地址为0(一个无效值) 遍历结束,如果在最差的情况也就是要查找的数在最后一个节点,最多要经过的节点数为链表的长度n,所以时间复杂度为O(n)