如何使用Java按字母順序排序鏈接列表？

我正在做圖書館庫存系統，所以我應該按照字母順序排列節點內的名字。我有書名，作者，isbn號碼，副本數量和類型，所有這些信息都存儲在一個班級中。如何使用Java按字母順序排序鏈接列表？

我寫它的代碼來按字母順序排序，但它沒有工作。有人能告訴我我的代碼有什麼問題嗎？

這裏是我的鏈表類包含插入和顯示方法：

public class LinkedList 
{ 
Node node = new Node(); 
static Node head; 

public LinkedList() 
{ 
    head=null; 
} 

public Node getHead() 
{ 
    return head; 
} 

public static void addNode(Data data) 
{ 
    Node newNode = new Node(data, head); 

    if (head == null) { 
     head = newNode; 
     newNode.setNext(null); 
    } else { 
     Node next = head; 
     Node prev = next; 
    do { 
     if (data.name.compareTo(next.data.name) < 0) { 
      break; 
     } 
     prev = next; 
     next = next.getNext(); 
    } while (next != null); 

    newNode.setNext(next); 
    if (data.name.compareTo(next.data.name) < 0) { 
     head = newNode; 
    } else prev.setNext(newNode); 
} 
} 

public static String displayNode() 
{ 
    Node current = head; 
    String output = ""; 
    while(current != null){  
     output+=current.data.toString(); 
     current = current.next; 
    } 
    return output; 
}

這裏是我的節點類：

public class Node 
{ 
Data data; 
Node next; 

public Node() 
{ 
    next = null; 
} 

Node(Data data, Node next) 
{ 
    this.data = data; 
    this.next = next; 
} 

public Object getData() 
{ 
    return data; 
} 

public Node getNext() 
{ 
    return next; 
} 

public void setNext(Node next) 
{ 
    this.next=next; 
} 
}

這裏是我的數據類：

public class Data { 
LinkedList list; 
String name; 
String author; 
int isbn; 
int number; 
String genre; 

public Data(String name, String author, int isbn, int number, String genre) 
{ 
    this.name = name; 
    this.author = author; 
    this.isbn = isbn; 
    this.number = number; 
    this.genre = genre; 
} 

public String toString() 
{ 
    return("Book Name: "+name+"\nAuthor: "+author+"\nISBN Number: "+isbn+"\nNumber of Copies: "+number+"\nGenre: "+genre+"\n\n"); 
} 

public String getName() 
{ 
    return name; 
}

這裏是我用來顯示列表的Iterator類：

public class DisplayIterator 
{ 
LinkedList list; 
static Node current; 
static Node newNode; 

DisplayIterator(Node newNode) 
{ 
    this.newNode = newNode; 
    current = list.head; 
} 

public static boolean hasNext() 
{ 
    if(current == null){ 
     return false; 
    } 
    else if (current.next == null){ 
     return false; 
    } 
    return true; 
} 

public static Node next() 
{ 
    if(hasNext()){ 
     current = current.next; 
    } 
    return current; 
} 

public static void remove(){ 
    throw new UnsupportedOperationException("It is read-only.");   
} 

}

謝謝。

來源

2016-11-19 Acetamide

要添加的不是列表的頂部沒有任何順序排序豐富的庫。您的* while *循環在鏈表中運行，直到它被排序。如果你想排序鏈接列表，你應該在正確的位置添加新的節點，而不是總是在頂部。但是，如果我可以問，爲什麼不使用* Collection *？ –

你爲什麼要重新發明輪子？使用TreeSet和Comparable或Comparator接口。它們也是這樣做的，但它們是Java Lib的一部分。 – brummfondel

當然他應該使用「集合」，但我的猜測是該任務需要編寫自定義鏈表實現。 –

以下代碼實現基於訂單的插入到鏈接列表中。這當然假定列表已經排序。做出這個假設是安全的，因爲在你的接口中添加節點到鏈表的唯一方法是通過這種方法。

public static void addNode(Data data) { 
    Node newNode = new Node(data, head); 
    if (head == null) { 
     head = newNode; 
     return; 
    } 
    Node current = head; 
    while (current.next != null && data.name.compareTo(current.data.name) >= 0) { 
     current = current.next; 
    } 
    if (current == head && data.name.compareTo(current.data.name) < 0) { 
     newNode.next = head; 
     head = newNode; 
    } 
    else { 
     newNode.next = current.next; 
     current.next = newNode; 
    } 
    JOptionPane.showMessageDialog(null,"Book Information has been added to the inventory."); 
}

來源

2016-11-19 09:40:59

當我輸入第二個數據時，它顯示錯誤：線程中的異常「AWT-EventQueue-0」java.lang.NullPointerException＃ – Acetamide

@TimBiegeleisen我不認爲這處理的情況下，只有一個項目，並且將要插入的第二項插入頭部。 – rafid059

不過仍然沒有排序......我輸入d，a，c，b，然後它向我顯示d，a，c，b。另外我也使用迭代器實現來顯示它。 – Acetamide

我假設，您的Node不是來自java util LinkedList的，對不對？你能提供它的實現嗎？爲什麼它的構造函數是head？

您在開始處插入新元素並嘗試前進。並在您的循環結束current是第一個更大的和previous最後更小。直到現在正確。

但之後，您從不使用Previous，並將新元素設置爲您的。你需要插入它在previous和current之間。類似的東西：

if (previous == null) 
     head = newData; 
    else 
     previous.next = newData; 

    newData.next = current;

來源

2016-11-19 09:56:25 fairtrax

我明白了，明白了。謝謝！ – Acetamide

不客氣。但作爲一個保存元素的結構，它更適合堆。在java中，我會使用PriorityQueue併爲數據實現一個比較器。它效率更高。 – fairtrax

Java有數據

的任何集合

java.util.Collections.sort(YOURLIST_valiable)

來源

2016-11-19 10:19:17

如何使用Java按字母順序排序鏈接列表？

回答

相關問題