ArrayList和LinkedList的reverse实现

java集合类中的ArrayList和LinkedList都实现了List接口，都实现了get,add,set,size,remove等列表操作。但是ArrayList的底层实现是数组，LinkedList的底层实现是双向链表。这意味着ArrayList的get(int index),set(int index,E element)操作的时间复杂度为O(1),与索引的大小无关，而LinkedList的get,set需要线性检索链表,时间复杂度和index的大小成正比。基于数组和链表在检索性能上的不同，实现reverse的策略也不相同。
下面是ArrayList的reverse实现

public ArrayList<E> reverse(ArrayList<E> list){
        int size=list.size();
        ArrayList<E> reversedList=new ArrayList<E>(size);
        for(int i=size-1;i>-1;i--){
            reversedList.add(list.get(i));
        }
        return reversedList;
    }

ArrayList源码中的add方法如下，如果不需要给数组扩容，那么add的时间复杂度总是O(1)。所以在reverse的实现中，用原始的list的size初始化一个reversedList，这样每次for循环的执行时间都是常数级的时间成本。最终的时间复杂度是O(size)。

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

LinkedList的reverse实现如下

public LinkedList<E> reverse(LinkedList<E> list){

        if(list.getFirst()==null){
            return null;
        }
        LinkedList<E> reversedList=new LinkedList<E>();
        E item=null;
        int n=list.size();
        for(int i=0;i<n;i++){
            reversedList.add(list.removeLast());
        }
        return reversedList;
    }

LinkedList的add和ArrayList的add都是常数级的时间复杂度，但是LinkedList通过index索引的时间复杂度是index线性函数，所以这里for循环里不能通过索引来得到原始LinkedList的元素引用。考虑到LinkedList的底层实现是双向链表，可以实现类似栈的pop操作，对应的api为removeLast()，源码如下

public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }
    }

从源码中看到，弹出列表末节点只涉及修改倒数第二个节点的链接，这个操作也是常数级的复杂度。