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

在路上

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

Java模拟单链表和双端链表数据结构的实例讲解

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

摘要: 模拟单链表 线性表： 线性表（亦作顺序表）是最基本、最简单、也是最常用的一种数据结构。 线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。 线性表的 ...

模拟单链表

线性表：
线性表（亦作顺序表）是最基本、最简单、也是最常用的一种数据结构。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
线性表的逻辑结构简单，便于实现和操作。
在实际应用中，线性表都是以栈、队列、字符串等特殊线性表的形式来使用的。
线性结构的基本特征为:
1．集合中必存在唯一的一个“第一元素”；
2．集合中必存在唯一的一个 “最后元素” ；
3．除最后一个元素之外，均有 唯一的后继(后件)；
4．除第一个元素之外，均有 唯一的前驱(前件)。

链表：linked list
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
每个数据项都被包含在“链结点”（Link）中。
链结点是一个类的对象，这类可叫做Link。链表中有许多类似的链结点，每个Link中都中包含有一个对下一个链结点引用的字段next。
链表对象本身保存了一个指向第一个链结点的引用first。(若没有first，则无法定位)
链表不能像数组那样(利用下标)直接访问到数据项，而需要用数据间的关系来定位，即访问链结点所引用的下一个链结点，而后再下一个，直至访问到需要的数据
在链头插入和删除的时间复杂度为O(1)，因为只需要改变引用的指向即可
而查找、删除指定结点、在指定结点后插入，这些操作都需要平均都需要搜索链表中的一半结点，效率为O(N)。
单链表：
以“结点的序列”表示线性表 称作线性链表（单链表）
是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。(这组存储单元既可以是连续的，也可以是不连续的)
链结点的结构：

20164884727592.png (180×69)

存放结点值的数据域data;存放结点的引用 的指针域（链域）next
链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
每个结点只有一个链域的链表称为单链表（Single Linked List） ， 一个方向, 只有后继结节的引用

  2. /**
  3. * 单链表:头插法 后进先出
  4. * 将链表的左边称为链头，右边称为链尾。
  5. * 头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。
  6. * 头插法最先得到的是尾结点
  7. * @author stone
  8. */
  9. public class SingleLinkedList<T> {
  11. private Link<T> first; //首结点
  12. public SingleLinkedList() {
  14. }
  16. public boolean isEmpty() {
  17. return first == null;
  18. }
  20. public void insertFirst(T data) {// 插入 到 链头
  21. Link<T> newLink = new Link<T>(data);
  22. newLink.next = first; //新结点的next指向上一结点
  23. first = newLink;
  24. }
  26. public Link<T> deleteFirst() {//删除 链头
  27. Link<T> temp = first;
  28. first = first.next; //变更首结点，为下一结点
  29. return temp;
  30. }
  32. public Link<T> find(T t) {
  33. Link<T> find = first;
  34. while (find != null) {
  35. if (!find.data.equals(t)) {
  36. find = find.next;
  37. } else {
  38. break;
  39. }
  40. }
  41. return find;
  42. }
  44. public Link<T> delete(T t) {
  45. if (isEmpty()) {
  46. return null;
  47. } else {
  48. if (first.data.equals(t)) {
  49. Link<T> temp = first;
  50. first = first.next; //变更首结点，为下一结点
  51. return temp;
  52. }
  53. }
  54. Link<T> p = first;
  55. Link<T> q = first;
  56. while (!p.data.equals(t)) {
  57. if (p.next == null) {//表示到链尾还没找到
  58. return null;
  59. } else {
  60. q = p;
  61. p = p.next;
  62. }
  63. }
  65. q.next = p.next;
  66. return p;
  67. }
  69. public void displayList() {//遍历
  70. System.out.println("List (first-->last):");
  71. Link<T> current = first;
  72. while (current != null) {
  73. current.displayLink();
  74. current = current.next;
  75. }
  76. }
  78. public void displayListReverse() {//反序遍历
  79. Link<T> p = first, q = first.next, t;
  80. while (q != null) {//指针反向，遍历的数据顺序向后
  81. t = q.next; //no3
  82. if (p == first) {// 当为原来的头时，头的.next应该置空
  83. p.next = null;
  84. }
  85. q.next = p;// no3 -> no1 pointer reverse
  86. p = q; //start is reverse
  87. q = t; //no3 start
  88. }
  89. //上面循环中的if里，把first.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给first
  90. first = p;
  91. displayList();
  92. }
  94. class Link<T> {//链结点
  95. T data; //数据域
  96. Link<T> next; //后继指针，结点 链域
  97. Link(T data) {
  98. this.data = data;
  99. }
  100. void displayLink() {
  101. System.out.println("the data is " + data.toString());
  102. }
  103. }
  105. public static void main(String[] args) {
  106. SingleLinkedList<Integer> list = new SingleLinkedList<Integer>();
  107. list.insertFirst(33);
  108. list.insertFirst(78);
  109. list.insertFirst(24);
  110. list.insertFirst(22);
  111. list.insertFirst(56);
  112. list.displayList();
  114. list.deleteFirst();
  115. list.displayList();
  117. System.out.println("find:" + list.find(56));
  118. System.out.println("find:" + list.find(33));
  120. System.out.println("delete find:" + list.delete(99));
  121. System.out.println("delete find:" + list.delete(24));
  122. list.displayList();
  123. System.out.println("----reverse----");
  124. list.displayListReverse();
  125. }
  126. }
