代碼審查鏈接列表中添加（I，X）方法

我目前正在努力刷上ADT實現，專門爲鏈表（我使用Java 5的做到這一點）的實現。代碼審查鏈接列表中添加（I，X）方法

我有兩個問題：

（1）這是實現我爲加法書面（I，X）正確和有效的？

public void add(int i, Object x) { 

    // Possible Cases: 
    // 
    //  1. The list is non-empty, but the requested index is out of 
    //  range (it must be from 0 to size(), inclusive) 
    // 
    //  2. The list itself is empty, which will only work if i = 0 
    // 
    // This implementation of add(i, x) relies on finding the node just before 
    // the requested index i. 

    // These will be used to traverse the list 
    Node currentNode = head; 
    int indexCounter = 0; 

    // This will be used to mark the node before the requested index node 
    int targetIndex = i - 1; 

    // This is the new node to be inserted in the list 
    Node newNode = new Node(x); 

    if (currentNode != null) { 

     while (indexCounter < targetIndex && currentNode.getNext() != null) { 

      indexCounter++; 
      currentNode = currentNode.getNext(); 
     } 

     if (indexCounter == targetIndex) { 

      newNode.setNext(currentNode.getNext()); 
      currentNode.setNext(newNode); 

     } else if (i == 0) { 

      newNode.setNext(head); 
      head = newNode; 
     } 

    } else if (i == 0) { 

     head = newNode; 
    }  
}

（2）我發現這個方法非常具有挑戰性的實現。說實話，這花了我好幾天的時間。這很難承認，因爲我喜歡編程，並且認爲自己處於幾種語言和平臺的中級水平。我從13歲起就開始編程（Applesoft BASIC在Apple IIc上！）並擁有CS學位。我目前是一名軟件測試員，並計劃在某個時候成爲開發人員。所以我的問題的第二部分是：我是否在愚弄自己，這是我擅長的工作類型，還是幾乎每個人都覺得這種問題具有挑戰性？有些事情告訴我，即使經驗豐富的開發人員，面對實施這種方法，會發現它具有挑戰性。

感謝您對第二部分的反饋和建議。

來源

2011-07-08 dvanaria

@dvanaria：我認爲這個問題更適合http://codereview.stackexchange.com。 –

屬於http://codereview.stackexchange.com/ –

好的謝謝，我從來沒有聽說過codereview.stackexchange，它聽起來像一個更好的地方。我會考慮現在移動它。 – dvanaria

我認爲這是一個良好的開端...幾點建議：

我覺得你currentNode == NULL的情況下，應採取照顧起步，然後返回。我不喜歡裏面的所有內容「if（currentNode！= null）」
您應該跟蹤鏈接列表的大小，以便您可以輕鬆地檢查是否我> list_size
我wouldn 't打擾重命名「i-1」到targetIndex
不要創建newNode，直到你需要
編寫單元測試，然後你可以很容易地改變事物並知道你的實現仍然有效。
不要簡單地忽略非法參數。如果索引i < 0或>大小，拋出IllegalArgumentException或IndexOutOfBoundsException異常（感謝@JB Nizet）

來源

2011-07-08 20:00:58 dgrant

好的，謝謝，我確實寫了一個單元測試，試圖打所有的邊界情況。我嘗試在允許的範圍外添加元素，將元素添加到空列表中，在非空列表範圍內添加元素，在位置0添加元素以及添加元素i = size（）（即，在當前列表）。 – dvanaria

另外，不要簡單地忽略非法參數。如果索引i < 0 or >大小，請拋出IllegalArgumentException。否則，調用者不知道沒有任何東西被添加到列表中。 –

我大多數人都同意，但我不同意不將i-1重命名爲targetIndex。我會說改變targetIndex priorindex或priorToInsertionIndex，因爲它使你的意圖更清晰。 targetIndex具有誤導性，i-1根本不清楚。 – Cervo

我建議你先寫一些單元測試。特別是，嘗試在列表末尾添加一個節點，看看會發生什麼。 ;）

我想大多數開發商會發現寫一個LinkedList困難的，因爲一）有實現它很多方面和b）它不是你通常會自己寫。您通常會使用其中一個現有的實現。 ;）

作爲練習這是一個好主意，都是一樣的。我建議你閱讀內置LinkedList的代碼，並考慮如何以不同的方式做事。例如你如何簡化它可能是一個開始。

來源

2011-07-08 20:00:06

此實現的效率不高，但是這是部分因爲操作加（I，x）是不高效的一個正常的鏈表。鏈接列表不適用於隨機訪問。我想如果你創建了一個哈希表或者你可能創建一個更有效的索引到列表中。例如考慮地圖。然後你的插入例程（顯然是i = 0的特殊情況）map.ContainsKey（i-1）map.get（i-1），你立即擁有了先前的索引。如果我！= 0，並且你沒有那個索引的鍵，那麼你馬上就知道一個錯誤。如果沒有太多碰撞，Map理論上是O（1），所以這比每次遍歷列表更有效率（但是以一些磁盤空間爲代價）。再次，它真的取決於，因爲純鏈接列表不是非常有效的添加（i，x）。

我並不特別喜歡這種方法，因爲如果你說add（32，x）並且列表中只有15個項目，它會默默地失敗。它至少應該拋出一個異常，返回false或其他內容，以表明插入失敗。

你也可以合併這兩種特殊情況。假設newNode.setNext（NULL）有效，你只需要一次檢查i == 0，然後你可以執行newNode.setNext（head），head = newNode，因爲這個列表是否爲空或者是否爲空。如果列表爲空，則將下一個指針設置爲NULL。這至少消除了重複的代碼。

花了一個星期看起來似乎有點多，但有些人首先圍繞着指針（在javaspeak中的良好的類引用....），有很多麻煩。事實上，你最終得到的東西是正確的方向邁出的一大步。

來源

2011-07-08 20:04:44 Cervo

代碼審查鏈接列表中添加（I，X）方法

回答

相關問題