Sorted Linked Based List Java

Question

我正在爲我的數據結構類進行分配。我們必須使用我們自己的已排序鏈接列表adt創建通訊錄。現在，add方法起作用，但它似乎使所有節點都指向第一個節點。每當我嘗試在for循環中使用getEntry（）輸出列表時，它每次都會給我最後一個添加的條目。我試過使用toArray，但它做同樣的事情。你能看到任何問題嗎？

public class GTSortedLinkedBasedList implements GTListADTInterface { 
private Node firstNode; 
private int numberOfEntries; 

public GTSortedLinkedBasedList(){ 
    //firstNode = new Node(null); 
    numberOfEntries = 0; 
} 

public void setNumberOfEntries(int x){ 
    numberOfEntries = x; 
} 

public void add(ExtPersonType newEntry){ 
    //firstNode = null; 
    Node newNode = new Node(newEntry); 
    Node nodeBefore = getNodeBefore(newEntry); 
    if (isEmpty() || (nodeBefore == null)) 
    { 
     // Add at beginning 
     newNode.setNextNode(firstNode); 
     firstNode = newNode; 
    } 
    else 
    { 
     // Add after nodeBefore 
     Node nodeAfter = nodeBefore.getNextNode(); 
     newNode.setNextNode(nodeAfter); 
     nodeBefore.setNextNode(newNode); 
    } // end if 
    numberOfEntries++; 
} 

private Node getNodeBefore(ExtPersonType anEntry){ 
    Node currentNode = getFirstNode(); 
    Node nodeBefore = null; 
    while ((currentNode != null) && 
    (anEntry.getFirstName().compareTo(currentNode.getData().getFirstName()) > 0)) 
    { 
    nodeBefore = currentNode; 
    currentNode = currentNode.getNextNode(); 
    } // end while 
    return nodeBefore; 
} 

private class Node { 

    private ExtPersonType data; 
    private Node next; 

    public Node(ExtPersonType dataValue) { 
     next = null; 
     data = dataValue; 
    } 

    public Node(ExtPersonType dataValue, Node nextValue) { 
     next = nextValue; 
     data = dataValue; 
    } 

    public ExtPersonType getData(){ 
     return data; 
    } 
    public void setData(ExtPersonType newData){ 
     data = newData; 
    } 
    public Node getNextNode(){ 
     return next; 
    } 
    public void setNextNode(Node newNode){ 
     next = newNode; 
    } 

} 


public ExtPersonType getEntry(int givenPosition) { 
    if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)){ 
     assert !isEmpty(); 
     return getNodeAt(givenPosition).getData(); 
    } 
    else{ 
     throw new IndexOutOfBoundsException("Illegal position given to getEntry operation."); 
    } 
} 

public void loadData(GTSortedLinkedBasedList contacts) throws FileNotFoundException{ 
    //int index = 0; 
    ExtPersonType person = new ExtPersonType(); 
    DateType tempDate = new DateType(); 
    AddressType tempAddress = new AddressType(); 
    Scanner file = new Scanner(new FileInputStream("Programming Assignment 1 Data.txt")); 
    while(file.hasNext()){ 
     person.setFirstName(file.next()); 
     person.setLastName(file.next()); 
     tempDate.setMonth(file.nextInt()); 
     tempDate.setDay(file.nextInt()); 
     tempDate.setYear(file.nextInt()); 
     person.setDOB(tempDate); 
     tempAddress.setStreetAddress(file.nextLine()); 
     if(tempAddress.getStreetAddress().isEmpty()){ 
      tempAddress.setStreetAddress(file.nextLine()); 
     } 
     tempAddress.setCity(file.nextLine()); 
     tempAddress.setState(file.nextLine()); 
     tempAddress.setZipCode(file.nextLine()); 
     person.setAddress(tempAddress); 
     person.setPhoneNumber(file.nextLine()); 
     person.setPersonStatus(file.nextLine()); 
     if(person.getPersonStatus().isEmpty()){ 
      person.setPersonStatus(file.nextLine()); 
     } 
     contacts.add(person); 
     System.out.println(contacts.getEntry(contacts.getLength()).getFirstName()); 
     //index++; 

    } 
} 

public static void main(String[] args) throws FileNotFoundException { 
    AddressBook ab = new AddressBook(); 

    ab.loadData(ab); 
    ExtPersonType people = new ExtPersonType(); 
    //people = ab.toArray(people); 
    System.out.println(ab.getLength()); 
    for(int cnt = 1; cnt <= ab.getLength(); cnt++){ 
     people = ab.getEntry(cnt); 
     System.out.println(people.getFirstName()); 
    } 

} 

編輯：添加方法是用新添加的每個以前的對象覆蓋。這似乎也不重要，如果我做一個排序列表或只是一個基本列表。

Answer 1

我不會在這裏說謊，我不完全確定我理解你的代碼，但我想我明白了什麼是錯的。在getNodeBefore（）方法的代碼中，您將currentNode（）始終設置爲firstNode（）。我相信這是造成這個問題的原因。我發現你試圖通過遞歸遍歷列表來找到合適的節點，但我認爲每次遞歸調用都不會導致整個列表的移動。我建議你向代表向前和向後節點的對象添加屬性。

事情是這樣的......

private T data; 
private Node nodeBefore; 
private Node nodeAfter; 

當你創建對象時，前，後分配屬性，然後所有你需要的信息都包含在對象本身。

要在列表中遞歸移動，您只需添加一條語句，如currentNode = currentNode.nodeAfter。

您的getNodeBefore（）方法將簡單地返回currentNode.nodeBefore，getNodeAfter（）將返回currentNode.nodeAfter。

Answer 2

您沒有處理所添加的節點將成爲列表中的第一個節點但列表也不爲空的情況的代碼。在這種情況下，getNodeBefore返回null，並且您的代碼將覆蓋根節點。

嘗試

if (isEmpty() && (nodeBefore == null)) 
    { 
    // Add at beginning 
    newNode.setNextNode(firstNode); 
    firstNode = newNode; 
    } 
    else if(nodeBefore == null) 
    { 
    Node temp = new Node(); 
    temp.setNextNode(first.next); 
    temp.setData(first.data); 
    newNode.setNextNode(temp); 
    firstNode = newNode; 
    }