6.线性表：顺序表和链表的优缺点

柔情只为你懂 2023-10-13 10:16 65阅读 0赞

线性表分为顺序表和链表，链表又分为单链表，双向链表和循环链表。对于链表的结构又分为带头链表和不带头链表。

## 一、顺序表 ##

1、定义：

将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。采用顺序存储结构的线性表简称为“ 顺序表”。

2、特点：

1）存储空间连续，即允许元素的随机访问。

2）长度固定，必须在分配内存之前确定数组的长度。

3、优点：

1）便于随机访问。

2）cpu缓存利用率高。

3）顺序表的内存空间连续。

4）尾插、尾删效率较高，时间复杂度是O(1)。

5）支持随机访问，可以高效的按下标进行操作，时间复杂度是O(1)。

4、缺点：

1）不便于插入删除等操作，因为插入删除一个元素需要移动其后的所有元素，因此效率较低，时间复杂度为O(N)。但是在末尾插入或删除数据比较方便。

2）顺序表长度固定，有时需要扩容。

5、适用情况：一般尾插，尾删多的用顺序表和需要大量访问元素的 而少量增添/删除元素的程序。

## 二、链表 ##

![6adc4a50107d4990baaaa5d33ae4083e.png][]

1、链表分类：

1）单链表是只包含指向下一个节点的指针，只能单向遍历。

2）双链表即包含指向下一个节点的指针，也包含指向前一个节点的指针，因此可以双向遍历。

3）循环单链表则是将尾节点与首节点链接起来，形成了一个环状结构。

2、特点：

1）长度不固定，可以随意增删改。

2）存储空间不连续，数据元素之间靠指针联系。

3）不支持随机查找。

4）在特定的数据元素之后插入或删除元素，不涉及到其他元素的移动。

3、优点：

1）链表的内存空间不连续。

2）如果知道要处理节点的前一个位置，则进行插入和删除的复杂度为O(1)。

3）如果不知道要处理节点的前一个位置，则进行插入和删除的复杂度为O(N)。

4）头插、头删的效率高，时间复杂度是O(1)。

5）没有空间限制，不会溢出，可以存储很多元素。

4、缺点：

链表不支持随机访问，查找元素效率低，需要遍历节点，时间复杂度是O(n)。

5、适用情况：

适用于需要进行大量增添/删除元素操作 而对访问元素无要求的程序。

## 三、总结 ##

1、当线性表的长度变化不大、易于确定其大小时，采用顺序表作为存储结构。

2、若线性表主要操作是查找。很少进行插入或删除操作时，采用顺序表作为存储结构。

3、对于频繁进行插入和删除的线性表，则应该使用链表作为存储结构。

**上一章：**

[5.线性表：顺序表与链表\_IT小悟的博客-CSDN博客本章主要介绍线性表的定义，线性表的顺序存储和链式存储，线性表的前驱和后继。以及顺序表(顺序存储结构)与链表（单链表），顺序表与数组的关系和区别和顺序表与链表（单链表）的基本操作。![favicon32.ico][]https://blog.csdn.net/speedwalkman/article/details/131501356][5._IT_-CSDN_favicon32.ico_https_blog.csdn.net_speedwalkman_article_details_131501356]**下一章：**

[7.线性表：实现单链表的各种操作\_IT小悟的博客-CSDN博客本章节主要介绍单链表的各种操作，主要包括， 单链表的增加节点、删除节点、排序、打印、计算长度，删除重复数据，找到倒数第k个元素，实现链表的反转，从尾到头输出链表，找到中间节点，检测链表是否有环，快慢指针移动判断，使用Set集合记录Node元素，如果有重复元素则认为有环，如果链表有环，找到有环的入口点是哪个节点，在不知道头指针的情况下删除指定节点，如何判断两个链表是否相交并找出相交节点。![favicon32.ico][]https://blog.csdn.net/speedwalkman/article/details/131527006][7._IT_-CSDN_ _k_Set_Node_favicon32.ico_https_blog.csdn.net_speedwalkman_article_details_131527006]

[6adc4a50107d4990baaaa5d33ae4083e.png]: https://img-blog.csdnimg.cn/6adc4a50107d4990baaaa5d33ae4083e.png
[favicon32.ico]: https://g.csdnimg.cn/static/logo/favicon32.ico
[5._IT_-CSDN_favicon32.ico_https_blog.csdn.net_speedwalkman_article_details_131501356]: https://blog.csdn.net/speedwalkman/article/details/131501356
[7._IT_-CSDN_ _k_Set_Node_favicon32.ico_https_blog.csdn.net_speedwalkman_article_details_131527006]: https://blog.csdn.net/speedwalkman/article/details/131527006