有序链表：
按关键值排序。删除链头时，就删除最小(/最大)的值，插入时，搜索插入的位置。
插入时需要比较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> { private Link 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 newLink = new Link (data); Link 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 deleteFirst() {//删除 链头 Link temp = first; first = first.next; //变更首结点，为下一结点 return temp; } public Link find(T t) { Link find = first; while (find != null) { if (!find.data.equals(t)) { find = find.next; } else { break; } } return find; } public Link delete(T t) { if (isEmpty()) { return null; } else { if (first.data.equals(t)) { Link temp = first; first = first.next; //变更首结点，为下一结点 return temp; } } Link p = first; Link 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 current = first; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//反序遍历 Link 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 data; //数据域 Link next; //后继指针，结点 链域 Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { LinkedListInsertSort list = new LinkedListInsertSort (); 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
立即学习“Java免费学习笔记（深入）”；
单链表反序:
凡人网络购物系统jsp版(JspShop)
下载
基于jsp+javabean+access(mysql)三层结构的动态购物网站，v1.2包含v1.0中未公开的数据库连接 的java源文件 一，网站前台功能： 产品二级分类展示：一级分类－－二级分类－－产品列表－－详细介绍（名称，图片，市场价，会员价，是否推荐，功能介绍等） 产品搜索：关键字模糊搜索 定购产品：选择商品－－确认定购－－填写收货人信息－－选择付款方式－－订单号自动生成（限登录用户）
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免费学习笔记（深入）”；
更多Java模拟有序链表数据结构的示例相关文章请关注PHP中文网！