复制代码

打印

  2. List (first-->last):
  3. the data is 56
  4. the data is 22
  5. the data is 24
  6. the data is 78
  7. the data is 33
  8. List (first-->last):
  9. the data is 22
  10. the data is 24
  11. the data is 78
  12. the data is 33
  13. find:null
  14. find:linked_list.SingleLinkedList$Link@4b71bbc9
  15. delete find:null
  16. delete find:linked_list.SingleLinkedList$Link@17dfafd1
  17. List (first-->last):
  18. the data is 22
  19. the data is 78
  20. the data is 33
  21. ----reverse----
  22. List (first-->last):
  23. the data is 33
  24. the data is 78
  25. the data is 22
复制代码

单链表:尾插法 、后进先出 ——若将链表的左端固定，链表不断向右延伸，这种建立链表的方法称为尾插法。
尾插法建立链表时，头指针固定不动，故必须设立一个尾部的指针，向链表右边延伸，
尾插法最先得到的是头结点。

  2. public class SingleLinkedList2<T> {
  4. private Link<T> head; //首结点
  5. public SingleLinkedList2() {
  7. }
  9. public boolean isEmpty() {
  10. return head == null;
  11. }
  13. public void insertLast(T data) {//在链尾 插入
  14. Link<T> newLink = new Link<T>(data);
  15. if (head != null) {
  16. Link<T> nextP = head.next;
  17. if (nextP == null) {
  18. head.next = newLink;
  19. } else {
  20. Link<T> rear = null;
  21. while (nextP != null) {
  22. rear = nextP;
  23. nextP = nextP.next;
  24. }
  25. rear.next = newLink;
  26. }
  27. } else {
  28. head = newLink;
  29. }
  30. }
  32. public Link<T> deleteLast() {//删除 链尾
  33. Link<T> p = head;
  34. Link<T> q = head;
  35. while (p.next != null) {// p的下一个结点不为空，q等于当前的p(即q是上一个，p是下一个) 循环结束时，q等于链尾倒数第二个
  36. q = p;
  37. p = p.next;
  38. }
  39. //delete
  40. q.next = null;
  41. return p;
  42. }
  44. public Link<T> find(T t) {
  45. Link<T> find = head;
  46. while (find != null) {
  47. if (!find.data.equals(t)) {
  48. find = find.next;
  49. } else {
  50. break;
  51. }
  52. }
  53. return find;
  54. }
  56. public Link<T> delete(T t) {
  57. if (isEmpty()) {
  58. return null;
  59. } else {
  60. if (head.data.equals(t)) {
  61. Link<T> temp = head;
  62. head = head.next; //变更首结点，为下一结点
  63. return temp;
  64. }
  65. }
  66. Link<T> p = head;
  67. Link<T> q = head;
  68. while (!p.data.equals(t)) {
  69. if (p.next == null) {//表示到链尾还没找到
  70. return null;
  71. } else {
  72. q = p;
  73. p = p.next;
  74. }
  75. }
  77. q.next = p.next;
  78. return p;
  79. }
  81. public void displayList() {//遍历
  82. System.out.println("List (head-->last):");
  83. Link<T> current = head;
  84. while (current != null) {
  85. current.displayLink();
  86. current = current.next;
  87. }
  88. }
  90. public void displayListReverse() {//反序遍历
  91. Link<T> p = head, q = head.next, t;
  92. while (q != null) {//指针反向，遍历的数据顺序向后
  93. t = q.next; //no3
  94. if (p == head) {// 当为原来的头时，头的.next应该置空
  95. p.next = null;
  96. }
  97. q.next = p;// no3 -> no1 pointer reverse
  98. p = q; //start is reverse
  99. q = t; //no3 start
  100. }
  101. //上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head
  102. head = p;
  103. displayList();
  104. }
  106. class Link<T> {//链结点
  107. T data; //数据域
  108. Link<T> next; //后继指针，结点 链域
  109. Link(T data) {
  110. this.data = data;
  111. }
  112. void displayLink() {
  113. System.out.println("the data is " + data.toString());
  114. }
  115. }
  117. public static void main(String[] args) {
  118. SingleLinkedList2<Integer> list = new SingleLinkedList2<Integer>();
  119. list.insertLast(33);
  120. list.insertLast(78);
  121. list.insertLast(24);
  122. list.insertLast(22);
  123. list.insertLast(56);
  124. list.displayList();
  126. list.deleteLast();
  127. list.displayList();
  129. System.out.println("find:" + list.find(56));
  130. System.out.println("find:" + list.find(33));
  132. System.out.println("delete find:" + list.delete(99));
  133. System.out.println("delete find:" + list.delete(78));
  134. list.displayList();
  135. System.out.println("----reverse----");
  136. list.displayListReverse();
  137. }
  138. }
