设为首页收藏本站
开启辅助访问

在路上

 找回密码
 立即注册
在路上 › 站点首页 ›学习 › 查看内容

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

2016-7-29 15:37| 发布者: zhangjf| 查看: 747| 评论: 0

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

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

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


打印

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

单链表反序:

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

收藏 邀请
上一篇：java验证用户是否已经登录 java实现自动登录下一篇：java实现FTP文件上传与文件下载

最新评论

相关分类

小黑屋|在路上 ( 蜀ICP备15035742号-1 )  

;

GMT+8, 2025-5-10 21:25

Copyright 2015-2025 djqfx

返回顶部