双向链表

双向链表结构

image.png

双向链表和动态数组对比

• 动态数组
  开辟,销毁内存空间的次数相对较少,但可能造成内存空间浪费(可以通过缩容解决)
• 双向链表
  开辟,销毁内存空间的次数相对较多,但不会造成内存空间的浪费.
• 如果频繁的在尾部进行添加 删除操作,动态数组 双向链表均可选择.
• 如果频繁的在头部进行添加 删除操作,建议选择使用双向链表
• 如果频繁在(在任意位置)添加 删除操作,建议选择使用双向链表
• 如果有频繁的查询操作(随机访问操作),建议选择使用动态数组

Q:有了双向链表,单向链表是否就没有任何用处了?
A: 哈希表的设计就用到了单向链表