0

我想知道这在Java中是否可行。我想按字母顺序将其插入正确的位置。例如，LinkedList 的（假设它被称为coollist）元素是：[Dusty, Gordon, Mayer, Popovic, Zechariah] 我尝试通过执行以下操作插入另一个字符串：

    coollist.add(d,Nyugen); //d is a a variable representing ant int which is the index

无论 LinkedList 中有什么，我该怎么做才能使 d 成为按字母顺序插入它的值？你们能帮帮我吗？我希望这是有道理的。

4

3 回答 3

1

您可以遍历列表，搜索索引何时生成大于参数的字符串。然后只需插入该索引后面。如果这是一个单向链表，您必须跟踪前一个节点，以便更新其字段。

    Node newNode = new Node( stringToBeAdded ); //Create new node

    if ( this.head == null ){ //list is empty, just insert
      this.head = newNode; //Initialize head
    }

    else{

      Node cur = this.head; //Start at the beginning of the list
      Node prev = this.head; //just initialize the previous node to something

      //keep going until found or at end of list
      while( (stringToBeAdded < cur.data) && (cur != null) ){ 
        prev = cur;
        cur = cur.next;
      }

      prev.next = newNode;

      if ( cur != null ){ //if we did not reach the end
        newNode.next = cur; //current Node is alphabetically greater
      }
    }
于 2013-10-09T04:10:45.827 回答
1

以下是在 LinkedList 中查找排序索引的一种方法。

import java.util.*;

public class SortedLinkedListDemo {

public static void main (String [] args) {
    List<String> list = new LinkedList<String> ();
    list.add ("Dusty");
    list.add ("Gordon");
    list.add ("Mayer");
    list.add ("Popovic");
    list.add ("Zechariah");

    list.add (getSortedIndex ("Nyugen", list), "Nyugen");

    System.out.println ("List: "+list);
}

private static int getSortedIndex (String name, List<String> list) {
    for (int i=0; i < list.size(); i++) {
        if (name.compareTo(list.get(i)) < 0) {
            return i;
        }
    }       
    // name should be inserted at end.
    return list.size();
}

}

这将给出以下输出：

名单：[Dusty、Gordon、Mayer、Nyugen、Popovic、Zechariah]

于 2013-10-09T04:40:10.377 回答
0

搜索链表需要 O(n)。但是由于您的数据已排序，因此放置下一个字符串是找到正确位置的问题。在另一个由数组支持的数据结构中，这是通过二进制搜索完成的，需要 O(log n)。请参阅评论中的 lreeder 链接。当然，您始终可以自己查看列表并插入字符串，但这不是链表最擅长的。

于 2013-10-09T04:01:42.387 回答