LinkedList最後に挿入

Question

リンクリストの末尾に要素を挿入しようとしていますinsertAtEnd()。コードをデバッグすると、挿入の最初にnode(0,null)がデフォルトとして挿入されています。私はこれがリストを反復しながら問題を引き起こしていると思います。どのようにこれを修正するための任意の提案？

package com.ds.azim; 

public class Node { 
    //Node has 1. Data Element 2. Next pointer 
    public int data; 
    public Node next; 
    //empty constructor 
    public Node(){ 
     // 
    } 
    public Node(int data){ 
     this.data= data; 
     this.next = null; 
    } 
    public Node(int data, Node next){ 
     this.data = data; 
     this.next = next; 
    } 
} 

//*************************************//  

package com.ds.azim; 

    public class SingleLinkedList { 
     //Single Linked list has a head tail and has a length 
     public Node head; 
     public Node tail; 
     public int length; 
     //constructor 
     public SingleLinkedList(){ 
      head = new Node(); 
      length = 0; 
     } 
     public void insertAtFirst(int data){ 
      head = new Node(data,head); 
     } 
     public void insertAtEnd(int data){ 
      Node curr = head; 
      if(curr==null){ 
       insertAtFirst(data); 
      }else{ 
       while(curr.next!=null){ 
        curr = curr.next; 
       } 
       curr.next = new Node(data,null); 
      } 
     } 
     public void show(){ 
      Node curr = head; 
      while(curr.next!=null){ 
       //do something 
       System.out.print(curr.data+","); 
       curr = curr.next; 
      } 
     } 
     public static void main(String[] args){ 
      SingleLinkedList sll = new SingleLinkedList(); 
      sll.insertAtFirst(12); 
      sll.insertAtFirst(123); 
      sll.insertAtFirst(890); 
      sll.insertAtEnd(234); 
      sll.show(); 


     } 
    } 

Answer 1

あなたのコードは、それを指して(0, null)とheadを含むNodeでリストを初期化します。これを修正するには、それをしないでください。そのコードでも

public SingleLinkedList() { 
    head = new Node(); 
    length = 0; 
} 

あなたはlength = 0;を設定し、実際の長さは1です。両方の割り当てをコンストラクタから削除します。次にメンバーがゼロの構造を持ち、長さは正しいでしょう。

Answer 2

リストの最後のノードを指す変数tailがあります。あなたは今までにそれを維持する必要があります。

class SingleLinkedList { 
    private Node head = null; 
    private Node tail = null; 

    public void addAtHead(int data) { 
     if (head == null) { 
      addFirst(data); 
     } else { 
      head.next = new Node(data, head.next); 
      if (tail == head) 
       tail = head.next; 
     } 
    } 

    public void addAtTail(int data) { 
     if (head == null) { 
      addFirst(data); 
     } else { 
      assert tail != null; 
      assert tail.next == null; 
      tail.next = new Node(data); 
      tail = tail.next; 
     } 
    } 

    private void addFirst(int data) { 
     assert head == null; 
     assert tail == null; 
     head = new Node(data); 
     tail = head; 
    } 
} 

あなたは、tail変数を削除する場合：

class SingleLinkedList { 
    private Node head = null; 

    public void addAtHead(int data) { 
     if (head == null) { 
      head = new Node(data); 
     } else { 
      head.next = new Node(data, head.next); 
     } 
    } 

    public void addAtTail(int data) { 
     if (head == null) { 
      head = new Node(data); 
     } else { 
      Node curr = head; 
      while (curr.next != null) 
       curr = curr.next; 
      curr.next = new Node(data); 
     } 
    } 
} 

Answer 3

コード

public SingleLinkedList() { 
    head = new Node(); 
    length = 0; 
} 

この変化の一部を除去するとともに最後の要素は印刷されないので、あなたのshow関数も同様です。

while(curr.next!=null){ 
       //do something 
       System.out.print(curr.data+","); 
       curr = curr.next; 
      } 

この後、最後の要素を印刷するprintステートメントを1つ追加します。

System.out.print(curr.data); 

これでエラーを修正します。