單連結清單之排序單連結清單

package list;

public class SortedSinglyList<T extends Comparable<? super T>> extends SinglyList {

	/*
	 * 構造空排序單連結清單
	 */
	public SortedSinglyList() {
		super(); // 直接調用單連結清單的構造方法，構造一個空的單連結清單
	}

	/*
	 * 将values數組中的所有對象按值大小插入
	 */
	public SortedSinglyList(T[] values) {
		super();
		for (int i = 0; i < values.length; i++)
			this.insert(values[i]); // 調用重載插入方法，這裡的插入方法在父類的方法上進行重載，可以進行順序插入
	}

	/*
	 * 重載深拷貝，由單連結清單建構排序單連結清單
	 */
	public SortedSinglyList(SinglyList<T> list) {
		super(); // 調用無參構造方法，構造一個空的排序單連結清單
		for (Node<T> p = list.head.next; p != null; p = p.next)
			this.insert(p.data); // 構造好空的排序單連結清單後，開始插入資料
	}

	/*
	 * 深拷貝構造方法，這個方法和上面内容基本一緻，差的就是list的類型不同，但是原理是一樣的
	 */
	@SuppressWarnings("unchecked") // 如果方法中有警告，用了這句話就沒有警告了，但是沒什麼實際叼用
	public SortedSinglyList(SortedSinglyList<T> list) {
		super(list);
	}

	/*
	 * 設定節點内容，但是排序單連結清單中不支援，是以要覆寫掉，然後抛出異常 這裡如果不寫，就會調用父類的set方法，這樣你的連結清單就不是排序的了
	 */
	public void set(int i, T x) {
		throw new java.lang.UnsupportedOperationException("set(int i,T x)");
	}

	/*
	 * 原理同上，就不多說了
	 */
	public Node<T> insert(int i, T x) {
		throw new java.lang.UnsupportedOperationException("set(int i,T x)");
	}

	/*
	 * 這是最關鍵的地方了，順序插入節點，時間複雜度為O(n)
	 */
	public Node<T> insert(T x) {
		Node<T> front = this.head, p = front.next;

		while (p != null && x.compareTo(p.data) > 0) {
			front = p;
			p = front.next;
		}
		front.next = new Node<T>(x, p);
		return front.next; // 傳回插入節點
	}

	/*
	 * 好了剩下的一些方法，都可以繼承單連結清單的方法，這裡就不再一一講述了
	 */

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
           

注意，這裡的排序單連結清單裡面有很多方法沒有寫，不是因為省略了，而是因為它已經繼承了父類單連結清單中的方法（詳細代碼，可以檢視我的上一篇部落格）

參考書籍：《資料結構（java版）》葉核亞，有不懂的，可以再看一下這本書