关于链表的插入效率

百度链表和顺序表的插入效率问题,总是说链表优于顺序表

........汗

链表插入删除的效率优于顺序表是有条件的:它不是单向链表

单向链表

如果你不知道要插入位置的元素的地址,那么它和顺序表的插入效率没有什么区别,这需要从链表的第一个元素开始遍历,然后找到插入位置之前的元素,然后让它的指针部分指向新的元素,将插入的元素的指针部分指向原先在这个位置的元素.

  如果已经知道要插入位置的元素地址,那么此时可以在插入位置的元素后面插入,然后将要插入位置的元素的数据和插入元素的数据对换.这时链表的插入效率才优于顺序表.

双向链表

由于双向链表可以通过指针找到插入位置的上一个元素,所以不管知不知道插入位置的元素地址,它的效率都优于顺序表

java的linkedlist正是一个双向链表.