有序链表：
按关键值排序。删除链头时，就删除最小(/最大)的值，插入时，搜索插入的位置。
插入时需要比较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;
}
}
更多java模拟有序链表数据结构的示例。