复制代码

打印

  2. List (head-->last):
  3. the data is 33
  4. the data is 78
  5. the data is 24
  6. the data is 22
  7. the data is 56
  8. List (head-->last):
  9. the data is 33
  10. the data is 78
  11. the data is 24
  12. the data is 22
  13. find:null
  14. find:linked_list.SingleLinkedList2$Link@4b71bbc9
  15. delete find:null
  16. delete find:linked_list.SingleLinkedList2$Link@17dfafd1
  17. List (head-->last):
  18. the data is 33
  19. the data is 24
  20. the data is 22
  21. ----reverse----
  22. List (head-->last):
  23. the data is 22
  24. the data is 24
  25. the data is 33
复制代码

模拟双端链表，以链表实现栈和队列
双端链表：
双端链表与传统链表非常相似.只是新增了一个属性-即对最后一个链结点的引用rear
这样在链尾插入会变得非常容易，只需改变rear的next为新增的结点即可，而不需要循环搜索到最后一个节点
所以有insertFirst、insertLast
删除链头时，只需要改变引用指向即可；删除链尾时，需要将倒数第二个结点的next置空，
而没有一个引用是指向它的，所以还是需要循环来读取操作

  2. /**
  3. * 双端链表
  4. * @author stone
  5. */
  6. public class TwoEndpointList<T> {
  7. private Link<T> head; //首结点
  8. private Link<T> rear; //尾部指针
  10. public TwoEndpointList() {
  12. }
  14. public T peekHead() {
  15. if (head != null) {
  16. return head.data;
  17. }
  18. return null;
  19. }
  21. public boolean isEmpty() {
  22. return head == null;
  23. }
  25. public void insertFirst(T data) {// 插入 到 链头
  26. Link<T> newLink = new Link<T>(data);
  27. newLink.next = head; //新结点的next指向上一结点
  28. head = newLink;
  29. }
  31. public void insertLast(T data) {//在链尾 插入
  32. Link<T> newLink = new Link<T>(data);
  33. if (head == null) {
  34. rear = null;
  35. }
  36. if (rear != null) {
  37. rear.next = newLink;
  38. } else {
  39. head = newLink;
  40. head.next = rear;
  41. }
  42. rear = newLink; //下次插入时，从rear处插入
  44. }
  46. public T deleteHead() {//删除 链头
  47. if (isEmpty()) return null;
  48. Link<T> temp = head;
  49. head = head.next; //变更首结点，为下一结点
  50. if (head == null) {
  51. <span style="white-space:pre"> </span>rear = head;
  52. }
  53. return temp.data;
  54. }
  56. public T find(T t) {
  57. if (isEmpty()) {
  58. return null;
  59. }
  60. Link<T> find = head;
  61. while (find != null) {
  62. if (!find.data.equals(t)) {
  63. find = find.next;
  64. } else {
  65. break;
  66. }
  67. }
  68. if (find == null) {
  69. return null;
  70. }
  71. return find.data;
  72. }
  74. public T delete(T t) {
  75. if (isEmpty()) {
  76. return null;
  77. } else {
  78. if (head.data.equals(t)) {
  79. Link<T> temp = head;
  80. head = head.next; //变更首结点，为下一结点
  81. return temp.data;
  82. }
  83. }
  84. Link<T> p = head;
  85. Link<T> q = head;
  86. while (!p.data.equals(t)) {
  87. if (p.next == null) {//表示到链尾还没找到
  88. return null;
  89. } else {
  90. q = p;
  91. p = p.next;
  92. }
  93. }
  94. q.next = p.next;
  95. return p.data;
  96. }
  98. public void displayList() {//遍历
  99. System.out.println("List (head-->last):");
  100. Link<T> current = head;
  101. while (current != null) {
  102. current.displayLink();
  103. current = current.next;
  104. }
  105. }
  107. public void displayListReverse() {//反序遍历
  108. if (isEmpty()) {
  109. return;
  110. }
  111. Link<T> p = head, q = head.next, t;
  112. while (q != null) {//指针反向，遍历的数据顺序向后
  113. t = q.next; //no3
  114. if (p == head) {// 当为原来的头时，头的.next应该置空
  115. p.next = null;
  116. }
  117. q.next = p;// no3 -> no1 pointer reverse
  118. p = q; //start is reverse
  119. q = t; //no3 start
  120. }
  121. //上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head
  122. head = p;
  123. displayList();
  124. }
  126. class Link<T> {//链结点
  127. T data; //数据域
  128. Link<T> next; //后继指针，结点 链域
  129. Link(T data) {
  130. this.data = data;
  131. }
  132. void displayLink() {
  133. System.out.println("the data is " + data.toString());
  134. }
  135. }
  137. public static void main(String[] args) {
  138. TwoEndpointList<Integer> list = new TwoEndpointList<Integer>();
  139. list.insertLast(1);
  140. list.insertFirst(2);
  141. list.insertLast(3);
  142. list.insertFirst(4);
  143. list.insertLast(5);
  144. list.displayList();
  146. list.deleteHead();
  147. list.displayList();
  149. System.out.println("find:" + list.find(6));
  150. System.out.println("find:" + list.find(3));
  152. System.out.println("delete find:" + list.delete(6));
  153. System.out.println("delete find:" + list.delete(5));
  154. list.displayList();
  155. System.out.println("----reverse----");
  156. list.displayListReverse();
  157. }
  158. }
