爲什麼我的自定義LinkedList無法正常工作？

Question

我想創建自定義LinkedList來更好地理解數據結構。我無法弄清楚我的LinkedList類的問題。

package numberlist.primitivelist.objectlist; 

public class ObjectLinkedList extends ObjectList implements Copiable { 

Node firstNode; 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: ObjectLinkedList() description:constructor 
* 
* @author Jinyu Wu Date: 2017/2/4 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
*/ 
public ObjectLinkedList() { 
    firstNode = null; 
} 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: add() description: Insert an item into the list 
* 
* @param index position of the list 
* @param obj the element is going to be inserted 
* @author Jinyu Wu Date: 2017/2/4 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
*/ 
@Override 
public void add(int index, Object obj) { 
    Node tempNode = firstNode; 
    Node currentNode = new Node(obj); 
    if (index == 0) { 
     firstNode = currentNode; 
     return; 
    } 
    if (index < 0 || index > size()) { 
     System.out.println("add(ObjectLinkedList) index out of bound exception"); 
    } else { 
     for (int i = 1; i <= index; i++) { 
      tempNode = tempNode.getNext(); 
      if (i == index - 1) { 
       if (index != size() - 1) { 
        currentNode.setNext(tempNode.getNext()); 
       } else { 
        currentNode.setNext(null); 
       } 
       tempNode.setNext(currentNode); 
      } 
     } 
    } 

} 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: removeAt() description: remove an item from a position of the 
* list 
* 
* @param index position in the list 
* @author Jinyu Wu Date: 2017/2/4 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
*/ 
@Override 
public void removeAt(int index) { 
    if (index < 0 || index > size()) { 
     System.out.println("removeAt(ObjectLinkedList) index out of bound exception"); 
    } else { 
     Node tempNode = firstNode; 
     if (index == 0) { 
      firstNode = firstNode.getNext(); 
     } else { 
      for (int i = 1; i <= index; i++) { 
       tempNode = tempNode.getNext(); 
       if (i == index - 1) { 
        if (index != size() - 1) { 
         tempNode.setNext(tempNode.getNext().getNext()); 
        } else { 
         tempNode.setNext(null); 
        } 
       } 
      } 
     } 
    } 

} 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: remove() description: remove a specific item from a position of 
* the list 
* 
* @param obj target object is going to be removed 
* @author Jinyu Wu Date: 2017/2/4 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
*/ 
@Override 
public void remove(Object obj) { 
    if (size() > 0) { 
     Node tempNode = firstNode; 
     for (int i = 0; i <= size(); i++) { 
      if (tempNode.equals(obj)) { 
       tempNode.setNext(tempNode.getNext().getNext()); 
       break; 
      } 
      if (i < size() - 1) { 
       tempNode = tempNode.getNext(); 
      } 
     } 

     System.out.println("target object is not found inside the linkedList(remove)"); 
    } 
} 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: get() description:get an item from the list 
* 
* @param index position in the list 
* @author Jinyu Wu Date: 2017/2/4 
* @return double ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
*/ 
@Override 
public Object get(int index) { 
    if (index < 0 || index > size()) { 
     System.out.println("get(ObjectLinkedList) index out of bound exception"); 
     return null; 
    } else if (index == 0) { 
     return firstNode; 
    } else { 
     Node tempNode = firstNode; 
     for (int i = 0; i <= index; i++) { 
      if (i == index - 1) { 
       tempNode = tempNode.getNext(); 
       return tempNode; 
      } 
     } 
     System.out.println("objectLinkedList get method nothing found"); 
     return null; 
    } 

} 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: toString() description: print out the content of the list 
* 
* @author Jinyu Wu Date: 2017/2/4 
* @return Integer ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
*/ 
@Override 
public String toString() { 
    return "ObjectLinkedList{" + "firstNode=" + firstNode + '}'; 
} 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: find() description:get an item from the list 
* 
* @author Jinyu Wu Date: 2017/2/4 
* @param obj Object is going to be found 
* @return Integer ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
*/ 
@Override 
public int find(Object obj) { 
    Node tempNode = firstNode; 
    Node newNode = new Node(obj); 
    if (newNode.equals(firstNode)) { 
     return 0; 
    } else { 
     for (int i = 1; i < size(); i++) { 
      if (tempNode.equals(newNode)) { 
       return i; 
      } 
      tempNode = tempNode.getNext(); 
     } 
     return -1; 
    } 

} 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: size() description:get the size of the list 
* 
* @author Jinyu Wu Date: 2017/2/4 
* @return Integer ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
*/ 
@Override 
public int size() { 
    int size = 1; 
    if (firstNode == null) { 
     return 0; 
    } 
    try { 
     for (Node n = firstNode; n.getNext() != null; n = n.getNext()) { 
      size++; 
     } 
     return size; 
    } catch (NullPointerException e) { 
     return size; 
    } 
} 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: deepCopy() description: make a deepCoy for this object 
* 
* @author Jinyu Wu Date: 2017/2/4 
* @return String ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
*/ 
@Override 
public ObjectLinkedList deepCopy() { 
    ObjectLinkedList newList = new ObjectLinkedList(); 
    Node currentNode = firstNode; 

    for (int i = 0; i < size(); i++) { 
     Node newNode = new Node(currentNode.getValue()); 
     newList.add(i, newNode); 
     currentNode = currentNode.getNext(); 
    } 

    return newList; 

} 

}

