上篇實(shí)現(xiàn)LinkedList的reverse完全依賴的是源碼的API,但是這種實(shí)現(xiàn)的問(wèn)題在于每次訪問(wèn)原list的元素后都new了一個(gè)node對(duì)象崇堰，這會(huì)導(dǎo)致更多的內(nèi)存被占用升熊。下面考慮復(fù)用原始list的node來(lái)實(shí)現(xiàn)reverse俄烁。

要復(fù)用node節(jié)點(diǎn)對(duì)象需要重新實(shí)現(xiàn)一個(gè)LinkedList,因?yàn)樵创a中的LinkedList沒(méi)有暴露操縱node成員變量的方法。下面是一個(gè)實(shí)現(xiàn)的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對(duì)象外操作node節(jié)點(diǎn)對(duì)象级野，故：(1)需要提供node成員變量的get,set方法页屠，(2)Node<E>不能嵌套定義在MyLinedList內(nèi)部，下面是我定義的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方法

用例測(cè)試代碼如下

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("開(kāi)始時(shí)間="+startTime.longValue());
        MyLinkedList<Integer> rList=new MyLinkedListReverse<Integer>().reverse(list);
        Long endTime=System.currentTimeMillis();
        System.out.println("結(jié)束時(shí)間="+endTime);
        System.out.println("復(fù)用node 4萬(wàn)耗時(shí)="+(endTime-startTime));
        int size=rList.size();
        for(int i=0;i<size;i++){
            System.out.println(rList.removeFirst().intValue());
        }
    }
}

運(yùn)行結(jié)果如下：

圖片.png

之前用new node的用例測(cè)試代碼和實(shí)驗(yàn)結(jié)果如下

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("開(kāi)始時(shí)間="+startTime.longValue());
        List<Integer> reversedList= new LinkedListReverse<Integer>().reverse(list);
        Long endTime=System.currentTimeMillis();
        System.out.println("結(jié)束時(shí)間="+endTime.longValue());
        System.out.println("通過(guò)new node實(shí)現(xiàn)4萬(wàn)條反轉(zhuǎn)時(shí)間="+(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

從運(yùn)行結(jié)果上看蓖柔，復(fù)用node的實(shí)現(xiàn)效率更高辰企，這應(yīng)該是節(jié)省了new對(duì)象的開(kāi)銷(xiāo)得到的好處。