复制代码

打印

  2. List (head-->last):
  3. the data is 4
  4. the data is 2
  5. the data is 1
  6. the data is 3
  7. the data is 5
  8. List (head-->last):
  9. the data is 2
  10. the data is 1
  11. the data is 3
  12. the data is 5
  13. find:null
  14. find:3
  15. delete find:null
  16. delete find:5
  17. List (head-->last):
  18. the data is 2
  19. the data is 1
  20. the data is 3
  21. ----reverse----
  22. List (head-->last):
  23. the data is 3
  24. the data is 1
  25. the data is 2
复制代码

使用链表实现栈 ，用前插 单链表就能实现，
本类采用双端链表实现：

  2. public class LinkStack<T> {
  3. private TwoEndpointList<T> datas;
  5. public LinkStack() {
  6. datas = new TwoEndpointList<T>();
  7. }
  9. // 入栈
  10. public void push(T data) {
  11. datas.insertFirst(data);
  12. }
  14. // 出栈
  15. public T pop() {
  16. return datas.deleteHead();
  17. }
  19. // 查看栈顶
  20. public T peek() {
  21. return datas.peekHead();
  22. }
  24. //栈是否为空
  25. public boolean isEmpty() {
  26. return datas.isEmpty();
  27. }
  29. public static void main(String[] args) {
  30. LinkStack<Integer> stack = new LinkStack<Integer>();
  31. for (int i = 0; i < 5; i++) {
  32. stack.push(i);
  33. }
  34. for (int i = 0; i < 5; i++) {
  35. Integer peek = stack.peek();
  36. System.out.println("peek:" + peek);
  37. }
  38. for (int i = 0; i < 6; i++) {
  39. Integer pop = stack.pop();
  40. System.out.println("pop:" + pop);
  41. }
  43. System.out.println("----");
  44. for (int i = 5; i > 0; i--) {
  45. stack.push(i);
  46. }
  47. for (int i = 5; i > 0; i--) {
  48. Integer peek = stack.peek();
  49. System.out.println("peek:" + peek);
  50. }
  51. for (int i = 5; i > 0; i--) {
  52. Integer pop = stack.pop();
  53. System.out.println("pop:" + pop);
  54. }
  55. }
  56. }
