数组、单链表、双链表的关系区别

原创
2019/04/07 15:04
阅读数 122

数组:

  1. 静态分布内存
  2. 根据下标定位元素
  3. 查找的时间复杂度为O(1),插入或删除的时间复杂度为O(N)
  4. 初始化数组需要规定数组大小,不能扩展

 

数组优点:

  1. 查找速度相较于链表更快
  2. 随机访问性更强,无序遍历,直接访问table[i]可快速定位

 

 

数组缺点:

  1. 删除或插入的速度更慢
  2. 由于数组大小是初始化时规定的,可能不能充分利用完全,容易造成内存浪费
  3. 需要连续的内存空间,且剩余内存必须足够大。对内存要求较高

 

 

 

链表:

  1. 动态分布内存
  2. 通过指针定位下位元素,单链表为next()方法,双链表除了next()方法外还有pre()方法定位上一位元素
  3. 插入或删除的时间复杂度为O(1),查找的时间复杂度为O(N)
  4. 链表的长度是动态扩展的

 

 

链表的优点:

  1. 插入的速度相较于数组更快
  2. 由于链表长度动态扩展,所以能充分利用内存,不会存在内存浪费

 

 

链表的缺点

  1. 查找的速度更慢一些
  2. 不支持随机访问

 

 

 

单链表常见于双链表的原因

 

双链表由于相较于单链表每个元素多了一个向前的指针,所以占用的存储空间更大,一个指针占用的内存空间在64位系统是8个字节,n个字节就需要多8*N个内存消耗。内存浪费严重

LinkedList是双向链表

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部