add方法应按排序顺序将元素插入列表中

Question

我已经完成了将元素添加到LinkedList中的代码。现在，我想按排序顺序将元素插入到列表中。我该怎么做？

         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;
                      }          
                  }

我的Main类是Linkedlist和arraylist的类，它调用SimpleLinkedList类和SimpleArrayListClass 的方法

            package Comp10152_linkedlist;

            import java.util.Random;
            public class Comp10152_Lab4 
            {
               public static void main(String[] args)
              {
                final int NUMBER_OF_ITERATIONS = 10;
                String names[] = {"Amy", "Bob", "Al", "Beth", "Carol", "Zed", "Aaron"};
                SimpleLinkedList ll = new SimpleLinkedList();
                final int TOTALOPERATIONS = names.length * NUMBER_OF_ITERATIONS;
                Random random = new Random();
                for (int i=0; i<NUMBER_OF_ITERATIONS;i++)
                {
                  for (int j=0; j<names.length; j++)
                    ll.add(names[j]);
                }
                 System.out.println("The members of list are:");
                  System.out.println(ll);
                // remove half of the items in the list by selecting randomly from names
                for (int i=0; i<TOTALOPERATIONS/2;i++)
                {
                  ll.remove(names[random.nextInt(names.length)]);
                }
                System.out.println("The members of list are:");
                  System.out.println(ll);
                SimpleArrayList al = new SimpleArrayList();
                try
                {
                for (int i=0; i<NUMBER_OF_ITERATIONS;i++)
                {
                  for (int j=0;j<names.length;j++)
                     al.add(i,names[j]);
                }
                  System.out.println("The members of array are:");
                  System.out.println(al);
                // remove half of the items in the list by selecting randomly from names
                for (int i=0; i<TOTALOPERATIONS/2;i++)
                {
                  al.remove(names[random.nextInt(names.length)]);
                }   
                 System.out.println("The members of array are:");
                  System.out.println(al);
                }
                catch (Exception e)
                {
                    System.out.println(e);
                }
              }     
            }

Answer 1

首先插入列表之外的元素，然后通过调用add方法插入到列表中。如何对列表外的元素进行排序取决于您使用的数据结构、数据类型以及要应用的算法。

Answer 2

插入列表时，按排序顺序添加。首先搜索排序列表中大于该元素的元素，然后搜索要插入的元素，再在此之前添加新元素。

类似。。

//Considering ascending order
public void add(String element) {
    if(isEmpty) {
        first = new Node(element);
        last = first;
    } else {
        currentNode = first;
        while(currentNode.next != null && currentNode.next.element > element) {
            currentNode = currentNode.next;
        }
        Node newNode = new Node(element);
        newNode.next = currentNode.next;
        currentNode.next = newNode;
    }
}