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