Java에서 링크드 목록을 수동으로 정렬하기 (어휘로)

Question

자바에서 내 자신의 링크 된 목록을 구현하고 있습니다. 노드 클래스에는 "name"이라는 문자열 필드와 "link"라는 노드가 있습니다. 지금은 여러 개의 이름을 순차적으로 삽입하는 테스트 드라이버 클래스가 있습니다. 자, 노드를 사전 순으로 정렬하는 정렬 방법을 쓰려고하는데 문제가 있습니다. 다른 사람의 게시물에서이 가상 코드를 발견하고이를 구현하려고 시도했지만 항목을 완전히 정렬하지 않았습니다. 나는 이유를 정말로 정말로 모르고있다. 모든 제안을 부탁드립니다!

Answer 1

나는 몇 분 동안 오류를 코드에 표시했지만 아무 것도 발견하지 못했습니다.

나는 더 똑똑한 사람이나 열심히 일하는 사람이 올 때까지 스스로 디버깅을 시도해야한다고 말하고 싶습니다. Eclipse와 같은 IDE를 사용하는 경우 변수의 값을 보면서 코드를 한 단계 씩 수행 할 수 있습니다. 그렇지 않다면 몇 군데에 print 문을 삽입하고 예상 한 내용을 직접 확인하십시오.

---

는 UPDATE I

난 당신의 코드를 복사하고 테스트했습니다. 그것이 내림차순으로 정렬한다는 것 (당신이 의도 한 것이 아닐 수도 있음) 외에도 0, 1 및 10 개의 무작위 노드 샘플에 대해 완벽하게 작동했습니다. 그럼 문제가 어디 있니?

UPDATE II

여전히 의미 할 수있는 것을 추측 "그것을하지 않습니다 완전히 정렬 항목." 사전 검색 분류 (예 : 'B'이전의 'a')가 예상 될 수 있으며 대문자와 소문자가 혼합 된 단어는 계획대로 나오지 않을 가능성이 있습니다. 이 경우의 해결책은 String 방법 compareToIgnoreCase(String str)을 사용하는 것입니다.

Answer 2

이것은 당신이 찾고있는 해결책이 아닐 수도 있지만, 멋지고 간단합니다. 아마 나처럼 게으른거야.

노드에는 데이터 항목이 하나뿐이므로 노드를 다시 셔플 할 필요가 없습니다. 노드의 값을 교환하는 동안 목록의 구조 자체를 그대로 유지하면서 간단하게 값을 교환 할 수 있습니다.

그런 식으로 버블 정렬을 아주 간단하게 구현할 수 있습니다.

Answer 3

언어별로 제공되는 정렬 절차를 사용해야합니다. 그런 다음 선택적으로 만들 수있는 Collections.sort(yourCollection)

을 사용할 수 있습니다 기본적으로

try this tutorial.

, 당신은 당신이 단지 obj.name.compareTo(other.name)

에 위임 할 것, java.lang.Comparable을 구현하기 위해 요소 클래스를 필요 객체를 비교하는 방법을 알고있는 java.util.Comparator

Answer 4

좋은 성능을 얻으려면 Merge Sort을 사용할 수 있습니다. 시간 복잡도는 O (n * log (n))이며 목록에 대한 메모리 오버 헤드없이 구현할 수 있습니다.

버블 정렬은 좋은 정렬 방법이 아닙니다. 자세한 내용은 What is a bubble sort good for?을 참조하십시오.

Answer 5

다소 늦을 수 있습니다. 연결된 목록을 정렬하는 것은 재미 없기 때문에 모든 것을 삽입하여 목록을 작성합니다.

저는 네 선생님이나 교수님이 자바 네이티브 라이브러리를 사용하기를 원하지 않는다고 확신합니다. 그러나,이 목록을 사용하는 진정한 빠른 방법은 없습니다.

은 모든 노드를 순서대로 읽은 다음 배열로 저장합니다. 어레이를 정렬 한 다음 노드를 다시 링크하십시오. 나는 Big-Oh의 복잡성이 O (n^2)가 될 것이라고 생각합니다. 실제로는 연결된 목록이있는 버블 정렬이 충분합니다.

Answer 6

단일 링크 된 목록에서 병합 정렬을 수행했으며 아래 코드가 있습니다.

public class SortLinkedList { 

public static Node sortLinkedList(Node node) { 

    if (node == null || node.next == null) { 
     return node; 
    } 
    Node fast = node; 
    Node mid = node; 
    Node midPrev = node; 
    while (fast != null && fast.next != null) { 
     fast = fast.next.next; 
     midPrev = mid; 
     mid = mid.next; 
    } 
    midPrev.next = null; 
    Node node1 = sortLinkedList(node); 
    Node node2 = sortLinkedList(mid); 
    Node result = mergeTwoSortedLinkedLists(node1, node2); 
    return result; 
} 

public static Node mergeTwoSortedLinkedLists(Node node1, Node node2) { 
    if (null == node1 && node2 != null) { 
     return node2; 
    } else if (null == node2 && node1 != null) { 
     return node1; 
    } else if (null == node1 && null == node2) { 
     return null; 
    } else { 

     Node result = node1.data <= node2.data ? node1 : node2; 
     Node prev1 = null; 
     while (node1 != null && node2 != null) { 
      if (node1.data <= node2.data) { 
       prev1 = node1; 
       node1 = node1.next; 
      } else { 
       Node next2 = node2.next; 
       node2.next = node1; 
       if (prev1 != null) { 
        prev1.next = node2; 
       } 
       node1 = node2; 
       node2 = next2; 
      } 
     } 
     if (node1 == null && node2 != null) { 
      prev1.next = node2; 
     } 
     return result; 
    } 
} 

public static void traverseNode(Node node) { 
    while (node != null) { 
     System.out.print(node + " "); 
     node = node.next; 
    } 
    System.out.println(); 

} 

public static void main(String[] args) { 
    MyLinkedList ll1 = new MyLinkedList(); 

    ll1.insertAtEnd(10); 
    ll1.insertAtEnd(2); 
    ll1.insertAtEnd(20); 
    ll1.insertAtEnd(4); 
    ll1.insertAtEnd(9); 
    ll1.insertAtEnd(7); 
    ll1.insertAtEnd(15); 
    ll1.insertAtEnd(-3); 
    System.out.print("list: "); 
    ll1.traverse(); 
    System.out.println(); 
    traverseNode(sortLinkedList(ll1.start)); 

} 

}

노드 클래스 :

public class Node { 
int data; 
Node next; 

public Node() { 
    data = 0; 
    next = null; 
} 

public Node(int data) { 
    this.data = data; 
} 

public int getData() { 
    return this.data; 
} 

public Node getNext() { 
    return this.next; 
} 

public void setData(int data) { 
    this.data = data; 
} 

public void setNext(Node next) { 
    this.next = next; 
} 

@Override 
public String toString() { 
    return "[ " + data + " ]"; 
} 

}

MyLinkedList 클래스 :

public class MyLinkedList { 
Node start; 

public void insertAtEnd(int data) { 
    Node newNode = new Node(data); 
    if (start == null) { 
     start = newNode; 
     return; 
    } 
    Node traverse = start; 
    while (traverse.getNext() != null) { 
     traverse = traverse.getNext(); 
    } 
    traverse.setNext(newNode); 
} 

public void traverse() { 
    if (start == null) 
     System.out.println("List is empty"); 
    else { 
     Node tempNode = start; 
     do { 
      System.out.print(tempNode.getData() + " "); 
      tempNode = tempNode.getNext(); 
     } while (tempNode != null); 
     System.out.println(); 
    } 
} 

}