实现双向链表

huangapple go评论121阅读模式
英文:

Implement doubly linked list

问题

我在这个论坛上查阅了关于双向链表实现的信息,但对下面的代码无法理解。

  1. // DoublyLinkedList 的实例变量
  2. private final Node<E> header; // 头哨兵
  3. private final Node<E> trailer; // 尾哨兵
  4. private int size = 0; // 链表中元素的数量
  5. private int modCount = 0; // 链表的修改次数(添加或移除操作)
  6. /**
  7. * 创建充当哨兵的两个元素
  8. */
  9. public DoublyLinkedList() {
  10. header = new Node<>(null, null, null); // 创建头哨兵
  11. trailer = new Node<>(null, header, null); // 尾哨兵位于头哨兵之前
  12. header.setNext(trailer); // 头哨兵之后是尾哨兵
  13. }

我看过关于链表和双向链表的视频,但没有看过这种实现。例如,trailer = new Node<> (null,header,null) 的背后逻辑是什么?

英文:

I've looked around on this forum regarding the implementation of doubly linked lists and I can't a grasp of the below code.

  1. // instance variables of the DoublyLinkedList
  2. private final Node&lt;E&gt; header; // header sentinel
  3. private final Node&lt;E&gt; trailer; // trailer sentinel
  4. private int size = 0; // number of elements in the list
  5. private int modCount = 0; // number of modifications to the list (adds or removes)
  6. /**
  7. * Creates both elements which act as sentinels
  8. */
  9. public DoublyLinkedList() {
  10. header = new Node&lt;&gt;(null, null, null); // create header
  11. trailer = new Node&lt;&gt;(null, header, null); // trailer is preceded by header
  12. header.setNext(trailer); // header is followed by trailer
  13. }

I've seen videos about linked lists and doubly ones, but I haven't seen this kind of implementation. What's the logic behind, for example: trailer = new Node&lt;&gt;(null, header, null)?

答案1

得分: 0

你可能有一个类似以下的双向链表:

  1. /**
  2. * 双向链表。
  3. */
  4. public class DoubleLinkedList<E> {
  5. private final Node<E> header; // 头哨兵
  6. private final Node<E> trailer; // 尾哨兵
  7. private int size = 0; // 链表中元素的数量
  8. private int modCount = 0; // 对链表的修改次数(添加或移除操作)
  9. public DoubleLinkedList() {
  10. this.header = new Node<>(
  11. // 头哨兵的后继节点是尾哨兵。
  12. // 设置为:header.setNext(trailer);
  13. null,
  14. // 头哨兵的前驱节点始终为null,
  15. // 因为在第一个节点之前没有节点。
  16. null,
  17. // 节点的有效载荷为null。
  18. // 我猜这只是示例的一部分。
  19. null
  20. );
  21. this.trailer = new Node<>(
  22. // 尾哨兵的后继节点始终为null,
  23. // 因为在最后一个节点之后没有节点。
  24. null,
  25. // 尾哨兵的前驱节点是头哨兵,
  26. // 在构造该对象时设置。
  27. header,
  28. // 节点的有效载荷为null。
  29. // 我猜这只是示例的一部分。
  30. null
  31. );
  32. // 现在头哨兵的后继节点被设置为尾哨兵。
  33. header.setNext(trailer);
  34. }
  35. // 一些链表方法,如add、remove、get等……
  36. /**
  37. * 链表中的节点。
  38. *
  39. * @param <T> 链表中存储对象的类型。
  40. */
  41. static class Node<T> {
  42. /**
  43. * 该节点的前驱节点。
  44. */
  45. private Node<T> predecessor;
  46. /**
  47. * 该节点的后继节点。
  48. */
  49. private Node<T> successor;
  50. /**
  51. * 载荷(有效数据)
  52. */
  53. private final T payload;
  54. public Node(final Node<T> successor, final Node<T> predecessor, final T payload) {
  55. this.predecessor = successor;
  56. this.successor = successor;
  57. this.payload = payload;
  58. }
  59. // 获取器和设置器:
  60. private Node<T> getPredecessor() {
  61. return this.predecessor;
  62. }
  63. private void setNext(final Node<T> next) {
  64. this.predecessor = next;
  65. }
  66. private Node<T> getSuccessor() {
  67. return this.successor;
  68. }
  69. private void setPrevious(final Node<T> previous) {
  70. this.successor = previous;
  71. }
  72. private T getPayload() {
  73. return this.payload;
  74. }
  75. }
  76. }

