面试中遇到关于LinkedList和ArrayList的逆序问题，请大家帮忙

Question

前天面试的时候，被问到这样的问题：可以使用Collections.reverse()方法对LinkedList和ArrayList进行逆序，谁的效率高？

Answer 1

从数据结构的角度来看LinkedList应该快一点至于这个方法的实现要去看看源码了

Answer 2

凭感觉是LinkedList效率高，修改引用即可。ArrayList应该会牵涉到交换操作

Answer 3

sorce来了，确实ArrayList是有交换操作，看swap(list, i, j);方法    public static void reverse(List<?> list) {
        int size = list.size();
        if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
                swap(list, i, j);
        } else {
            ListIterator fwd = list.listIterator();
            ListIterator rev = list.listIterator(size);
            for (int i=0, mid=list.size()>>1; i<mid; i++) {
Object tmp = fwd.next();
                fwd.set(rev.previous());
                rev.set(tmp);
            }
        }
    }

Answer 4

从我的实验，以及6F的代码来看，都应该是ArrayList，虽然和我的第一感觉相反。
    int length = 1000000;
    List<Integer> list = new ArrayList<Integer>(length); // or new LinkedList<Integer>();
    for (int i = 0; i < length; i++) {
      list.add(i);
    }
    long start = System.currentTimeMillis();
    for (int i = 0; i < 100; i++) {
      Collections.reverse(list);
    }
    long end = System.currentTimeMillis();
    System.out.println(end - start);ArrayList在我的电脑上平均在4秒左右，而LinkedList在5秒左右@Justlearn，ArrayList用Swap，其实LinkedList也是Swap，次数都是 size/2 次（每次一对）
但是，由于ArrayList只是简单的i++,j--，并调用set方法（基本上就是引用数组下标），而LinkedList基于两个ListIterator，且每次都必须调用fwd.next(), fwd.previous()，这两个操作本身就已经包含了iterator指针的swap操作 public E next() {
    checkForComodification();
    if (nextIndex == size)
throw new NoSuchElementException();     lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.element;
} public E previous() {
    if (nextIndex == 0)
throw new NoSuchElementException();     lastReturned = next = next.previous;
    nextIndex--;
    checkForComodification();
    return lastReturned.element;
}由于这里没有涉及到插入，而逆序对于两者都是要对所有元素的位置/指针进行调整，所以ArrayList的速度并不慢。不知分析的有没有纰漏。

Answer 5

我运行结果是ArrayList 2120 LinkedList 2300

Answer 6

看来是主观上夸大了swap的所消耗的时间，其实这里的swap只有length/2，并不像插入删除时候

Answer 7

Arraylist允许我们快速访问，但从列表中部插入和删除元素却不如linkedlist,而Linkedlist却相反

Answer 8

LinkedList快，完全的指针移动，数组完成的是值移动。

Answer 9

LinkedList快，完全的指针移动，数组完成的是值移动。

Answer 10

建议认为LinkedList快的，都尝试一下我的代码，如果你们发现确实LinkedList，也请告诉我。

Answer 11

http://edu.xvna.com/html/19290.html
or google
java arraylist linkedlist reverse performance

Answer 12

学过数据结构的都知道应该是 Linkedlist快，链表逆转 只需要修改引用指向，但是数组，这样连续区域的 逆转，需要交换移动元素，开销肯定大。

Answer 13

ArrayList底层是数组，操作起来复杂度要高些

Answer 14

LinkedList 的底层是二叉树查找慢，增、删、改快，而ArrayList底层结构是数组，查找快，增、删、改慢

Answer 15

顶了，虽然和自己的想法相反，但还是对Arraylist有了更多的了解！
谢谢lz提这个问题。也谢谢高手的分析。

Answer 16

LinkedList 查慢改快
ArrayList  查快改慢逆序的话个人理解是linkedList快

Answer 17

Array一个查快改慢
link查慢改快
我觉得是linkedlist效率高

Answer 18

ArrayList查快写慢，逆序也快一点。

Answer 19

