数据结构_顺序表(动态)和链表(带头双向循环)的区别

✨✨所属专栏：数据结构✨✨

✨✨作者主页：嶔某✨✨

储存空间

我们知道顺序表的实质就是一个数组，数组的物理地址是连续的；而链表是由一个个的节点组成的，物理地址不一定连续、因为在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.htmlhttps://coolshell.cn/articles/20793.html

上面链接的文章提到了缓存的命中这个概念，由于顺序表是连续的，在访问一个数据时，计算机会将这个数据后面地址的元素一起拖到CPU，万一后面的元素我们之后恰好也要访问，这就省去了不少CPU的负担。

但链表每个元素的地址不一定连续，所以当计算机连同后面的信息一起拖过去，但CPU不访问后面的元素，这就为CPU增加了负担。

缓存命中本是为了减少CPU的负担，但由于链表的特殊结构适得其反。

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低