数组和链表的联系和区别

数组和链表的联系和区别 一，什么是数据结构：

简单理解就是研究数据的存储方式，合理的组织数据，高效的处理数据。

二，链表

• 物理存储单元上非连续、非顺序
• 由结点组成，通过指针联系
• 不需要一块连续的内存空间，通过指针将一组零散的内存块串联起来使用

• 存储n个结点消耗的空间：n+m=2n。链表的每个节点除了存储数据(n)外还需要存储下一个节点地址-指针域所占存储量m

• 如果要找数据为3的结点(数据为3存储的位置不一定为3)，需要从头开始遍历寻找直到找到为止----地址是无序的–非顺序性。

• 每个元素的查找都要从头开始遍历，时间复杂度为O(n)–n为要查找的元素的节点的位置。

三，数组 

• 对应链表的连续、顺序

• 需要一块连续的内存空间来存储

• (Java中int型大小占4个字节)，由于元素在内存中是连续紧邻分配的，大小一样–方便查找，查询的速度比链表快。

• 通过下标找到相应的内存地址，从而进行访问。第一个元素的地址+元素下标×字节数。

• • 假设初始地址为100，查找第三个元素的地址：100+2×4=108。每个数据的地址都是有序的–顺序性。

  • 查找时间复杂度为O(1)：因为通过计算得出地址，通过地址进行访问，无论数据多大，都是计算完直接访问，所以为1。

• 存储n个结点消耗的内存：数组的容量n

假如要存储n个节点 数组和链表消耗的空间 各是多少
数组容量->n

链表 n+m->(x*n) =>(类似)2n

m是节点后面指向下一个地址 这些占据了多少空间 x是一个这种占据的空间 实际是1
所以最后类似 2n

实际上最后一个节点的空间也是占用了的 因此创建链表的时候 最后一个节点也要去指向Null

至于为什么不 把最后一个删了

如果要删除 我们每加一个节点要判断是不是最后一个节点每次判断消耗的成本和那么一个小小空间相比

并且如果最后一个没节点 管理起来 也会很费劲 所以就空着不用 也方便后续的增添