Question

数据结构中链表优势问题

说链表较于顺序表的优势有一个是便于插入和删除，链表时间复杂度也是O（n），（若要对最后一个数进行操作），线性表也是O（n），为什么说方便插入删除呢？
ps：我们学的链表的插入操作是
j=0;
while(p||j<i-1)
{
p=p->next;
j++;
}
其中i为插入位置。

Answer 1

插入操作：
对于顺序表（数组实现），插入元素前，需要把插入位置之后的所有元素往后移动一遍，最好的情况，在表尾插入，最糟糕的情况，在表头插入，需要移动n个元素，所以麻烦。
对于链表，只需要找到插入位置，然后新建节点，改一下指针指向的节点就完事了，不需要移动元素，所以方便。
删除操作：
对于顺序表，删除一个元素后，该位置就空了，需要把这个被删除元素之后的所有元素往前移动一遍，最好情况，删除表尾元素，最坏情况，删除表头元素，需要移动n-1个元素。
对于链表，只需要先修改一下指针，然后删除需要删除的元素所在的节点就完事了，也不用移动元素。
最后，时间复杂度是渐近计算的，平均时间复杂度是最好情况+最坏情况的平均值，而非特殊情况（如你所说的对表尾元素操作）。
你的代码是指针顺着不停的往下一个元素走，直到找到插入位置为止。计算时间复杂度不仅仅是看指针跑了多少次，也不仅仅是看访问了多少个元素。一个长度为n的顺序表和一个长度为n的链表，如果要在第i个位置插入元素，顺序表的操作是：寻找插入位置（访问i次），然后把i+1到n的元素往后移动一个位置（访问（n-i）+（n-i-1）+（n-i-2）...+1 = （n-i+1)/2次）；链表的操作：寻找插入位置（访问i次），然后就插入节点。所以当然是链表方便插入啦，删除也一个道理。

追问

线性表访问的时候不需要寻找啊，a[i]不就是第i个了吗

追答

...你概念混乱了，线性表分顺序表和链表，我写了啊，不论是链表还是顺序表，访问都是必须的啊。