实现双向链表

Question

我在这个论坛上看了看关于双向链表的实现，但我无法理解下面的代码。

// instance variables of the DoublyLinkedList
    private final Node<E> header;     // header sentinel
    private final Node<E> trailer;    // trailer sentinel
    private int size = 0;       // number of elements in the list
    private int modCount = 0;   // number of modifications to the list (adds or removes)

    /**
     * Creates both elements which act as sentinels
     */
    public DoublyLinkedList() {

        header = new Node<>(null, null, null);      // create header
        trailer = new Node<>(null, header, null);   // trailer is preceded by header
        header.setNext(trailer);                    // header is followed by trailer
    }

看过链表和双链表的视频，但没见过这种实现方式。背后的逻辑是什么，例如：trailer = new Node<>(null, header, null)?

Answer 1

给定一个列表（任何类型），您至少需要知道如何到达第一个元素，以及如何判断何时看到最后一个元素。

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

对于链表，要知道列表从哪里开始，您可能有一个对第一个节点的简单引用，或者您可能有一个始终存在的完整 'dummy' 节点。

要知道列表在哪里结束，您可能有一个空 'next' 引用，或者您可能有一个始终存在的完整 'dummy' 节点。

dummy-node 方法通常可以产生更清晰的代码，因为这样所有实际节点将始终具有一个 'previous' 节点，并且所有实际节点将始终具有一个 'next' 节点。

您的代码摘录中似乎采用了这种方法。

Answer 2

您可能有一些 DoubleLinkedList，例如：

     /**
     * A double linked list.
     *
     */
    public class DoubleLinkedList<E> {
    
        private final Node<E> header;     // header sentinel
        private final Node<E> trailer;    // trailer sentinel
        private int size = 0;       // number of elements in the list
        private int modCount = 0;   // number of modifications to the list (adds or removes)
    
        public DoubleLinkedList() {
            this.header = new Node<>(
                        // The successor of the header is the trailer.
                        // It will be set with: header.setNext(trailer);
                    null,
                        // The predecessor of the header is always null,
                        // because there there is no node before the first
                    null,
                        // The payload of the node is null.
                        // I guess it is just a part of the example.
                    null
            );
    
            this.trailer = new Node<>(
                    // The successor of the trailer is always null,
                    // because there there is no node after the last
                    null,
                    // The predecessor of the trailer is the header
                    // at construction of this object
                    header,
                    // The payload of the node is null.
                    // I guess it is just a part of the example.
                    null
            );
            // Now is the successor of the header set to the trailer.
            header.setNext(trailer);
        }
    
        // Some list methods like add, remove, get, ...
    
    
        /**
         * The nodes of the List
         *
         * @param <T> The type of the stored objects in the list.
         */
        static class Node<T> {
    
            /**
             * The predecessor of this node.
             */
            private Node<T> predecessor;
    
            /**
             * The successor of this node.
             */
            private Node<T> successor;
    
            /**
             * The payload
             */
            private final T payload;
    
            public Node(final Node<T> successor, final Node<T> predecessor, final T payload) {
                this.predecessor = successor;
                this.successor = successor;
                this.payload = payload;
            }
    
            // Getter and Setter:
    
            private Node<T> getPredecessor() {
                return this.predecessor;
            }
    
            private void setNext(final Node<T> next) {
                this.predecessor = next;
            }
    
            private Node<T> getSuccessor() {
                return this.successor;
            }
    
            private void setPrevious(final Node<T> previous) {
                this.successor = previous;
            }
    
            private T getPayload() {
                return this.payload;
            }
        }
    }

这个建筑不是很漂亮，但我认为这个解释符合你的情况。

实现双向链表

Implement doubly linked list

java

data-structures

linked-list

doubly-linked-list