24633


Aizu
Onlineジャッジの双方向リストに関するこの問題([http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp))を解いているのですが、最後のテストケースでどうしてもランタイムエラーになってしまいます。

どこか間違っている、もしくは速度を改善できる方法がありましたら教えてください。

[code]

    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.io.IOException;
    
    class DoublyLinkedList {
      public static void main(String args[]){
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        String str;
        String[] array=new String[2];
        int num;
    
        LinkedList list=new LinkedList();
        try{
          int n=Integer.parseInt(reader.readLine());
          num=-1;
    
          for(int i=0;i<n;i++){
            str=reader.readLine();
            if(str.charAt(0)=='i'){
              array=str.split(" ");
              num=Integer.parseInt(array[1]);
              list.insert(num);
            }else if(str.charAt(6)=='F'){
              list.deleteFirst();
            }else if(str.charAt(6)=='L'){
              list.deleteLast();
            }else{
              array=str.split(" ");
              num=Integer.parseInt(array[1]);
              list.delete(num);
            }
          }
          list.outputAll();
        }catch(IOException e){
          ;
        }
      }//main
    }
    
    class LinkedList{
      static class Node{
        int data;
        Node prev;
        Node next;
    
        Node(int data, Node prev, Node next){
          this.data=data;
          this.prev=prev;
          this.next=next;
        }
      }
    
      Node ptr, head;
    
      LinkedList(){
        ptr=head=null;
      }
    
      void insert(int num){
        ptr=head;
        head=new Node(num, null, ptr);
        if(ptr!=null){
          ptr.prev=head;
        }
      }
    
      void delete(int num){
        int cnt=0;
        ptr=head;
        while(ptr!=null){
          if(ptr.data==num){
            //削除
            cnt++;
            if(ptr.next==null&&ptr.prev==null){
              head=null;
            }else if(ptr.prev==null){
              deleteFirst();
            }else if(ptr.next==null){
              deleteLast();
            }else{
              Node Prev=ptr.prev;
              Node Next=ptr.next;
              Prev.next=ptr.next;
              Next.prev=ptr.prev;
            }
            break;
          }
          if(cnt==1){
            break;
          }
          ptr=ptr.next;
        }
      }
    
      void deleteFirst(){
        if(head.next==null){
          head=null; //ノードが一つのときは別処理
        }else{
          head=head.next;
          head.prev=null;
        }
      }
    
      void deleteLast(){
        ptr=head;
        if(head.next==null){
          head=null; //ノードが一つの時は別処理
        }else{
          while(ptr.next!=null){
            ptr=ptr.next;
          }
          ptr=ptr.prev;
          ptr.next=null;
        }
      }
    
      void outputAll(){
        ptr=head;
        while(ptr.next!=null){
          System.out.print(ptr.data+" ");
          ptr=ptr.next;
        }
        System.out.println(ptr.data);
      }
    }
    
[/code]


CC BY-SA 3.0
2016-05-06T15:49:24.083
24611
2016-05-07T12:53:56.903
2016-05-06T16:35:56.933
15279
question
java
Aizu Onlineジャッジ,双方向連結リストの問題(Java)


まず、`deleteLast`を改善する事をお勧めします。

今は双方向リストの最後の要素を得るのに、先頭から辿っていっています。  
双方向リストのインスタンスが先頭の要素しか持っていないからです。  
これを、最後尾の要素への参照も持たせるようにします。

この参照は、`insert`、`deleteFirst`,
`deleteLast`を行なう度に必要ならば更新する事になりますが、大したコストでは無いでしょう。  
`deleteLast`の際に一発で参照出来るメリットを考えれば、追加する価値があります。


CC BY-SA 3.0
2016-05-07T12:53:56.903
24633
2016-05-07T12:53:56.903
3054
24611
answer