计算机的线性表中有两种基本的存储方式：顺序存储和链式存储。顺序存储指的是用一段地址连续的存储单元依次存储数据；而链式存储中数据元素可以散乱的存储到存储单元中，每一个数据元素中包含数据项和下一个元素的存储地址。
通过二者的定义不难看出，顺序存储在查找时的时间复杂度为O(1)，因为它的地址是连续的，只要知道首元素的地址，根据下标可以很快找到指定位置的元素，而对与插入和删除操作由于可能要在插入前或删除后对元素进行移动，所以顺序存储的时间复杂度为O(n)。链式存储的特性则正好相反，在查找时需要从头元素逐个寻找，因此查找的时间复杂度为O(n),而对于插入和删除操作，由于只需要变更数据元素中下一元素的存储地址即可，因此时间复杂度为O(1)。
表面上看上面的说法没有什么问题，但其实在日常的使用中，比如要在数据集合的第i个位置插入或删除一个元素，要完成这样一个动作，使用顺序存储需要查找到元素然后执行插入或删除，时间复杂度为O(1)+O(n)=O(n);而链式存储同样需要先查找到元素然后在插入或删除，时间复杂度为O(n)+O(1)=O(n)。
所以说链式存储插入和删除的时间复杂度为O(1)的前提应该是已知元素当前的位置，否则实现在第i个位置插入或删除一个元素，顺序存储和链式存储的时间复杂度是一样的，都是O(n).
网友评论