Связанный список manual Алфавитная сортировка

Question

Я работаю с linkedlists на данный момент в java. Наше задание состояло в том, чтобы создать его с нуля, что сортирует пользовательский ввод (строки) в алфавитном порядке. Я много чего пытался, но ни одна из концепций, которые я придумываю, похоже, не работает. Любые советы/советы будут оценены.

package linkedlist; 
public class Linked { 

    Node head; 
    int listCount;  

    public Linked(){ 
     head = new Node(null); 
     listCount = 0; 
    } 
    public void add(String data){ 
     Node linkedTemp = new Node(data); 
     Node linkedCurrent = head; 
     while (linkedCurrent.getNext() != null) { 
       linkedCurrent = linkedCurrent.getNext(); 
       } 
     linkedCurrent.setNext(linkedTemp); 
     listCount++; 

    } 

    public void add2(String data){ 
     Node linkedTemp = new Node(data); 
     Node linkedCurrent = new Node(get(1)); 

     if(listCount >= 1){ 

      while (linkedCurrent.getNext() != null){ 

       if(linkedCurrent.getData().compareTo(linkedTemp.getData()) <= 0){ 
        linkedCurrent.setNext(linkedTemp); 
        listCount++; 
        break; 
       } 
       if(linkedCurrent.getData().compareTo(linkedTemp.getData()) >= 0) 
       linkedCurrent = linkedCurrent.getNext(); 
     } 
    } 
    } 

    public String toString() { 
     Node linkedCurrent = head.getNext(); 
     String output = ""; 
     while (linkedCurrent != null) { 
      output += "[" + linkedCurrent.getData().toString() + "]"; 
      linkedCurrent = linkedCurrent.getNext(); 
     } 
     return output; 
    } 
    public String get(int index) 
    { 
     if (index <= 0) 
      return null; 

     Node linkedCurrent = head.getNext(); 
     for (int i = 1; i < index; i++) { 
      if (linkedCurrent.getNext() == null) 
       return null; 

      linkedCurrent = linkedCurrent.getNext(); 
     } 
     return linkedCurrent.getData(); 
    } 
} 

Answer 1

За исключением случаев, когда сортировка не работает, я думаю, что ваш код в порядке. Например,

public static void main(String[] args) { 
    Linked linked = new Linked(); 
    linked.add("data3"); 
    linked.add("data2"); 
    linked.add("data1"); 
    System.out.println(linked); 

    System.out.println(linked.get(1)); 
    System.out.println(linked.get(2)); 
    System.out.println(linked.get(3)); 
    System.out.println(linked.get(4)); 
} 

Вышеуказанный тестовый код дает результат, который соответствует нашим ожиданиям.

[data3][data2][data1] 
data3 
data2 
data1 
null 

Но, как я уже сказал, дело в том, что сортировочная часть проблемы не решена. Чтобы решить проблему, я думаю, вам следует изменить часть кода «добавить». Ваш метод add не учитывает порядок вставленных элементов.

public void add(String data){ 
    Node linkedTemp = new Node(data); 
    Node linkedCurrent = head; 
    Node linkedPrev = head; 
    while (linkedCurrent != null) { 
     if (linkedCurrent.getData() != null && linkedCurrent.getData().compareTo(data) > 0) { 
      break;    
     } 
     linkedPrev = linkedCurrent; 
     linkedCurrent = linkedCurrent.getNext(); 
    } 
    linkedTemp.setNext(linkedPrev.getNext()); 
    linkedPrev.setNext(linkedTemp); 
    listCount++; 
} 

Как ваш код, используя «нулевую голову», которая содержит бессмысленные данные, добавленный if блока внутри проверки while заявления, если linkedCurrent.getData() не равно нуля.

После указанной модификации метода add, выход становится:

[data1][data2][data3] 
data1 
data2 
data3 
null