数据结构-链表（3）

前言

学习了顺序表和链表，这篇博客目的就是分析理解1、顺序表和链表的优缺点，2、单链表和有头（带头）双向循环链表的区别，3、链表中对于带头的理解、4、链表中对指针的理解。代码问题请看前几篇数据结构博客。

理解

一、顺序表和链表分类

二、顺序表和链表的优缺点

1、静态顺序表和动态顺序表

@ 静态顺序表

• 优点：空间连续，支持随机访问
• 缺点：空间固定，不能增容

@ 动态顺序表

说明：
1、插入数据时空间不够了，可以增容
2、要求数据是依次存储的

• 优点
  1、空间连续，支持随机访问
  2、支持增容

• 缺点
  1、增容时一次性开辟大的空间，可能会浪费内存
  2、开头或中间左右插入删除效率低，时间复杂度为O(N)

2、动态顺序表和链表

@ 动态顺序表

• 优点： 空间连续，支持随机访问

• 缺点：
  1、空间浪费大，申请空间以2倍空间的方式开辟空间
  2、插入删除效率低，头部或中间的插入删除需要移动数据

@ 链表

• 优点：
  1、按需索取空间，空间浪费小
  2、空间不连续，不需要挪动数据
  3、可以实现插入删除时间复杂度均为O(1)

• 缺点：空间不连续，不支持随机访问

三、链表中带头以及指针的理解

& 单链表（一级指针）：

& 单链表（二级指针）：

& 带头双向循环链表（一级指针）：

四、单链表和带双循链表的区别

1、初始化

• 单链表：不需要用Init函数去完成初始化，
• 带头双向循环链表：需要Init函数使用二级指针或者返回一级指针创建链表的头完成初始化

2、时间复杂度

• 单链表：PushFront、PopFront是O(1)，而PushBack、PopBack、Insert、Erase都是O(N)
• 带头双向循环链表：插入删除全是O(1)
• 至于查找、修改，二者都一样

3、指针

• 单链表：需要修改链表时必须用二级指针操作
• 带头双向循环链表：除了Init，各功能都可以用一级指针实现

4、函数复用

• 单链表：Insert可以实现头插，指定插，但不能实现尾插，Erase可以实现头删、尾删、指定删
• 带头双向循环链表：Insert可以完成任意位置插入，包括尾插，Erase可以完成任意位置删除