移动链表元素和数组开销不一样吗》

http://www.1point3acres.com/bbs/ ... &fromuid=107278

2.4 Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

原作者有句话说如果是数组那么开销会巨大，why?

不是移动的开销，而是不断开辟新空间的开销。数组和链表在速度上的差距很小。甚至可以说没有。但是空间上，数组需要开辟连续的内存，但是链表是不需要的。

链表每次移动都是O(1)时间，但如果是数组的话你把后边一个元素移到前边需要把这之间的所有元素后移来腾地方，所以是O(n)的时间（如果要保持相对顺序的话是这样，如果无需保持，则像快排那样直接交换也可，那就是O(1))。所以数组开销会更大一些。