复制代码

打印

  2. peek:4
  3. peek:4
  4. peek:4
  5. peek:4
  6. peek:4
  7. pop:4
  8. pop:3
  9. pop:2
  10. pop:1
  11. pop:0
  12. pop:null
  13. ----
  14. peek:1
  15. peek:1
  16. peek:1
  17. peek:1
  18. peek:1
  19. pop:1
  20. pop:2
  21. pop:3
  22. pop:4
  23. pop:5
复制代码

链表实现 队列 用双端链表实现：

  2. public class LinkQueue<T> {
  3. private TwoEndpointList<T> list;
  5. public LinkQueue() {
  6. list = new TwoEndpointList<T>();
  7. }
  8. //插入队尾
  9. public void insert(T data) {
  10. list.insertLast(data);
  11. }
  12. //移除队头
  13. public T remove() {
  14. return list.deleteHead();
  15. }
  16. //查看队头
  17. public T peek() {
  18. return list.peekHead();
  19. }
  21. public boolean isEmpty() {
  22. return list.isEmpty();
  23. }
  25. public static void main(String[] args) {
  26. LinkQueue<Integer> queue = new LinkQueue<Integer>();
  27. for (int i = 1; i < 5; i++) {
  28. queue.insert(i);
  29. }
  30. for (int i = 1; i < 5; i++) {
  31. Integer peek = queue.peek();
  32. System.out.println("peek:" + peek);
  33. }
  34. for (int i = 1; i < 5; i++) {
  35. Integer remove = queue.remove();
  36. System.out.println("remove:" + remove);
  37. }
  39. System.out.println("----");
  41. for (int i = 5; i > 0; i--) {
  42. queue.insert(i);
  43. }
  44. for (int i = 5; i > 0; i--) {
  45. Integer peek = queue.peek();
  46. System.out.println("peek2:" + peek);
  47. }
  48. for (int i = 5; i > 0; i--) {
  49. Integer remove = queue.remove();
  50. System.out.println("remove:" + remove);
  51. }
  52. }
  53. }
复制代码

打印

  2. peek:1
  3. peek:1
  4. peek:1
  5. peek:1
  6. remove:1
  7. remove:2
  8. remove:3
  9. remove:4
  10. ----
  11. peek2:5
  12. peek2:5
  13. peek2:5
  14. peek2:5
  15. peek2:5
  16. remove:5
  17. remove:4
  18. remove:3
  19. remove:2
  20. remove:1
复制代码

收藏 邀请
上一篇：Selenium处理select标签的下拉框下一篇：Java使用二分法进行查找和排序的示例

最新评论

相关分类

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

;

GMT+8, 2025-5-6 13:25

Copyright 2015-2025 djqfx

返回顶部