這裏是什麼做的，通過使用JUnit測試

package numberlist.primitivelist.objectlist; 

import org.junit.Before; 
import org.junit.Test; 
import static org.junit.Assert.*; 


public class ObjectLinkedListTest { 

ObjectLinkedList list; 
Money m1, m2; 
Node node1, node2; 

public ObjectLinkedListTest() { 

} 

@Before 
public void setUp() { 
    list = new ObjectLinkedList(); 
    m1 = new Money(5, (byte) 6); 
    node1 = new Node(m1); 
    list.add(0, node1); 

    m2 = new Money(2, (byte) 4); 
    node2 = new Node(m2); 
    list.add(1, node2); 
} 

/** 
* Test of add method, of class ObjectLinkedList. 
*/ 
@Test 
public void testAdd() { 
    assertEquals(list.get(0), node1); 
} 

/** 
* Test of removeAt method, of class ObjectLinkedList. 
*/ 
@Test 
public void testRemoveAt() { 
    list.removeAt(1); 
    assertNull(list.get(1)); 
} 

/** 
* Test of remove method, of class ObjectLinkedList. 
*/ 
@Test 
public void testRemove() { 
    list.remove(m2); 
    assertNull(list.get(1)); 
} 

/** 
* Test of get method, of class ObjectLinkedList. 
*/ 
@Test 
public void testGet() { 
} 

/** 
* Test of toString method, of class ObjectLinkedList. 
*/ 
@Test 
public void testToString() { 
} 

/** 
* Test of find method, of class ObjectLinkedList. 
*/ 
@Test 
public void testFind() { 
    assertEquals(list.find(m1), 0); 
    assertEquals(list.find(m2), 1); 
} 

/** 
* Test of size method, of class ObjectLinkedList. 
*/ 
@Test 
public void testSize() { 
    assertEquals(list.size(), 2); 
} 

/** 
* Test of deepCopy method, of class ObjectLinkedList. 
*/ 
@Test 
public void testDeepCopy() { 

} 

}

這裏測試它是我得到的錯誤：

Error here

我的節點類：

package numberlist.primitivelist.objectlist; 

public class Node { 

private Node nextNode; 
private Object obj; 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: Node() description: constructor 
* 
* @author Jinyu Wu Date: 2017/2/4 
* @param obj set the value 
*/ 
public Node(Object obj) { 
    this.obj = obj; 
    this.nextNode = null; 
} 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: getValue() description: get the value of object 
* 
* @author Jinyu Wu Date: 2017/2/4 
* @return return the object 
*/ 
public Object getValue() { 
    return this.obj; 
} 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: setValue() description: setValue for the Node 
* 
* @author Jinyu Wu Date: 2017/2/4 
* @param obj return the value 
*/ 
public void setValue(Object obj) { 
    this.obj = obj; 
} 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: getValue() description: get the next value of the currentNode 
* 
* @author Jinyu Wu Date: 2017/2/4 
* @return return next node 
*/ 
public Node getNext() { 
    if (nextNode != null) { 
     return this.nextNode; 
    } else { 
     return null; 
    } 
} 

/** 
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* 
* Method: setNext() description: set next value for the Node 
* 
* @author Jinyu Wu Date: 2017/2/4 
* @param node set next node 
*/ 
public void setNext(Node node) { 
    this.nextNode = node; 
} 

} 

Answer 1

我假設這是用於練習或作業，java有一個LinkedList的通用實現已經see the api docs。

您可能會發現在Java中helpul數據結構的很多texts之一，但通常是他們實現使用仿製藥，而不是Object，

