双方向線形リストの実装と反転時間の比較【Java】

以下の記事で、ノードを逐一繋ぎ変えて線形リストをリバースするアルゴリズムについて考えましたが、追加する時点でheadとtailを決めてしまって、さらに逆方向にもノードを辿れるようにすればリバースが一瞬で済むのではないかと考えました。

線形リストのin placeリバース【Java】

Node<T>

前のノードの情報も追加するため、各ノードが保持する情報が二倍になります。

public class Node<T extends Comparable<T>> {

    private T data;
    private Node<T> next;
    private Node<T> prev;
  
    public Node(T data) {
      this.data = data;
      this.next = null;
    }
  
    public T getData() {
      return data;
    }
  
    public void setData(T data) {
      this.data = data;
    }
  
    public Node<T> getNext() {
      return next;
    }
  
    public void setNext(Node<T> next) {
      this.next = next;
    }

    public void setPrev(Node<T> prev){
        this.prev = prev;
    }

    public Node<T> getPrev(){
      return this.prev;
    }
    
  }

LinkedList<T>

先頭と最後尾のノードの情報を保持したクラスを作ります。

public class LinkedList<T extends Comparable<T>>{

    private Node<T> head;
    private Node<T> tail;
    boolean isReversed = false;

    public LinkedList(Node<T> head){

        this.head = head;
        this.tail = null;

    }

    public void add(T data){

        Node<T> curNode = head;
        Node<T> newNode =  new Node<T>(data);
        while(curNode.getNext() != null){
            curNode = curNode.getNext();
        }curNode.setNext(newNode);
        newNode.setPrev(curNode);
        tail = newNode;
    }

    public String toString(){
        String result = "";
        if (!isReversed){
            Node<T> currNode = head;
            while (currNode.getNext() != null){
                result += currNode.getData()+"->";
                currNode = currNode.getNext();
            }
            result += currNode.getData();
        }else{
            Node<T> currNode = tail;
            while(currNode.getPrev() != null){
                result += currNode.getData()+"->";
                currNode = currNode.getPrev();
            }
            result += currNode.getData();
        }
        return result;
    }
}

リバースメソッド

LinkedList内にある、リバースされたかどうかの情報だけを書き換えます。

  public void reverse(){
        if (isReversed){
            this.isReversed = false;
        }else{
            this.isReversed = true;
        }
    }

実行時間の比較

ノードの再接続によるリバースの場合

前回行ったノードの再接続によるリバースメソッドを使用して、1から10000までの数が格納された線形リストをリバースする時間をナノ秒で計測します。

 public static void main(String[] args) {
        LinkedList l = new LinkedList(new Node(0));
        for (int i = 1;i<10000;i++){
            l.add(i);
        }
        
        double t0 = System.nanoTime();
        l.reverse();
        double t1 = System.nanoTime();
        System.out.println(l);
        System.out.println(t1-t0);
    }
>>>
326209.0

双方向線形リストによるリバースの場合

上記で作成した線形リストを使用して、同じく1から10000までの数を保持した線形リストをリバースして、その時間をナノ秒で計測します。

  public static void main(String[] args) {
        Node head = new Node(0);
        LinkedList l = new LinkedList<>(head);
        for (int i = 1;i<1000;i++){
            l.add(i);
        }
        System.out.println(l);
        double t0 = System.nanoTime();
        l.reverse();
        double t1 = System.nanoTime();
        System.out.println(l);
        System.out.println(t1-t0);
    }

>>>
2833.0