举例说明相同的逻辑结构采用不同存储方式影响其执行效率

顺序表和链表都是线性表，这是他们的共同之处（逻辑结构相同），但它们的存储方式是不同的。那就看看在顺序表和链表中运算效率是怎样产生不同的？

线性表既可以采用顺序存储方式，也可以采用链式存储方式来实现。

一、顺序存储方式

在线性表中插入和删除元素，平均要移动一半的元素，时间复杂度是O(n)。

事实上，就是在数组中进行增删操作。

例如：下面的数组存放了n个元素，若要在末尾插入一个元素，只要顺序表有足够的空间，就可以通过数组的下标号索引到数组的n+1个位置，直接将元素插入到里面，这只要花费O(1)的时间复杂就可以了。但是，这是一种特殊的情况。但若要在数组的头部插入元素一个元素，会影响到后面的元素，那么这些元素都会统一的依次往后面移动一个位置，给第一个位置要插入的元素空出一个单元格。这样会移动n个元素，消耗的时间复杂度为O(n)。同理，删除操作也便如此。

小结：顺序表插入和删除操作，在头部n次操作，在尾部一次操作，就平均而言，需要n/2次操作。

二、链式存储方式

例如，在下面的单表中，链接了n个结点。在这里我们不考虑每次都要从头结点重新遍历一遍。譬如，要在单链表的末尾插入一个n+1结点，就是在找到N结点后，直接链接N+1这个结点，而不是重头找一遍。这个过程的时间复杂度为O(1)。同理，删除一个结点操作的时间复杂度也是O(1),直接把链接箭头断开就可以了。

小结：单链表，插入和删除操作的时间复杂度为O(1)。在这里没有考虑查找这一过程。