---

爲了您的具體問題，你會發現，在testAdd方法調用

assertEquals(list.get(0), m1); 

這是比較一個Node到一個Money對象，它總是會失敗。

你可以 assertEquals(list.get(0).getValue(), m1); 這不會工作，除非你改變get()方法返回一個Node而不是Object，因爲它是目前正在做。

您與其他測試有類似的問題，其中list.get()返回Node，而不是該節點中的數據。

或者編輯get()方法在節點返回數據：

... 
    } else if (index == 0) { 
     return firstNode.getValue(); 
    } else { 
    // etc, you have multiple returns in this method 

編輯

你testRemoveAt()將拋出NullPointerException爲get方法試圖調用tempNode.getNext().getValue()，但你只有測試後，列表中的一個Money對象刪除第二個對象，所以getNext()返回null。

編輯2

這可能是最有用的讓你成爲更熟悉你的調試器。也許試試netbeans的視頻教程。然後你調查你的例外。例如，在運行的第一個測試得出：

java.lang.AssertionError: 
Expected :Node@4f2410ac 
Actual :Money@722c41f4 

這意味着testAdd（）測試失敗它呼籲assertEquals(list.get(0), m1);

的東西，這裏要注意的是，爲assertEquals簽名取其預期值第一，和實際值第二。因此，將該行更改爲assertEquals(m1, list.get(0));並重新運行測試。

現在的輸出爲：

java.lang.AssertionError: 
Expected :Money@722c41f4 
Actual :Node@4f2410ac 

所以測試一個expectod對象Money（那將m1參數），但list.get(0)返回Node對象來代替。

要麼測試期望錯誤的東西或get()方法返回錯誤的東西。我打算假設，當你打電話給list.get(0)時，你實際上想要得到一個Money對象，這意味着測試是正確，我們需要看看list.get()的實現。

您有：

1. public Object get(int index) { 
2.  if (index < 0 || index > size()) { 
3.   System.out.println("get(ObjectLinkedList) index out of bound exception"); 
4.   return null; 
5.  } else if (index == 0) { 
6.   return firstNode; 
7.  } else { 
8.   Node tempNode = firstNode; 
9.   for (int i = 0; i <= index; i++) { 
10.    if (i == index - 1) { 
11.     tempNode = tempNode.getNext(); 
12.     return tempNode; 
13.    } 
14.   } 
15.   System.out.println("objectLinkedList get method nothing found"); 
16.   return null; 
17.  } 
18. } 

和在線6和12，你可以看到問題：函數返回一個Node當我們真正想要Money;或者更具體地說，作爲對象的Node的值。所以下面的更改可那些行

6.  return firstNode.getValue(); 

和

12. return tempNode.getValue(); 

，然後運行testAdd再次應該能順利通過。

這可能是而不是修復代碼中的所有錯誤，但是它讓您瞭解要查找問題的步驟。

你的代碼格式良好，你已經努力把javadoc放在你的函數上，而且你是持久的。好的工作，繼續下去。

Answer 2

的問題是在size()方法，你沒有考慮到雙刃情況：

1. 當列表爲空（你會得到的NPE試圖執行n.getNext()

2. 當有在列表中只有一個節點（它沒有「下一個」，所以它會回到零，而不是1）

您可以輕鬆地通過添加在方法的開頭以下修正：

public int size() { 
     int size = 1; 
     if (firstNode == null) { 
      return 0; 
     } 
     try {... 

有一個在方法add另一個bug。 for循環不必要的複雜，並且不處理一些邊界情況。修改爲：

public void add(int index, Object obj) { 
    Node tempNode = firstNode; 
    Node currentNode = new Node(obj); 
    if (index < 0 || index > size()) { 
     System.out.println("add(ObjectLinkedList) index out of bound exception: " + index + "; size: " + size()); 
    } else if (index == 0) { 
     firstNode = currentNode; 
    } else { 
     for (int i = 0; i < index-1; i++) { 
      tempNode = tempNode.getNext(); 
     } 
     tempNode.setNext(currentNode); 
    } 
} 

而且代碼將工作。

而且，我也「升級」 toString方法是這樣的：

@Override 
public String toString() { 
    Node tmp = firstNode; 
    String res = "" + firstNode; 
    while (tmp.getNext() != null) { 
     tmp = tmp.getNext(); 
     res += "," + tmp; 
    } 
    return "ObjectLinkedList{" + res + "}"; 
} 

這樣，當你打印清單，你就可以看到所有的元素，不僅是第一個。