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; 
  } 
}