线性结构

线性结构

线性表是具有 n 个相同类型元素的有限序列

常见的线性表

1. 顺序表:

   • 动态数组
     • 数组是一种顺序存储的线性表, 所有元素的内存地址都是连续的;
     • 开辟,销毁内存空间的次数相对较少,但可能造成内存空间浪费(可以采取缩容机制)

2. 链表:

   • 单链表
     • HashMap中用到了单链表
   • 双链表
     • 开辟,销毁内存空间的次数相对较多,但不会造成内存空间浪费
   • 循环链表
   • 静态链表

3. 栈:

   • 只能顶部入栈,顶部出栈

4. 队列:

   • 顺序队列
   • 双端队列
   • 循环队列

双链表vs动态数组

如果频繁在尾部进行添加,删除操作, 选择动态数组
如果频繁在头部进行添加,删除,使用双链表
如果有频繁的任意位置的添加,删除,选择双链表
如果频繁的查询,选择动态数组