2014-12-07 152 views
0

我試圖實現一個有插入,刪除,並檢查整數是否存在方法的排序鏈接列表,我目前無法理解爲什麼我的插入方法工作不正確。它將整數插入鏈表中,但它們向後排序,我嘗試過移動條件,但它不能按照它的方式工作。插入排序的鏈接列表

void insert(int x){ 
    LinkedList newLink = new LinkedList(x); 
    if (front == null) { 
     front = newLink; 
    } else if (x > front.x){ 
     newLink.next = front; 
     front = newLink; 
    } else { 
     LinkedList current = front.next; 
     LinkedList before = front; 
     while (current != null){ 
      if (x < front.x) { 
       before = current; 
       current = current.next; 
      } 
      newLink.next = before.next; 
      before.next = newLink; 
     } 
    } 
} 
+0

嗯,如果'x'大於你當前的頭,然後你*預計*它到你的名單。這就是使列表按降序排列的原因。 – 5gon12eder 2014-12-07 21:22:55

回答

0

我認爲這將解決您的問題,再加上,我添加了一些意見讓你瞭解我的變化在你的代碼:

void insert(int x) { 
    LinkedList newLink = new LinkedList(x); 
    if (front == null) { 
     front = newLink; 
     // insert in head if x is lower than the head 
    } else if (x <= front.x) { 
     newLink.next = front; 
     front = newLink; 
    } else { 
     // find the first node which value is lower than x (or the tail) 
     LinkedList current; 
     for (current = front; current.next != null && x >= current.next.x ; current = current.next); 
     // to remove duplicates 
     if (x != current.x) { 
      newLink.next = current.next; 
      current.next = newLink; 
     } 
    } 
} 
+0

我認爲在for循環中的條件是防止我添加超過2個整數值,我試圖插入'1'和'3',並工作,但試圖插入'2'失敗。儘管這幫助了一噸,但它現在正在升序排列。 – kamahl 2014-12-07 21:47:38

+0

它是如何失敗?異常?錯誤的輸出? – Dici 2014-12-07 22:06:04

+0

我沒有得到一個異常,它沒有輸出任何東西,這是我的控制檯看起來像http://imgur.com/AhwM1Oq我使用toString();輸出鏈接列表 – kamahl 2014-12-07 22:27:25

0
else if (x > front.x){ 
    newLink.next = front; 
    front = newLink; 
} 

如果新的鏈接比前面更大,使新節點front節點,它的下一個節點設置爲最近前面。您按逆序排序順序插入列表的前面。

if (x < front.x) { 
    before = current; 
    current = current.next; 
} 

你總是比較的front節點爲好,不是你的current節點。

0

附上我的實現。請使用和修改您的需求。

注意!這個實現將會降低相同的值!

/****************************************************************** 
* Adds the given string to the sorted list. If the string already 
* is in the list, then the list will not be modified. 
* 
* @param list The sorted list of strings 
* @param str The string to be inserted if not there already 
* @return Returns true if the list has changed otherwise false 
*/ 
public static boolean 
add2SortedList(List<String> list, String str) { 
    int res = 0; 

    //--- Loop through list from end to front 
    for (int i = list.size() - 1; i >= 0 ; i--) { 

     //--- Compare to current entry 
     res = str.compareTo(list.get(i)); 

     //--- Already in list => return 
     if (res == 0) 
      return false; 

     //--- Bigger than current one => insert after 
     if (res > 0) { 
      list.add(i + 1, str); 
      return true; 
     } 
    } 

    //--- Insert at head of list 
    list.add(0, str); 
    return true; 
} 


/****************************************************************** 
* Adds the given value to the sorted list if its not already there. 
* 
* @param list the sorted list of values 
* @param value the value to be inserted if not there already 
* @return returns true when value was added, else false 
*/ 
public static boolean 
add2SortedSet(List<Integer> list, Integer value) 
{ 
    int size = list.size(); 
    for (int i = 0 ; i < size ; i++) 
    { 
     int res = value.compareTo (list.get(i)); 

     //----- Insert before this element 
     if (res < 0) { 
      list.add(i, value); 
      return true ; 
     } 

     //----- New element already in list 
     if (res == 0) 
      return false ; 
    } 

    //----- Append to end of list 
    list.add (value); 
    return true ; 
} 
-1

默認方式在一個LinkedList插入:

LinkedList<Integer> myList = new LinkedList<>(); 

myList.add(238); 
myList.add(7); 
..   
Collections.sort(myList); 

http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

了不同的排序方式使用接口可比

+0

根本沒有回答這個問題,因爲我們正在討論鏈接列表數據結構的自定義實現 – Dici 2014-12-07 22:49:13