LinkedList的reverse实现（二）

上篇实现LinkedList的reverse完全依赖的是源码的API,但是这种实现的问题在于每次访问原list的元素后都new了一个node对象，这会导致更多的内存被占用。下面考虑复用原始list的node来实现reverse。

要复用node节点对象需要重新实现一个LinkedList,因为源码中的LinkedList没有暴露操纵node成员变量的方法。下面是一个实现的List接口的MyLinkedList

public  class MyLinkedList<E> implements List<E> {
    private int size;
    private Node<E> first;
    private Node<E> last;
    public int getSize() {
        return size;
    }
    public void setSize(int size) {
        this.size = size;
    }
    public Node<E> getFirst() {
        return first;
    }
    public void setFirst(Node<E> first) {
        this.first = first;
    }
    public Node<E> getLast() {
        return last;
    }
    public void setLast(Node<E> last) {
        this.last = last;
    }
 @Override
    public boolean add(E e) {
        if(size!=0){
            Node<E> node=new Node<E>(e,last,null);
            last.setNext(node);
            last=node;
            size++;
            return true;
        }else{
            Node<E> node=new Node<E>(e,null,null);
            last=node;
            first=node;
            size++;
            return true;
        }
    }
public E removeFirst(){
        if(size==0){
            return null;
        }
        E item=first.getItem();
        size--;
        first=first.getNext();
        if(first==null){
            last=null;
        }
        return item;
    }
.........

由于要在MyLinkedList对象外操作node节点对象，故：(1)需要提供node成员变量的get,set方法，(2)Node<E>不能嵌套定义在MyLinedList内部，下面是我定义的Node<E>类

public class Node<E> {
    private E item;
    private Node<E> next;
    private Node<E> pre;
    public Node(E item,Node<E> pre,Node<E> next){
        this.item=item;
        this.pre=pre;
        this.next=next;
    }
    public Node<E> exchangeDirection(Node<E>  node){
        Node<E> temp=node.getNext();
        node.setNext(node.getPre());
        node.setPre(temp);
        return node;
    }
    //省略get,set方法

用例测试代码如下

public class MyLinkedListTest {
    public static void main(String[] args) {
        MyLinkedList<Integer> list=new MyLinkedList<Integer>();
        for(int i=0;i<40000;i++){
            list.add(i);
        }
        Long startTime=System.currentTimeMillis();
        System.out.println("开始时间="+startTime.longValue());
        MyLinkedList<Integer> rList=new MyLinkedListReverse<Integer>().reverse(list);
        Long endTime=System.currentTimeMillis();
        System.out.println("结束时间="+endTime);
        System.out.println("复用node 4万耗时="+(endTime-startTime));
        int size=rList.size();
        for(int i=0;i<size;i++){
            System.out.println(rList.removeFirst().intValue());
        }
    }
}

运行结果如下：

图片.png

之前用new node的用例测试代码和实验结果如下

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<Integer> list=new LinkedList<Integer>();
        for(int i=0;i<40000;i++){
            list.add(i);
        }
        System.out.println("原始的LinkedList的size="+list.size());
        Long startTime=System.currentTimeMillis();
        System.out.println("开始时间="+startTime.longValue());
        List<Integer> reversedList= new LinkedListReverse<Integer>().reverse(list);
        Long endTime=System.currentTimeMillis();
        System.out.println("结束时间="+endTime.longValue());
        System.out.println("通过new node实现4万条反转时间="+(endTime-startTime));
        for(Integer i: reversedList){
            System.out.println(i.intValue());
        }
    }
}
public class LinkedListReverse <E> {
    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;
    }
}

图片.png

从运行结果上看，复用node的实现效率更高，这应该是节省了new对象的开销得到的好处。