Java模拟有序链表数据结构的示例

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