这个架构不太美观,但我认为这个解释适用于你的情况。

英文:

You have Probably some DoubleLinkedList like:

  1. /**
  2. * A double linked list.
  3. *
  4. */
  5. public class DoubleLinkedList&lt;E&gt; {
  6. private final Node&lt;E&gt; header; // header sentinel
  7. private final Node&lt;E&gt; trailer; // trailer sentinel
  8. private int size = 0; // number of elements in the list
  9. private int modCount = 0; // number of modifications to the list (adds or removes)
  10. public DoubleLinkedList() {
  11. this.header = new Node&lt;&gt;(
  12. // The successor of the header is the trailer.
  13. // It will be set with: header.setNext(trailer);
  14. null,
  15. // The predecessor of the header is always null,
  16. // because there there is no node before the first
  17. null,
  18. // The payload of the node is null.
  19. // I guess it is just a part of the example.
  20. null
  21. );
  22. this.trailer = new Node&lt;&gt;(
  23. // The successor of the trailer is always null,
  24. // because there there is no node after the last
  25. null,
  26. // The predecessor of the trailer is the header
  27. // at construction of this object
  28. header,
  29. // The payload of the node is null.
  30. // I guess it is just a part of the example.
  31. null
  32. );
  33. // Now is the successor of the header set to the trailer.
  34. header.setNext(trailer);
  35. }
  36. // Some list methods like add, remove, get, ...
  37. /**
  38. * The nodes of the List
  39. *
  40. * @param &lt;T&gt; The type of the stored objects in the list.
  41. */
  42. static class Node&lt;T&gt; {
  43. /**
  44. * The predecessor of this node.
  45. */
  46. private Node&lt;T&gt; predecessor;
  47. /**
  48. * The successor of this node.
  49. */
  50. private Node&lt;T&gt; successor;
  51. /**
  52. * The payload
  53. */
  54. private final T payload;
  55. public Node(final Node&lt;T&gt; successor, final Node&lt;T&gt; predecessor, final T payload) {
  56. this.predecessor = successor;
  57. this.successor = successor;
  58. this.payload = payload;
  59. }
  60. // Getter and Setter:
  61. private Node&lt;T&gt; getPredecessor() {
  62. return this.predecessor;
  63. }
  64. private void setNext(final Node&lt;T&gt; next) {
  65. this.predecessor = next;
  66. }
  67. private Node&lt;T&gt; getSuccessor() {
  68. return this.successor;
  69. }
  70. private void setPrevious(final Node&lt;T&gt; previous) {
  71. this.successor = previous;
  72. }
  73. private T getPayload() {
  74. return this.payload;
  75. }
  76. }
  77. }

This is architectural not very beautiful, but I think this explanation matches your case.

答案2

得分: -1

给定一个列表(可以是任何类型),你至少需要知道如何访问第一个元素,以及如何判断是否已经遍历到最后一个元素。

有几种方法可以满足这些要求。

对于链表,为了知道列表从哪里开始,你可以简单地引用第一个节点,或者你可以有一个始终存在的完整的“虚拟”节点。

为了知道列表在哪里结束,你可以有一个空的“next”引用,或者你可以有一个始终存在的完整的“虚拟”节点。

使用虚拟节点的方法通常可以使代码更清晰,因为所有实际节点将始终有一个“previous”节点,而且所有实际节点将始终有一个“next”节点。

这似乎是你的代码片段中采取的方法。

英文:

Given a list (of any kind), you need to know at least how to get to the first element, and how to tell when you've seen the last element.

There are a few ways to arrange for these requirements to be satisfied.

For a linked list, to know where the list starts, you might have a simple references to the first node, or you might have a full 'dummy' node that always exists.

To know where the list ends, you might have a null 'next' reference, or you might have a full 'dummy' node that always exists.

The dummy-node approach can often result in cleaner code, because then all actual nodes will always have a 'previous' node, and all actual nodes will always have a 'next' node.

That seems to be the approach being taken in your code extract.

huangapple
  • 本文由 发表于 2020年10月21日 19:44:55
  • 转载请务必保留本文链接:https://go.coder-hub.com/64462821.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定