个人随笔
目录
图解双向链表及Java实现
2021-04-28 17:25:35

什么是双向链表?

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

双向链表的逻辑结构图解

在最后添加节点图解

在中间添加节点图解

删除节点图解

Java代码实现

  1. /**
  2. * 双向链表
  3. * @author 爱吃鱼的乌贼
  4. *
  5. */
  6. public class DoubleLink {
  7. private Node head;
  8. private Node tail;
  9. public DoubleLink() {
  10. //初始化链表
  11. head = new Node(0);
  12. //刚开始尾指针和头指针一样,只有一个节点
  13. tail = head;
  14. }
  15. //打印节点信息
  16. public void printNodes() {
  17. Node temp = head;
  18. while(temp!=null) {
  19. System.out.println("[data="+temp.data+";pre="+temp.pre+";next="+temp.next+"]");
  20. temp = temp.next;
  21. }
  22. }
  23. //1、在尾部添加节点
  24. public void addTailNode(Object newData) {
  25. //1、新生成一个节点
  26. Node newNode = new Node(newData);
  27. //2、把节点添加到最后
  28. tail.next = newNode;
  29. newNode.pre=tail;
  30. //3、新节点为尾节点
  31. tail = newNode;
  32. }
  33. //2、按data的顺序递增新增节点:这样子要从后往前找
  34. public void addDataNode(Object newData) {
  35. Node temp = tail;
  36. while(temp!=null) {
  37. if((Integer)newData>=(Integer)temp.data) {
  38. //就在这个位置添加
  39. //如果temp是tail则直接调用在最后添加即可
  40. if(temp==tail) {
  41. addTailNode(newData);
  42. }else {
  43. //若不是尾节点,则直接添加即可
  44. Node newNode = new Node(newData);
  45. newNode.next = temp.next;
  46. newNode.pre = temp;
  47. temp.next.pre =newNode;
  48. temp.next=newNode;
  49. }
  50. return;
  51. }
  52. temp = temp.pre;
  53. }
  54. }
  55. //3、删除节点:这里可以删除除了头节点的任意节点
  56. public void delDataNode(Object newData) {
  57. Node temp = head.next;
  58. while(temp!=null) {
  59. if(newData==temp.data) {
  60. //头节点
  61. if(temp==tail) {
  62. tail = temp.pre;
  63. temp.pre.next=null;
  64. }else {
  65. temp.pre.next=temp.next;
  66. temp.next.pre=temp.pre;
  67. }
  68. return;
  69. }
  70. temp = temp.next;
  71. }
  72. }
  73. public Node getHead() {
  74. return head;
  75. }
  76. public void setHead(Node head) {
  77. this.head = head;
  78. }
  79. public Node getTail() {
  80. return tail;
  81. }
  82. public void setTail(Node tail) {
  83. this.tail = tail;
  84. }
  85. public static void main(String[] args) {
  86. // TODO Auto-generated method stub
  87. }
  88. class Node{
  89. //数据域
  90. private Object data;
  91. //前驱
  92. private Node pre;
  93. //后继
  94. private Node next;
  95. public Node() {
  96. super();
  97. }
  98. @Override
  99. public String toString() {
  100. return "Node [data=" + data + "]";
  101. }
  102. public Node(Object data) {
  103. super();
  104. this.data = data;
  105. }
  106. public Object getData() {
  107. return data;
  108. }
  109. public void setData(Object data) {
  110. this.data = data;
  111. }
  112. public Node getPre() {
  113. return pre;
  114. }
  115. public void setPre(Node pre) {
  116. this.pre = pre;
  117. }
  118. public Node getNext() {
  119. return next;
  120. }
  121. public void setNext(Node next) {
  122. this.next = next;
  123. }
  124. }
  125. }

其它变种自行实现!

代码测试

  1. public class DoubleLinkTest {
  2. public static void main(String[] args) {
  3. DoubleLink doubleLink = new DoubleLink();
  4. doubleLink.addTailNode(1);
  5. doubleLink.addTailNode(2);
  6. doubleLink.addDataNode(4);
  7. doubleLink.addDataNode(3);
  8. doubleLink.printNodes();
  9. System.out.println("------------删除3-------------");
  10. doubleLink.delDataNode(3);
  11. doubleLink.printNodes();
  12. System.out.println("------------删除4-------------");
  13. doubleLink.delDataNode(4);
  14. doubleLink.printNodes();
  15. System.out.println("------------删除0-------------");
  16. doubleLink.delDataNode(0);
  17. doubleLink.printNodes();
  18. }
  19. }

结果输出:

  1. [data=0;pre=null;next=Node [data=1]]
  2. [data=1;pre=Node [data=0];next=Node [data=2]]
  3. [data=2;pre=Node [data=1];next=Node [data=3]]
  4. [data=3;pre=Node [data=2];next=Node [data=4]]
  5. [data=4;pre=Node [data=3];next=null]
  6. ------------删除3-------------
  7. [data=0;pre=null;next=Node [data=1]]
  8. [data=1;pre=Node [data=0];next=Node [data=2]]
  9. [data=2;pre=Node [data=1];next=Node [data=4]]
  10. [data=4;pre=Node [data=2];next=null]
  11. ------------删除4-------------
  12. [data=0;pre=null;next=Node [data=1]]
  13. [data=1;pre=Node [data=0];next=Node [data=2]]
  14. [data=2;pre=Node [data=1];next=null]
  15. ------------删除0-------------
  16. [data=0;pre=null;next=Node [data=1]]
  17. [data=1;pre=Node [data=0];next=Node [data=2]]
  18. [data=2;pre=Node [data=1];next=null]

总结

双向链表实现脑袋中一定要按每个节点都是对象来分析,而head,tail,pre,next,temp这些只是指针而已,坚持这个标准就不会乱。

 9

啊!这个可能是世界上最丑的留言输入框功能~


当然,也是最丑的留言列表

有疑问发邮件到 : suibibk@qq.com 侵权立删
Copyright : 个人随笔   备案号 : 粤ICP备18099399号