Java模仿有序鏈表數據構造的示例

Java模仿有序鏈表數據構造的示例。本站提示廣大學習愛好者：（Java模仿有序鏈表數據構造的示例）文章只能為提供參考，不一定能成為您想要的結果。以下是Java模仿有序鏈表數據構造的示例正文

有序鏈表：
按症結值排序。刪除鏈頭時，就刪除最小(/最年夜)的值，拔出時，搜刮拔出的地位。
拔出時須要比擬O(N)，均勻O(N/2)，刪除最小(/最年夜)的在鏈頭的數據時效力為O(1),
假如一個運用須要頻仍的存取(拔出/查找/刪除)最小(/最年夜)的數據項，那末有序鏈表是一個不錯的選擇
優先級隊列 可使用有序鏈表來完成
有序鏈表的拔出排序：
對一個無序數組，用有序鏈表來排序，比擬的時光級照樣O(N^2)
復制時光級為O(2*N)，由於復制的次數較少，第一次放進鏈表數據挪動N次，再從鏈表復制到數組，又是N次
每拔出一個新的鏈結點，不須要復制挪動數據，只須要轉變一兩個鏈結點的鏈域

import java.util.Arrays; 
import java.util.Random; 
 
/** 
 * 有序鏈表 對數組停止拔出排序 
 * @author stone 
 */ 
public class LinkedListInsertSort<T extends Comparable<T>> { 
   
  private Link<T> first;    //首結點 
  public LinkedListInsertSort() { 
     
  } 
   
  public boolean isEmpty() { 
    return first == null; 
  } 
   
  public void sortList(T[] ary) { 
    if (ary == null) { 
      return; 
    } 
    //將數組元素拔出進鏈表,以有序鏈表停止排序 
    for (T data : ary) { 
      insert(data); 
    } 
    // 
     
  } 
   
  public void insert(T data) {// 拔出 到 鏈頭, 以從小到年夜排序 
    Link<T> newLink = new Link<T>(data); 
    Link<T> current = first, previous = null; 
    while (current != null && data.compareTo(current.data) > 0) { 
      previous = current; 
      current = current.next; 
    } 
    if (previous == null) { 
      first = newLink; 
    } else { 
      previous.next = newLink; 
    } 
    newLink.next = current; 
  } 
   
  public Link<T> deleteFirst() {//刪除 鏈頭 
    Link<T> temp = first; 
    first = first.next; //變革首結點，為下一結點 
    return temp; 
  } 
   
  public Link<T> find(T t) { 
    Link<T> find = first; 
    while (find != null) { 
      if (!find.data.equals(t)) { 
        find = find.next; 
      } else { 
        break; 
      } 
    } 
    return find; 
  } 
   
  public Link<T> delete(T t) { 
    if (isEmpty()) { 
      return null; 
    } else { 
      if (first.data.equals(t)) { 
        Link<T> temp = first; 
        first = first.next; //變革首結點，為下一結點 
        return temp; 
      } 
    } 
    Link<T> p = first; 
    Link<T> q = first; 
    while (!p.data.equals(t)) { 
      if (p.next == null) {//表現到鏈尾還沒找到 
        return null; 
      } else { 
        q = p; 
        p = p.next; 
      } 
    } 
     
    q.next = p.next; 
    return p; 
  } 
   
  public void displayList() {//遍歷 
    System.out.println("List (first-->last):"); 
    Link<T> current = first; 
    while (current != null) { 
      current.displayLink(); 
      current = current.next; 
    } 
  } 
   
  public void displayListReverse() {//反序遍歷 
    Link<T> p = first, q = first.next, t; 
    while (q != null) {//指針反向，遍歷的數據次序向後 
      t = q.next; //no3 
      if (p == first) {// 當為本來的頭時，頭的.next應當置空 
        p.next = null; 
      } 
      q.next = p;// no3 -> no1 pointer reverse 
      p = q; //start is reverse 
      q = t; //no3 start 
    } 
    //下面輪回中的if裡，把first.next 置空了, 而當q為null不履行輪回時，p就為本來的最且一個數據項，反轉後把p賦給first 
    first = p;  
    displayList(); 
  } 
   
