✨✨所属专栏：数据结构✨✨
✨✨作者主页：嶔某✨✨
储存空间
我们知道顺序表的实质就是一个数组，数组的物理地址是连续的；而链表是由一个个的节点组成的，物理地址不一定连续、因为在malloc空间的时候不能保证，每次开辟的空间都与上次开辟的空间相邻。
随机访问（排序）
在随机访问的时候，顺序表可以直接使用数组的下标访问O(1)；而链表在随机访问时必须遍历链表O(n)。这导致了在排序的时候顺序表比链表便捷的多。（如果要用链表排序还不如copy到数组那排完了在copy过来）
任意位置插入删除
链表在插入删除的时候只需要删除对应的节点就行，
void LTPopBack(LTNode* phead)//尾删
{assert(phead && phead->next != phead);//第二个很容易忽视！LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}void LTPopFront(LTNode* phead)//头删
{assert(phead && phead->next != phead);LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}void LTErase(LTNode* pos)//任意位置删除
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
但是顺序表在插入删除时可能需要将整体元素向前或向后移动，就非常麻烦。
void SeqListPushFront(SLT* ps, SQDataType x)
{SeqListCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->data[end + 1] = ps->data[end];//整体移动end--;}ps->data[0] = x;ps->size++;
}插入扩容
顺序表经常会有空间不够的时候，这时候就需要扩容了，每次扩容的时候都会产生一定的消耗，有时扩容还有可能会多扩（原来有100个空间，扩到了200个，但最终只使用了120个空间）这就导致了空间的浪费。
而链表几乎没有空间的概念，每一个元素都是独善其身的，只有prev和next指针与其他元素有联系，插入元素时只需要新malloc一块空间即可。
缓存利用率
https://coolshell.cn/articles/20793.html
https://coolshell.cn/articles/20793.html
上面链接的文章提到了缓存的命中这个概念，由于顺序表是连续的，在访问一个数据时，计算机会将这个数据后面地址的元素一起拖到CPU，万一后面的元素我们之后恰好也要访问，这就省去了不少CPU的负担。
但链表每个元素的地址不一定连续，所以当计算机连同后面的信息一起拖过去，但CPU不访问后面的元素，这就为CPU增加了负担。
缓存命中本是为了减少CPU的负担，但由于链表的特殊结构适得其反。
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连 续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 任意位置插入或者删除元 素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩 容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
本期博客到这里就结束了，如果有什么错误，欢迎指出，如果对你有帮助，请点个赞，谢谢！
