Java数据结构

Question

求数据排序方法。
一个List中包含许多Node.要用到如下的数据结构,尽量不要用Java包里的方法。
static class Node { 
int val; 
Node next; 
Node(int v) { 
val = v; 
} 
} 

Answer 1

/* 链表的插入排序*/
public class LinkedChainList<T extends Comparable<? super T>>
       implements ListInterface<T>
{
  private Node firstNode;
  int length;
//  . . .
  
private void insertInOrder(Node nodeToInsert)
{
  T item = nodeToInsert.getData();
  Node currentNode = firstNode;
  Node previousNode = null;
  
  // locate insertion point
  while ( (currentNode != null) && 
          (item.compareTo(currentNode.getData()) > 0) )
  {
    previousNode = currentNode;
    currentNode = currentNode.getNextNode();
  } // end while
  
  // make the insertion
  if (previousNode != null)
  { // insert between previousNode and currentNode
    previousNode.setNextNode(nodeToInsert);
    nodeToInsert.setNextNode(currentNode);
  }
  else // insert at beginning
  {
    nodeToInsert.setNextNode(firstNode);
    firstNode = nodeToInsert;
  } // end if
} // end insertInOrder
} // end LinkedChainList