Java模拟有序链表数据结构的示例--Java学习网

时间:2016-12-8 8:08:15

  核心提示:有序链表:按关键值排序。删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置。插入时需要比较O(N),平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1),如果一个应用需要频繁的...

有序链表:
按关键值排序。删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置。
插入时需要比较O(N),平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1),
如果一个应用需要频繁的存取(插入/查找/删除)最小(/最大)的数据项,那么有序链表是一个不错的选择
优先级队列 可以使用有序链表来实现
有序链表的插入排序:
对一个无序数组,用有序链表来排序,比较的时间级还是O(N^2)
复制时间级为O(2*N),因为复制的次数较少,第一次放进链表数据移动N次,再从链表复制到数组,又是N次
每插入一个新的链结点,不需要复制移动数据,只需要改变一两个链结点的链域

  1. import java.util.Arrays;
  2. import java.util.Random;
  3. /**
  4. * 有序链表 对数组进行插入排序
  5. * @author stone
  6. */
  7. public class LinkedListInsertSort<T extends Comparable<T>> {
  8. private Link<T> first; //首结点
  9. public LinkedListInsertSort() {
  10. }
  11. public boolean isEmpty() {
  12. return first == null;
  13. }
  14. public void sortList(T[] ary) {
  15. if (ary == null) {
  16. return;
  17. }
  18. //将数组元素插入进链表,以有序链表进行排序
  19. for (T data : ary) {
  20. insert(data);
  21. }
  22. //
  23. }
  24. public void insert(T data) {// 插入 到 链头, 以从小到大排序
  25. Link<T> newLink = new Link<T>(data);
  26. Link<T> current = first, previous = null;
  27. while (current != null && data.compareTo(current.data) > 0) {
  28. previous = current;
  29. current = current.next;
  30. }
  31. if (previous == null) {
  32. first = newLink;
  33. } else {
  34. previous.next = newLink;
  35. }
  36. newLink.next = current;
  37. }
  38. public Link<T> deleteFirst() {//删除 链头
  39. Link<T> temp = first;
  40. first = first.next; //变更首结点,为下一结点
  41. return temp;
  42. }
  43. public Link<T> find(T t) {
  44. Link<T> find = first;
  45. while (find != null) {
  46. if (!find.data.equals(t)) {
  47. find = find.next;
  48. } else {
  49. break;
  50. }
  51. }
  52. return find;
  53. }
  54. public Link<T> delete(T t) {
  55. if (isEmpty()) {
  56. return null;
  57. } else {
  58. if (first.data.equals(t)) {
  59. Link<T> temp = first;
  60. first = first.next; //变更首结点,为下一结点
  61. return temp;
  62. }
  63. }
  64. Link<T> p = first;
  65. Link<T> q = first;
  66. while (!p.data.equals(t)) {
  67. if (p.next == null) {//表示到链尾还没找到
  68. return null;
  69. } else {
  70. q = p;
  71. p = p.next;
  72. }
  73. }
  74. q.next = p.next;
  75. return p;
  76. }
  77. public void displayList() {//遍历
  78. System.out.println("List (first-->last):");
  79. Link<T> current = first;
  80. while (current != null) {
  81. current.displayLink();
  82. current = current.next;
  83. }
  84. }
  85. public void displayListReverse() {//反序遍历
  86. Link<T> p = first, q = first.next, t;
  87. while (q != null) {//指针反向,遍历的数据顺序向后
  88. t = q.next; //no3
  89. if (p == first) {// 当为原来的头时,头的.next应该置空
  90. p.next = null;
  91. }
  92. q.next = p;// no3 -> no1 pointer reverse
  93. p = q; //start is reverse
  94. q = t; //no3 start
  95. }
  96. //上面循环中的if里,把first.next 置空了, 而当q为null不执行循环时,p就为原来的最且一个数据项,反转后把p赋给first
  97. first = p;
  98. displayList();
  99. }
  100. class Link<T> {//链结点
  101. T data; //数据域
  102. Link<T> next; //后继指针,结点 链域
  103. Link(T data) {
  104. this.data = data;
  105. }
  106. void displayLink() {
  107. System.out.println("the data is " + data.toString());
  108. }
  109. }
  110. public static void main(String[] args) {
  111. LinkedListInsertSort<Integer> list = new LinkedListInsertSort<Integer>();
  112. Random random = new Random();
  113. int len = 5;
  114. Integer[] ary = new Integer[len];
  115. for (int i = 0; i < len; i++) {
  116. ary[i] = random.nextInt(1000);
  117. }
  118. System.out.println("----排序前----");
  119. System.out.println(Arrays.toString(ary));
  120. System.out.println("----链表排序后----");
  121. list.sortList(ary);
  122. list.displayList();
  123. }
  124. }
