Java: добавление функции сортировки в самонесущий двусвязный список

Question

Я пытаюсь реализовать функцию сортировки в этом коде, которая создает двусвязный список.

Я не знаю, с чего начать, кроме добавления «реализует сравнимые». После этого я просто в недоумении, что делать дальше.

public class MyLinkedList<AnyType> implements Comparable<AnyType>, Iterable<AnyType> 
{ 
    private int theSize; 
    private Node<AnyType> beginMarker; 
    private Node<AnyType> endMarker; 

    public MyLinkedList() 
    { 
     clear(); 
    } 

    private static class Node<AnyType> 
    { 
     public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) 
     { 
      data = d; prev = p; next = n; 
     } 

     public AnyType data; 
     public Node<AnyType> prev; 
     public Node<AnyType> next; 
    } 

    public void clear() 
    { 
     beginMarker = new Node<AnyType>(null, null, null); 
     endMarker = new Node<AnyType>(null, beginMarker, null); 
     beginMarker.next = endMarker; 

     theSize = 0; 
    } 

    public int size() 
    { 
     return theSize; 
    } 

    public boolean isEmpty() 
    { 
     return size() == 0; 
    } 

    public boolean add(AnyType x) 
    { 
     add(size(), x); 
     return true;   
    } 

    public void add(int idx, AnyType x) 
    { 
     addBefore(getNode(idx, 0, size()), x); 
    } 

    private void addBefore(Node<AnyType> p, AnyType x) 
    { 
     Node<AnyType> newNode = new Node<AnyType>(x, p.prev, p); 
     newNode.prev.next = newNode; 
     p.prev = newNode;   
     theSize++; 
    } 

    public AnyType get(int idx) 
    { 
     return getNode(idx).data; 
    } 

    public AnyType set(int idx, AnyType newVal) 
    { 
     Node<AnyType> p = getNode(idx); 
     AnyType oldVal = p.data; 

     p.data = newVal; 
     return oldVal; 
    } 


    private Node<AnyType> getNode(int idx) 
    { 
     return getNode(idx, 0, size() - 1); 
    } 

    private Node<AnyType> getNode(int idx, int lower, int upper) 
    { 
     Node<AnyType> p; 

     if(idx < lower || idx > upper) 
      throw new IndexOutOfBoundsException("getNode index: " + idx + "; size: " + size()); 

     if(idx < size()/2) 
     { 
      p = beginMarker.next; 
      for(int i = 0; i < idx; i++) 
       p = p.next;    
     } 
     else 
     { 
      p = endMarker; 
      for(int i = size(); i > idx; i--) 
       p = p.prev; 
     } 

     return p; 
    } 

    public AnyType remove(int idx) 
    { 
     return remove(getNode(idx)); 
    } 

    private AnyType remove(Node<AnyType> p) 
    { 
     p.next.prev = p.prev; 
     p.prev.next = p.next; 
     theSize--; 

     return p.data; 
    } 

    public String toString() 
    { 
     StringBuilder sb = new StringBuilder("[ "); 

     for(AnyType x : this) 
      sb.append(x + " "); 
     sb.append("]"); 

     return new String(sb); 
    } 

    public java.util.Iterator<AnyType> iterator() 
    { 
     return new LinkedListIterator(); 
    } 

    private class LinkedListIterator implements java.util.Iterator<AnyType> 
    { 
     private Node<AnyType> current = beginMarker.next; 
     private boolean okToRemove = false; 

     public boolean hasNext() 
     { 
      return current != endMarker; 
     } 

     public AnyType next() 
     { 
      if(!hasNext()) 
       throw new java.util.NoSuchElementException(); 

      AnyType nextItem = current.data; 
      current = current.next; 
      okToRemove = true; 
      return nextItem; 
     } 

     public void remove() 
     { 
      if(!okToRemove) 
       throw new IllegalStateException(); 

      MyLinkedList.this.remove(current.prev); 
      okToRemove = false;  
     } 
    } 

    public int compareTo(AnyType other) 
    { 
     return this.compareTo(other); 
    } 

Answer 1

Обычно вы хотите, чтобы ваш список реализовал интерфейс Collection и элементы в списке для реализации Comparable (который включает в себя реализацию compareTo() в любом типе, который вы добавляете в список). Вы можете сильно набрать это, потребовав, чтобы типы элементов списка реализовали Comparable. Сокращение может заключаться в расширении другого типа Collection, такого как LinkedList, и улучшении его с помощью обратного списка.

Как правило, однако, если вы ищете реализацию чужой двойной ссылки. Возможно, попробуйте Google Guava? - http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained

Answer 2

Связанный список - это наихудшая возможная структура данных для сортировки. Один простой подход (который можно рассматривать как чит) - это сопоставление списка в массив, сортировка массива, затем восстановление списка.

Если вы должны реализовать весь алгоритм сортировки (для вашего класса?), То каждый из них имеет базовый примитив сортировки , обычно «обмен», который вы должны реализовать.

В любом случае следите за идентификацией корневого элемента списка.