Java鏈接列表瞭解方法

Question

我想了解Java中的鏈接列表中的方法，但我仍然有一些問題。

於是我開始用類元素：

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

然後我有類List：

public class List { 

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

我們的方法：看評論請。首先，我從一個方法開始，它將一個元素插入到列表的開頭。

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 
    } 
}