复制代码


打印

  1. ----排序前----
  2. [595, 725, 310, 702, 444]
  3. ----链表排序后----
  4. List (first-->last):
  5. the data is 310
  6. the data is 444
  7. the data is 595
  8. the data is 702
  9. the data is 725
复制代码

单链表反序:

  1. public class SingleLinkedListReverse {
  2. public static void main(String[] args) {
  3. Node head = new Node(0);
  4. Node temp = null;
  5. Node cur = null;
  6. for (int i = 1; i <= 10; i++) {
  7. temp = new Node(i);
  8. if (i == 1) {
  9. head.setNext(temp);
  10. } else {
  11. cur.setNext(temp);
  12. }
  13. cur = temp;
  14. }//10.next = null;
  15. Node h = head;
  16. while (h != null) {
  17. System.out.print(h.getData() + "\t");
  18. h = h.getNext();
  19. }
  20. System.out.println();
  21. //反转1
  22. // h = Node.reverse1(head);
  23. // while (h != null) {
  24. // System.out.print(h.getData() + "\t");
  25. // h = h.getNext();
  26. // }
  27. //反转2
  28. h = Node.reverse1(head);
  29. while (h != null) {
  30. System.out.print(h.getData() + "\t");
  31. h = h.getNext();
  32. }
  33. }
  34. }
  35. /*
  36. * 单链表的每个节点都含有指向下一个节点属性
  37. */
  38. class Node {
  39. Object data;//数据对象
  40. Node next; //下一节点
  41. Node(Object d) {
  42. this.data = d;
  43. }
  44. Node(Object d, Node n) {
  45. this.data = d;
  46. this.next = n;
  47. }
  48. public Object getData() {
  49. return data;
  50. }
  51. public void setData(Object data) {
  52. this.data = data;
  53. }
  54. public Node getNext() {
  55. return next;
  56. }
  57. public void setNext(Node next) {
  58. this.next = next;
  59. }
  60. //方法1 head被重置
  61. static Node reverse1(Node head) {
  62. Node p = null; //反转后新的 头
  63. Node q = head;
  64. //轮换结果:012,123,234,.... 10 null null
  65. while (head.next != null) {
  66. p = head.next; // 第1个 换成第2个 这时p表示原始序列头中的next
  67. head.next = p.next; // 第2个 换成第3个
  68. p.next = q; //已经跑到第1位置的原第2个的下一个 就要变成 原第1个
  69. q = p; //新的第1个 要变成 当前第一个
  70. }
  71. return p;
  72. }
  73. //方法2 head没重置
  74. static Node reverse2(Node head) {
  75. //将中间节点的指针指向前一个节点之后仍然可以继续向后遍历链表
  76. Node p1 = head, p2 = head.next, p3; // 前 中 后
  77. //轮换结果 :012, 123, 234, 345, 456.... 9 10 null
  78. while (p2 != null) {
  79. p3 = p2.next;
  80. p2.next = p1; //指向后 变 指向前
  81. p1 = p2; //2、3向前挪
  82. p2 = p3;
  83. }
  84. head.next = null;//head没变,当输出到0时,再请求0.next 为1
  85. return p1;
  86. }
  87. }

Java免费学习   Java自学网 http://www.javalearns.com

关注微信号:javalearns   随时随地学Java

或扫一扫

随时随地学Java

作者:不详 来源:网络
    你是从哪里知道本网站的?
  • 网友介绍的
  • 百度搜索的
  • Google搜索的
  • 其它搜索过来的
  • 网址输错了进来的
  • 太忙了不记得了
共有评论 0相关评论
发表我的评论
  • 大名:
  • 内容:
  • java学习网(www.javalearns.com) © 2014 版权所有 All Rights Reserved.
  • Email:javalearns@163.com 站长QQ:1356121699 晋ICP备14003680号-3
  • java学习网部分内容来自网络或网友发布,如侵犯了您利益,请发邮件至:javalearns@126.com,我们尽快处理!
  • Java学习网
  • 网站统计
  • 晋公网安备 14042902000001号