鏈接列表中的排序列表

Question

我已經編寫了此代碼來插入元素並將其移除並形成鏈接列表。我想在排序列表中插入元素到列表中。我怎樣才能改進我的「添加」方法來做到這一點？

public void add(String element) 
     { 
     if (isEmpty()) 
      { 
       first = new Node(element); 
       last = first; 
      } 
      else 
      { 
       // Add to end of existing list 
       last.next = new Node(element); 
       last = last.next; 
     } 

     } 

     /** 
     * The toString method computes the string representation of the list. 
     * 
     * @return The string form of the list. 
     */ 
     public String toString() 
     { 
     StringBuilder strBuilder = new StringBuilder(); 

     // Use p to walk down the linked list 
     Node p = first; 
     while (p != null) { 
      strBuilder.append("[" + p.value + "]"); 
      p = p.next; 
     } 
     return strBuilder.toString(); 
     } 


      The remove method removes an element. 
      @param element The element to remove. 
      @return true if the remove succeeded, 
      false otherwise. 


     public boolean remove(String element) 
     { 
      if (isEmpty()) 
       return false;  

      if (element.equals(first.value)) 
      { 
       // Removal of first item in the list 
       first = first.next; 
       if (first == null) 
        last = null;  
       return true; 
      } 

      // Find the predecessor of the element to remove 
      Node pred = first; 
      while (pred.next != null && 
       !pred.next.value.equals(element)) 
      { 
       pred = pred.next; 
      } 

      // pred.next == null OR pred.next.value is element 
      if (pred.next == null) 
       return false; 

      // pred.next.value is element 
      pred.next = pred.next.next;  

      // Check if pred is now last 
      if (pred.next == null) 
       last = pred; 

      return true;  
     } 

Answer 1

這是一個排序的鏈接列表。插入時，我們可以將它插入正確的位置。

1）如果列表爲空，則將第一個和最後一個作爲新元素。否則

2）如果新元素小於第一個節點，則將新元素設置爲第一個。否則

3）遍歷整個列表，找到一個位置，其中前一個節點較小，下一個節點較大或爲空。將新節點插入此位置

因此，使用此方法我們可以保持列表始終排序。

public void add(String element) 
    { 
     Node newNode = new Node(element); 
     if (isEmpty()) 
     { 
      first = newNode; 
      last = newNode; 
     } 
     else if (element.compareTo(first.value) < 0)//if element is lesser than all elements in list 
     { 
     newNode.next = first; 
     first= newNode; 
     } 
     else 
     { 
     Node after = first.next; 
     Node before = first; 
     while (after != null)// finding exact position to insert 
     { 
      if (element.compareTo(after.value) < 0) 
       break; 
      before = after; 
      after = after.next; 
     } 
     // insert between before & after 
     newNode.next = before.next; 
     before.next = newNode; 
     } 

    } 

Answer 2

這應該工作：

public void addElementInSortOrder(final List<String> list, final String element) { 
    if (list.isEmpty()) { 
     list.add(element); 
    } else { 
     // look for the correct index 
     int index = list.size(); 
     for (int i = 0; i < list.size(); i++) { 
      if (list.get(i).compareTo(element) >= 0) { 
       index = i; 
       break; 
      } 
     } 
     list.add(index, element); 
    } 
}