顺序表和链表的比较

2021-06-11 本文已影响0人 TPEngineer

都是线性表，即线性结构。

顺序表按照顺序存储，支持随机存取，存储密度高。不过改变容量很麻烦。

链表离散的存储，改变容量容易，但是不能随机存取，存储密度低。

$！初始化$

顺序表初始化时需要预分配空间，其中静态分配是不能改变容量的，这种分配方式比较少见，常用的是动态分配，可以改变容量，不过需要移动大量元素，时间代价很高。

而链表之需要分配一个头节点，很方便。

$！删除$

顺序表静态分配的数组系统会自动回收，无需操心。但是动态分配的数组则需要手动free。

而链表删除节点需要手动free。

$！查找$

顺序表查找的时间复杂度可以控制到 $O(\log_2 n )$ ，不过链表只能控制到 $O(n)$ 。