사용자 지정 연결 목록을 사용하여 정렬을 어떻게 구현해야합니까?

Question

나는 어떻게 링크 목록이 작동하는지 알아 내려고 노력했지만 개념을 시각화하는 데 어려움을 겪고있다. 여러 알고리즘을 알고 있지만 구현 방법을 알 수는 없습니다.

public class LL { 
    private ListNode front,last; 

    public LL(){ 
     front = null; last = null; 
    } 

    // 
    //methods here... 
    // 

    public class ListNode{ 
     public double coefficient; 
     public int exponent; 
     public ListNode next; 

     public ListNode(){ 
      this(0, 0, null); 
     } 

     public ListNode(double coefficient, int exponent, ListNode next){ 
      this.coefficient = coefficient; 
      this.exponent = exponent; 
      this.next = next; 
     } 
    } 
} 

이 다항식의 데이터를 저장하기위한 것입니다 :

여기 내 코드입니다. 나는 그들에게 내림차순으로 가도록 노력하고있다. 결국 노드의 계수를 같은 지수로 더합니다.

거품 정렬 알고리즘을 사용할 것 같지만 링크를 어떻게 다시 배열 할 것인지 알 수 없습니다. 나는 또한 remove() 메소드를 추가하고 하나의 노드를 제거하고 정렬 될 때까지 끝에 추가하려고 생각했다. 하지만 매번 새로운 노드를 만들어야하기 때문에 이는 매우 비효율적입니다.

추신 : 나 또한 문자열을 가져 와서 LL로 바꾸는 다항식 클래스가 있습니다. 나는 그것을 게시하는 것이 필요하다고 생각하지 않지만 당신이 그것을 필요로한다면 나는 그것을 게시 할 것입니다! 감사합니다. 연결리스트를 정렬

Answer 1

는 당신이, 당신이 정말로 스파 스 indecies이 BTW 않는합니다 (JDK가하는 일이있다)

을 일반적으로 당신이 그들을 정렬 배열로 목록리스트를 복사합니다 그들을 다시 복사, 정말 비효율적이다 배열 또는 배열 목록을 사용하는 것이 더 좋습니다. 이것은 단순하고 효율적이며 빠르며 자연스럽게 정렬됩니다.

계수가 거의없는 경우에도 배열은 메모리와 연결된 목록의 일부를 사용합니다.