什麼是一個LinkedListNode在Java中

Question

請原諒我的無知，但我開始了我的第一個技術面試準備，碰到這個問題就來了，並在話題LinkedList的回答

問題：實現一個算法，中間刪除一個節點單鏈表的，只給該節點

 
public static boolean deleteNode(LinkedListNode n) { 
if (n == null || n.next == null) { 
    return false; // Failure 
} 
LinkedListNode next = n.next; 
n.data = next.data; 
n.next = next.next; 
return true; 
} 

我要開始使用此代碼打（更改編譯測試），但我不知道如何開始用Java做這個訪問。我無法在Java文檔中找到LinkedListNode類。

這可能是一個非常愚蠢的問題，但如果有人能指出我在正確的方向 - 將不勝感激。

編輯

感謝您的快速和有效的反應。我想我的問題不是很清楚。上面的算法是作爲該問題的解決方案提供的。我想知道如何在Java中實現這個功能，這樣我就可以使用代碼了。

感謝

Answer 1

如果列表中有尾部節點，代碼才能正常工作。

該算法有以下邏輯

When referring to the node to be deleted, call it "curr" 
When referring to the node before "curr", call it "prev" 
When referring to the node after "curr", call it "next" 

To effectively delete our node, "prev".next should point to "next" 
It currently points to "curr" 

Our problem is that we have no reference to "prev" 

We know "prev".next points to "curr" 

Since we cannot change the fact that "prev".next points to "curr", 
we must have "curr" gobble up "next" 

We make "curr"s data be "next"s data 
We make "curr"s next be "next"s next 

The reason this only works if there's a tail guard 
is so we can make "next" be the "tail" node of the 
list. (Its data is null and it's next is null.) Otherwise, 
"prev".next would still be pointing to something. 

這是一個使用一個LinkedListNode類。我應該注意到，如果你正在申請一個程序員的職位，你應該能夠基本上從內存中做到這一點。 :-)

class LinkedList<E> { 

    static class LinkedListNode<E> { 
     E data; 
     LinkedListNode<E> next; 
    } 

    /** 
    * Not exactly the best object orientation, but we'll manage 
    */ 
    static <E> E deleteNode(LinkedListNode<E> node) { 
     if(node == null || node.next == null) return null; 

     E retval = node.data; 
     LinkedListNode<E> next = node.next; 
     node.data = next.data; 
     node.next = next.next; 
     return retval; 
    } 

    private LinkedListNode<E> head; 
    private LinkedListNode<E> tail; 

    public LinkedList() { 
     this.head = new LinkedListNode<E>(); 
     this.tail = new LinkedListNode<E>(); 
     head.next = tail; 
    } 

    public void addLast(E e) { 
     LinkedListNode<E> node = new LinkedListNode<E>(); // e and next are null 
     tail.data = e; 
     tail.next = node; 
     tail = node; 
    } 

    public void addFirst(E e) { 
     LinkedListNode<E> node = new LinkedListNode<E>(); // e and next are null; 
     node.next = head.next; 
     node.data = e; 
     head.next = node; 
    } 

    public E deleteFirst() { 
     LinkedListNode<E> first = head.next; 
     head.next = first.next; 
     return first.data; 
    } 

    public E deleteLast() { 
     // cannot do without iteration of the list! :-(
     throw new UnsupportedOperationException(); 
    } 

    public LinkedListNode<E> findFirst(E e) { 
     LinkedListNode<E> curr = head.next; 
     while(curr != null) { 
      if(curr.data != null && curr.data.equals(e)) return curr; 
      curr = curr.next; 
     } 
     return null; 
    } 

    public void print() { 
     LinkedListNode<E> curr = head.next; 
     while(curr.next != null) { 
      System.out.println(curr.data); 
      curr = curr.next; 
     } 
    } 


    public static void main(String[] args) { 
     LinkedList<String> list = new LinkedList<String>(); 
     list.addLast("Apple"); 
     list.addLast("Bear"); 
     list.addLast("Chair"); 
     list.addLast("Dirt"); 

     //list.print(); 

     LinkedListNode<String> bear = list.findFirst("Bear"); 
     deleteNode(bear); 

     list.print(); 
    } 

} 

Answer 2

這個類是最有可能用於這一Linked List例如問題進行的假想類。

Answer 3

你的問題有點混亂。無論你想要一個邏輯刪除單鏈表中的節點，還是想學習和使用java LinkedListNode。

，如果你在第二下面的鏈接將幫助您

LinkedListNodee

，或者如果你想要的邏輯

let P the pointer to the current node 
P->data = P->next->data 
Q=P->next 
P->next=Q->next 
delete(Q) 

Answer 4

在這個問題的重要細節涉及數據結構，是java只是在這種情況下用來實現的語言。
您應該閱讀關於linked lists的維基百科文章，對於此問題，請注意您的解決方案不會產生任何懸掛引用或孤兒節點。
用粗體對兩個術語進行一些搜索，並確保您瞭解它們

Answer 5

LinkedListNode是一個您將要定義的用於存放數據的類。爲了讓你的上面的例子工作 - 我已經很快寫了這段代碼（只是爲了讓你理解這個簡單的概念），其中我創建了3個節點（它們相互鏈接），然後刪除中間的一個，調用deleteNode您在問題中指定的方法。

該代碼非常自我解釋。讓我知道這是否有幫助。 好運

class LinkedListNode 
{ 
    public Object data; 
    public LinkedListNode next; 

    public LinkedListNode(Object data) { 
    this.data = data; 
    } 
} 

class DeleteNodeLinkedList 
{ 
    public static void main(String[] args) 
    { 
     LinkedListNode node_1 = new LinkedListNode("first");   
     LinkedListNode node_2 = new LinkedListNode("second"); 
     node_1.next = node_2; 
     LinkedListNode node_3 = new LinkedListNode("third"); 
     node_2.next = node_3; 

     System.out.println("*** Print contents of linked list"); 
     LinkedListNode current = node_1; 
     while (current != null) { 
      System.out.println(current.data); 
      current = current.next; 
     } 

     System.out.println("*** Now delete second node"); 
     deleteNode(node_2); 

     System.out.println("*** Print after deleting second node"); 
     current = node_1; 
     while (current != null) { 
      System.out.println(current.data); 
      current = current.next; 
     } 
    } 

    public static boolean deleteNode(LinkedListNode n) 
    { 
     if (n == null || n.next == null) { 
      return false; // Failure 
     } 
     LinkedListNode next = n.next; 
     n.data = next.data; 
     n.next = next.next; 
     return true; 
    } 
}