链表的优缺点（请区分顺序表和链表的优缺点.）
本文目录
请区分顺序表和链表的优缺点.
顺序表 优点：可以随机访问，查找方便，没有空间浪费，适用于元素数目一定 或者较少的情况 缺点：分配的空间是固定的，元素个数不能超过预定的长度 链表 优点：可以动态分配空间，元素个数无限制，适用于元素数目变化较大 或者数目不确定的情况 缺点：有结构性开销（有空间浪费），查找不方便
简述顺序表和链表的优缺点和适用范围
顺序表
长度固定，必须在分配内存之前确定数组的长度。
存储空间连续，即允许元素的随机访问。
存储密度大，内存中存储的全部是数据元素。
要访问特定元素，可以使用索引访问，时间复杂度为 $O(1)$。
要想在顺序表中插入或删除一个元素，都涉及到之后所有元素的移动，因此时间复杂度为 $O(n)$。
顺序表最主要的问题就是要求长度是固定的，可以使用倍增-复制的办法来支持动态扩容，将顺序表变成“可变长度”的。
这个办法不可避免的会浪费一些内存，因为数组的容量总是倍增的。而且每次扩容的时候，都需要将旧的数据全部复制一份，肯定会影响效率。不过实际上，这样做还是直接使用链表的效率要高。
链表
长度不固定，可以任意增删。
存储空间不连续，数据元素之间使用指针相连，每个数据元素只能访问周围的一个元素（根据单链表还是双链表有所不同）。
存储密度小，因为每个数据元素，都需要额外存储一个指向下一元素的指针（双链表则需要两个指针）。
要访问特定元素，只能从链表头开始，遍历到该元素，时间复杂度为 $O(n)$。在特定的数据元素之后插入或删除元素，不涉及到其他元素的移动，因此时间复杂度为 $O(1)$。双链表还允许在特定的数据元素之前插入或删除元素。
静态链表
为了弥补链表在内存分配上的不足，出现了静态链表这么一个折中的办法。静态链表比较类似于内存池，它会预先分配一个足够长的数组，之后链表节点都会保存在这个数组里，这样就不需要频繁的进行内存分配了。
当然，这个方法的缺点是需要预先分配一个足够长的数组，肯定会导致内存的浪费。数组不够长到不是什么大不了的，使用第一节的动态扩容方法就是了。
静态链表一般是由两个链表组成，一个保存数据的链表，一个空闲节点的链表，如图 所示。
块状链表
块状链表则是链表和顺序表的结合体，将多个顺序表以链表连接起来，如图 4所示。
这种数据结构的优点是结合了顺序表和链表的优点，长度可变，而且插入、删除也比较迅速（不必移动全部元素，只需要移动某一个或几个块中的元素），时间复杂度约为 $O(\sqrt n)$，内存的占用也不会像链表那么多。
但是缺点也很明显，就是实现起来过于复杂，要想让时间复杂度达到 $O(\sqrt n)$，需要令块的个数和每块中存储的元素个数都接近 $\sqrt n$ 才行，这进一步限制了块状链表的应用。
STL 中的 deque 结构比较类似于块状链表，只不过它记录每一块使用的仍然是数组，而不是链表。同时 deque 只允许在两端进行插入和删除，实现上就容易很多。
参考资料
***隐藏网址***
链表存储的优缺点分别是什么
1、空间上。顺序比链式节约空间。是因为链式结构每一个节点都有一个指针存储域；
2、存储操作上。顺序支持随机存取，方便操作；
3、插入和删除上。链式的要比顺序的方便（这句话是不能这么说的，因为插入的话顺序表也很方便，问题是顺序表的插入要执行更大的空间复杂度，包括一个从表头索引以及索引后的元素后移，而链表是索引后，插入就完成了）
存储
存储，把钱或物等积存起来。《清会典事例·户部·库藏》:"户部奏部库空虚，应行存储款项。"
更多文章：
2024年5月20日 09:57
2024年7月3日 06:29
免费迅雷会员激活码（求一个迅雷会员激活码 一天的都行 体验码也可以 就用一天）
2024年6月21日 08:01
2024年5月20日 11:31
2024年5月25日 22:46
2024年7月23日 01:58
win10最适合打游戏的版本（win10玩梦幻哪个版本兼容）
2024年8月30日 06:55
2024年5月27日 01:58
极品飞车18手机版（极品飞车18 怎么玩 怎样才能得到好车 我怎么跑也不解锁车啊）
2024年6月28日 05:24
2024年5月29日 03:48
2023年9月17日 09:00
2024年3月31日 09:05
2024年5月6日 05:03
2024年7月2日 21:22
2024年7月18日 15:50
2024年2月18日 01:20
2024年7月1日 19:26
2024年6月9日 13:30
2024年5月17日 08:04
机器学习 为什么会使用梯度下降法？2、牛顿法和最速下降法只能求解无约束优化，有约束的非线性规划有哪些求解方法
2024年7月24日 12:18