public static void reverse(List<?> list) {
        int size = list.size();
        if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
                swap(list, i, j);
        } else {
            ListIterator fwd = list.listIterator();
            ListIterator rev = list.listIterator(size);
            for (int i=0, mid=list.size()>>1; i<mid; i++) {
        Object tmp = fwd.next();
                fwd.set(rev.previous());
                rev.set(tmp);
            }
        }
    }
 if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) 是数组实现或集合长度小于16时，第一个和最后一个交换，第二个和倒数第二个交换，以些类推。　
RandomAccess：随机访问接口，数组的实现才支持随机访问。而链表的实现LinkedList是不支持此接口的。
链表的get(i)必须从头指针开始，移动i-1次到指定的位置，当然链表里元素个数较大的时候，不停的移动增加了复杂度。所以采用ListIterator fwd = list.listIterator();
            ListIterator rev = list.listIterator(size);
            for (int i=0, mid=list.size()>>1; i<mid; i++) {
        Object tmp = fwd.next();
                fwd.set(rev.previous());
                rev.set(tmp);
前移后移来实现，是为了降低移动指针的复杂度。swap(list, i, j);是交换两个元素的引用
fwd.set(rev.previous()); rev.set(tmp);也是交换的元素的引用。所以前面很多说数组交换的是值，链表交换的是引用的说法是不正确的。
综合起来看数组reverse稍快些，但差别不太大，因为是同一个复杂度等级。

Answer 20

ArrayList  用数组实现；查找快，插入或删除慢；
LinkedList 用链表实现；查找慢，插入或删除快；就这个问题，理论上应该是LinkedList快些；

Answer 21

逆序涉及所有元素的遍历，在遍历元素上数组操作比链表的迭代操作快。就算是数组需要进行元素交换，但是链表也需要进行链路的交换，这种交换在性能上基本上是一样的。看到楼上有很多称“学过数据结构的都知道 LinkedList 快”，从这一点上看中国学生读书就是一种死读书，书上说什么就是什么了。

Answer 22

你的理论有点错误，数组是采用内存首地址与索引偏移量决定的，这样的定位操作是非常快的。如果需要遍历整个 List，那使用下标迭代 ArrayList 的性能要超过迭代器迭代 LinkedList 的性能。逆转 List 这两种 List 的性能差别主要就体现在遍历的速度上。

Answer 23

应该是LinkedList吧 双向链表存储的

Answer 24

试了一下
果然ArrayList耗费时间要少一点

Answer 25

sorry，最可恶的是发帖不结贴的

Answer 26

看java中自己的实现吧？如果是双向连表直接把头指针直到尾部就行了。相当快吧

Answer 27

数组是采用内存首地址与索引偏移量决定的，这样的定位操作是非常快的。如果需要遍历整个 List，那使用下标迭代 ArrayList 的性能要超过迭代器迭代 LinkedList 的性能。逆转 List 这两种 List 的性能差别主要就体现在遍历的速度上。

Answer 28

从理论上讲应该差不多，ArrayList swap的只不过是对象地址而已，和LinkedList修改指针的效率差不多
但是ArrayList只需要swap length/2次，而LinkedList则需要修改2*length个指针（LinkedList是双向链表）

Answer 29

当然是Linklist效率更高喽，只要掉转一下指针就可以了

Answer 30

关于这2个比较，今天有看到1.6的API上有说明，arraylist会比linkedlist快。具体原因你到那里找下，官方有说明。

Answer 31

说实在的 我感觉两个差不了太多
后来才看你们的回复 结果就是差不多
那些移动数组的童鞋不知道写过算法没
可能还慢慢移动么 直接弄一个占空间（或可变空间） 然后每个轮着复制过去
速度很快
当然基于指针就是地址的值得 也不会很慢
两者都是一次赋值：一个是赋值去新地方 一个是赋新地址去LIST 速度能差很远
那个外国的不知道搞什么的 我就不去看了 不可能差150倍吧 除非底层对ARRAYLIST很给力

Answer 32

从源码上看应该是ArrayListListIterator fwd = list.listIterator();
            ListIterator rev = list.listIterator(size);
            for (int i=0, mid=list.size()>>1; i<mid; i++) {
Object tmp = fwd.next();
                fwd.set(rev.previous());
                rev.set(tmp);
            }linkedList这个移动N次ArrayListl.set(i, l.set(j, l.get(i)));也是n次但是ArrayList的实现代码行少些，代码的多少也是决定速度的；