线性表

特点

• 唯一一个头节点
• 唯一一个尾节点
• 除头节点外，均只有一个前驱节点
• 除尾节点外，均只有一个后继节点

顺序表

插入平均移动步数    n/2

删除平均移动步数   (n-2)/2

查找时间代价        O(n)

二分查找时间代价    O(log₂n)

适合整块存储有序数据，不适合频繁插入删除以及动态扩展。

链接表

查找时间代价 O(n)

适合频繁增删的零散数据，不适合快速查找。

常见类型：单链表、循环链表、双链表、循环双链表。

注意：带头节点和不带头节点的区别。