  class Link<T> {//鏈結點 
    T data;   //數據域 
    Link<T> next; //後繼指針，結點    鏈域 
    Link(T data) { 
      this.data = data; 
    } 
    void displayLink() { 
      System.out.println("the data is " + data.toString()); 
    } 
  } 
   
  public static void main(String[] args) { 
    LinkedListInsertSort<Integer> list = new LinkedListInsertSort<Integer>(); 
    Random random = new Random(); 
    int len = 5; 
    Integer[] ary = new Integer[len]; 
    for (int i = 0; i < len; i++) { 
      ary[i] = random.nextInt(1000); 
    } 
    System.out.println("----排序前----"); 
    System.out.println(Arrays.toString(ary)); 
    System.out.println("----鏈表排序後----"); 
    list.sortList(ary); 
    list.displayList(); 
  } 
} 

打印

----排序前---- 
[595, 725, 310, 702, 444] 
----鏈表排序後---- 
List (first-->last): 
the data is 310 
the data is 444 
the data is 595 
the data is 702 
the data is 725 

單鏈表反序:

public class SingleLinkedListReverse { 
   
  public static void main(String[] args) { 
    Node head = new Node(0); 
    Node temp = null; 
    Node cur = null; 
     
    for (int i = 1; i <= 10; i++) { 
      temp = new Node(i); 
      if (i == 1) { 
        head.setNext(temp); 
      } else { 
        cur.setNext(temp); 
      } 
      cur = temp; 
    }//10.next = null; 
     
    Node h = head; 
    while (h != null) { 
      System.out.print(h.getData() + "\t"); 
      h = h.getNext(); 
    } 
    System.out.println(); 
     
    //反轉1 
//   h = Node.reverse1(head); 
//   while (h != null) { 
//     System.out.print(h.getData() + "\t"); 
//     h = h.getNext(); 
//   } 
     
    //反轉2 
    h = Node.reverse1(head); 
    while (h != null) { 
      System.out.print(h.getData() + "\t"); 
      h = h.getNext(); 
    } 
     
     
  } 
} 
 
/* 
 * 單鏈表的每一個節點都含有指向下一個節點屬性 
 */ 
class Node { 
  Object data;//數據對象  
  Node next; //下一節點 
   
  Node(Object d) { 
    this.data = d; 
  } 
  Node(Object d, Node n) { 
    this.data = d; 
    this.next = n; 
  } 
  public Object getData() { 
    return data; 
  } 
  public void setData(Object data) { 
    this.data = data; 
  } 
  public Node getNext() { 
    return next; 
  } 
  public void setNext(Node next) { 
    this.next = next; 
  } 
  //辦法1 head被重置 
  static Node reverse1(Node head) { 
 
    Node p = null; //反轉後新的 頭 
    Node q = head; 
    //輪換成果：012,123,234,.... 10 null null 
    while (head.next != null) { 
      p = head.next;   // 第1個 換成第2個 這時候p表現原始序列頭中的next 
      head.next = p.next; // 第2個 換成第3個 
      p.next = q;     //曾經跑到第1地位的原第2個的下一個 就要釀成 原第1個 
      q = p;       //新的第1個 要釀成 以後第一個 
    } 
    return p; 
     
  } 
  //辦法2 head沒重置 
  static Node reverse2(Node head) { 
    //將中央節點的指針指向前一個節點以後依然可以持續向後遍歷鏈表 
    Node p1 = head, p2 = head.next, p3; // 前 中 後 
    //輪換成果 ：012, 123, 234, 345, 456.... 9 10 null 
    while (p2 != null) { 
      p3 = p2.next;  
      p2.next = p1; //指向後 變 指向前 
      p1 = p2;   //2、3向前挪 
      p2 = p3; 
    } 
    head.next = null;//head沒變，當輸入到0時，再要求0.next 為1 
    return p1; 
  } 
}