数据结构：线性表中线性表与链表的区别

Love The Way You Lie 2023-02-13 08:57 58阅读 0赞

##  ##

1.  ## 线性表与单链表的区别 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE_size_16_color_FFFFFF_t_70]

> ## 结论： ##
> 
> 使用到的线性表需要频繁查找时，使用线性表结构；  
> 频繁插入和删除是，采用单链表结构
> 
> ## 补充说明： ##
> 
> 线性表的元素地址是连续的。  
> 链表里的地址是不连续的，是通过指针联系起来的。

PS：线性表是逻辑结构，各个元素存储的先后位置反映逻辑上的线性关系。  
单链表是线性结构，是靠指针来反映这种关系的。  
![线性表中各存储类型的区分][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE_size_16_color_FFFFFF_t_70 1]

2\#\#

## 2.1 顺序存储： ##

> 顺序表，使用数组实现，是一组连续的存储单元，数组的大小有静态分配与动态扩展两种方式。 值得注意的是线性表是从1开始，而数组是从0开始。
> 
> > 优点：随机访问特性，查找O(1)时间，存储密度高；逻辑上相邻的元素，物理上也相邻；
> 
> > 缺点：插入删除需移动大量元素。
> 
> 顺序表相关的操作跟数组有关，一般都是移动数组元素。

## 2.2 单链表 ##

> 使用任意存储单元来存储线性表中的数据元素，节点类型如上。
> 
> 单链表分为带头结点和不带头结点两种，不管有没有头结点，头指针都指向链表的第一个节点（有头结点指向头结点）。
> 
> 头结点：数值域可不设任何信息，头结点的指针域指向链表的第一个元素。
> 
> 带头节点的好处有：
> 
> > （1）链表第一位置节点上的操作和其它位置上的操作一致
> 
> > （2）无论链表是否为空，头指针都指向头结点（非空），空表和非空表处理一样
> 
> 注：链表麻烦的地方是插入和删除时指针的修改，保证不断链，一般先断后链。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200528111912381.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200528112458481.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmJlaTE=,size_16,color_FFFFFF,t_70