将数组放入链表遍历链表与数组，哪个效率高？

2021-03-16

2969

遍历链表与数组，哪个效率高？因为O（n）的内涵不同，他们是写O（n）和读O（n）。数组善于读取，链表善于写入。写入前读取位置。读取场景：任意顺序读取，复杂度：数组o（1），链表o（n）。写入场景：按任

遍历链表与数组，哪个效率高？

因为O（n）的内涵不同，他们是写O（n）和读O（n）。

数组善于读取，链表善于写入。

写入前读取位置。

读取场景：任意顺序读取，复杂度：数组o（1），链表o（n）。

写入场景：按任意顺序写入，位置复杂度：数组o（1），链表o（n）；写入复杂度：数组o（n），链表o（1）。

在写入场景中，数组链表的复杂度是位置写入复杂度的总和，即O（n），但是写入速度比位置O（n）慢得多，并且具有相同表面的两个O（n）的实际时间仍然少得多。因此，链表和数组的插入和删除时间复杂度为O（n），链表写入效率高。