Javaのリンクリストのメソッドを理解する

Question

Javaのリンクリストのメソッドを理解しようとしていますが、まだいくつか問題があります。

だから私は、クラスの要素で開始：

class Element { 
int val; // can be anything like String etc. 
Element next; // Pointer to the next Element 

その後、私はクラスのリストを持っている：

方法に今

public class List { 

Element head = null; // Beginning of the list (head) 

：コメントにしてくださいをご覧ください。最初に、リストの先頭にElementを挿入するメソッドから始めます。

public void insertAtEnd(int x){ 
    Element n = new Element(); 
    n.val = x; 

    if (head == null){ // If the list is empty 
     head = n; // we insert the Element n as the first element 
    } 
    else{ 
     Element h = head; // I think this helps as a reference right? 
     while (h.next != null){ // While the pointer of the head isn't empty 
      h = h.next; // our Element h becomes the next Element added to the list 
     } 
     h.next = n; // If none of the cases above apply, the Element h ist just added at the end of the list right? 
    } 
} 

方法は、私が今、特定の番号の後に要素を挿入したい場合はどのように見えるか：

public void insertAtBegin (int x){ 
    Element n = new Element(); // We create a new Object Element called n 
    n.val = x; // We pass the value of x to the object n with the attribute int val (Is that right?) 
    n.next = head; // What happens here? 
    head = n; // The new Element n becomes the head 
} 

第二の方法は、リストの末尾に要素を挿入しますか？始まりでも終わりでもない。理論的には、まず頭が空であるかどうかを調べます。次に、私の特定の要素のポインタを置く。 4を私が挿入したいと思っている新しい要素に置き換えます。そして、新しく挿入された要素のポインタを次の要素に渡します。しかし、これをコードに入れる方法がわかりません。

リストの最後の要素を削除し、最初に挿入するメソッドもあります。誰かがこれも同様にどのようにコメントしていただけますか？

public void lastToBegin(){ 
    if (head != null && head.next != null){ 
     Element e = head; 
     while(e.next.next != null){ 
      e = e.next; 
     } 
     Element h = e.next; 
     e.next = null; 
     h.next = head; 
     head = h; 
    } 
} 

私にはもっと多くの方法がありますが、まず基本を理解したいと思います。 ありがとうございました。

Answer 1

リスト内の特定のインデックスに要素を挿入する場合は、最後に挿入する必要があるメソッドと非常によく似ていますが、最後ではなく正しいインデックスで停止する必要があります。挿入している要素にリストの「末尾」を追加する必要があります。

は、だからあなたのコードは次のようになります：

public void insertAtIndex(int x, int index){ 
    Element n = new Element(); 
    n.val = x; 

    if (head == null){ // If the list is empty 
     head = n; // we insert the Element n as the first element 
    } 
    else{ 
     Element h = head; // our current element we are looking at 
     int currentIndex = 0; 
     while (h.next!=null && currentIndex < index) { // increment until we reach the correct index 
      h = h.next; // our Element h becomes the next Element added to the list   
      currentIndex++; 
     } 
     Element tail = h.next; // store the rest of the list in a temp variable, tail 
     h.next = n; // we've reached the right index and/or the end, so add the element n here 
     n.next = tail // reattach the tail 
    } 
}